您有一组 $$$S$$$ 的 $$$n$$$ 不同整数,介于 $$$1$$$ 和 $$$m$$$ 之间。
每一秒您都会执行以下步骤:
1. 统一随机选取$$$S$$$中的一个元素$$$x$$$。
2. 从 $$$S$$$ 中删除 $$$x$$$。
3. 如果 $$$x+1 \leq m$$$ 和 $$$x+1$$$ 不在 $$$S$$$ 中,则将 $$$x+1$$$ 添加到 $$$S$$$ 中。
$$$S$$$ 为空之前预计的秒数是多少?
输出对 $$$1\,000\,000\,007$$$ 取模的答案。
正式地,让 $$$P = 1\,000\,000\,007$$$。可以证明,答案可以表示为不可约分数 $$$\frac{a}{b}$$$,其中 $$$a$$$ 和 $$$b$$$ 是整数,$$$b \not \equiv 0 \pmod{P}$$$。输出等于 $$$a \cdot b^{-1} \bmod P$$$ 的整数。换句话说,输出一个整数 $$$z$$$,使得 $$$0 \le z < P$$$ 且 $$$z \cdot b \equiv a \pmod{P}$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq m \leq 500$$$) - 集合 $$$S$$$ 中的元素数量以及 $$$S$$$ 中元素值的上限。
第二行包含 $$$n$$$ 整数 $$$S_1,\,S_2,\,\dots,\,S_n$$$ ($$$1 \leq S_1 < S_2 < \ldots < S_n \leq m$$$) — 集合 $$$S$$$ 的元素。
输出
输出一个整数 - $$$S$$$ 为空之前的预期秒数,以 $$$1\,000\,000\,007$$$ 为模。
示例
输入 #1
2 3 1 3
输出 #1
750000009
输入 #2
5 10 1 2 3 4 5
输出 #2
300277731
输入 #3
5 10 2 3 6 8 9
输出 #3
695648216
输入#4
1 100 1
输出#4
100
注意
对于测试 1,以下是所有可能场景及其概率的列表:
1. $$$[1, 3]$$$(50% 几率)$$$\至$$$ $$$[1]$$$ $$$\至$$$ $$$[2]$$$ $$$\至$$$ $$$[3]$$$ $$$\至$$$ $$$[]$$$
2. $$$[1, 3]$$$(50% 几率)$$$\to$$$ $$$[2, 3]$$$(50% 几率)$$$\to$$$ $$$[2]$$$ $$$\to$$$ $$$[3]$$$ $$$\to$$$ $$$[]$$$
3. $$$[1, 3]$$$(50% 几率)$$$\to$$$ $$$[2, 3]$$$(50% 几率)$$$\to$$$ $$$[3]$$$ $$$\to$$$ $$$[]$$$
将它们相加,我们得到 $$$\frac{1}{2}\cdot 4 + \frac{1}{4} \cdot 4 + \frac{1}{4} \cdot 3 = \frac{15}{4}$$$。我们看到 $$$750000009 \cdot 4 \equiv 15 \pmod{1\,000\,000\,007}$$$。