题目描述

你正在玩一个抽卡游戏。

一共有 $n$ 种卡片，其中第 $i$ 种卡片在商店中的售价为 $a_i$。

现在游戏推出了一个活动：你可以花费 $b$ 元，随机获得一张卡片。每种卡片出现的概率均为

你可以按照任意顺序访问商店和参加活动。

请计算在最优策略下，集齐全部 $n$ 种卡片所需花费的最小期望值。

输入格式

从文件 barricade.in 中读入数据。

第一行包含两个整数 $n,b$，分别表示卡片种类数和参加一次活动所需的费用。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每种卡片在商店中的售价。

输出格式

输出到文件 barricade.out 中。

输出一行一个整数，表示最优策略下所需花费的最小期望值，对

取模后的结果。

样例 1

输入

2 3
3 4

输出

499122183

样例解释

答案为 $6.5$。

最优策略是先参加一次活动，再到商店购买尚未获得的卡片。

样例 2

输入

8 3
3 1 4 1 5 9 2 6

输出

817609690

数据范围与约定

对于全部测试数据：