题目描述

小可可正在和波特玩卡牌游戏。

这个游戏有 $m$ 种卡牌。种类为 $x$ 的卡牌价值也为 $x$。首先，波特一共会进行 $n$ 次抽卡来确定游戏的牌堆。第 $i$ 次，会有 $a_i$ 种新的卡牌解锁。也就是说如果第 $i$ 次抽卡之前第 $1\sim s$ 种卡牌解锁了，那么第 $i$ 次时第 $1 \sim s + a_i$ 种卡牌都会解锁。保证 $\sum_{i=1}^{n}{ai} = m$。 初始没有卡牌解锁。

在第 $i$ 次抽卡时，波特会等概率随机选择一种已经被解锁的卡牌，并且取出两张这个种类的卡牌，依次放在现在所有牌的右边。在 $n$ 次抽卡结束后，一共会有 $2n$ 张卡牌从左向右排成一排作为游戏的牌堆。小可可知道这 $2n$ 张卡牌各自的价值。

现在，小可可和波特会轮流从这个牌堆中进行抽卡，直到抽完所有卡牌，小可可先手。波特每次抽卡只会取走当前牌堆中最左边的卡牌。而小可可可以在当前牌堆中任意选择一张取走。小可可希望抽卡结束后自己手中的卡牌价值总和最大。他想要知道，如果自己采取最优策略，那么期望得到的价值是多少呢？你只需要告诉他答案对 $10^9 + 7$ 取模的结果就行。

关于期望：设离散型随机变量 $X$ 的概率分布为 $p_i = P\{X = x_i\}$，那么我们称 $E = \sum x_ip_i$ 的值为 $X$ 的期望。不过在本题中，由于每种可能的情况出现概率相等，所以你可以简单地理解为所有方案中小可可得到的卡牌价值总和除以总方案数。

关于有理数取余：不难发现答案一定是一个有理数，设其为 $C = \frac{A}{B}$，其中 $A,B$ 互质，你需要输出 $C \mod 1000000007$ 的值。这个值被定义为 $Bx ≡ A(\mod 1000000007)$ 的最小非负整数解。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数表示 $a$。

输出格式

输出一行一个整数表示答案。

样例 1

2 3
1 2

4

样例 1 解释

第 $1$ 次，解锁的卡牌种类只有 $1$，于是波特会取出两张 $1$ 卡牌。

第 $2$ 次，解锁的卡牌种类有 $1, 2, 3$。波特会随机取出某一种类的两张卡牌。于是有如下三种可能：

• 牌堆中的卡牌从左到右分别为：$1, 1, 1, 1$，概率为 $\frac{1}{3}$，小可可可以获得的最大价值为 $1 + 1 = 2$。
• 牌堆中的卡牌从左到右分别为：$1, 1, 2, 2$，概率为 $\frac{1}{3}$，小可可可以获得的最大价值为 $2 + 2 = 4$。
• 牌堆中的卡牌从左到右分别为：$1, 1, 3, 3$，概率为 $\frac{1}{3}$，小可可可以获得的最大价值为 $3 + 3 = 6$。

于是答案为 $2 × \frac{1}{3} + 4 × \frac{1}{3} + 6 × \frac{1}{3} = 4$。

数据规模与约定

测试点编号	$n\le$	$m\le$	特殊性质
$1 \sim 2$	3		无
$3 \sim 6$	8
$7 \sim 9$	500	500	$a_1=m$
$10 \sim 13$			无
$14 \sim 15$		$10^5$
$16 \sim 19$	100	$10^9$
$20 \sim 21$	500		$a_1=m$
$22 \sim 25$			无

对于 $100\%$ 的数据，满足 $1 ≤ n ≤ 500$ , $1 ≤ m ≤ 10^9$ , $0 ≤ a_i ≤ m$。保证 $\sum_{i=1}^{n}{a_i} = m$ 并且 $a_1 > 0$。

ex_card1.in  ex_card1.ans

ex_card2.in  ex_card2.ans

ex_card3.in  ex_card3.ans

ex_card4.in  ex_card4.ans

ex_card5.in  ex_card5.ans

ex_card6.in  ex_card6.ans

ex_card7.in  ex_card7.ans

ex_card8.in  ex_card8.ans

ex_card9.in  ex_card9.ans