310586: CF1855E. Expected Destruction

E. Expected Destructiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have a set $S$ of $n$ distinct integers between $1$ and $m$.

Each second you do the following steps:

1. Pick an element $x$ in $S$ uniformly at random.
2. Remove $x$ from $S$.
3. If $x+1 \leq m$ and $x+1$ is not in $S$, add $x+1$ to $S$.

What is the expected number of seconds until $S$ is empty?

Output the answer modulo $1\,000\,000\,007$.

Formally, let $P = 1\,000\,000\,007$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are integers and $b \not \equiv 0 \pmod{P}$. Output the integer equal to $a \cdot b^{-1} \bmod P$. In other words, output an integer $z$ such that $0 \le z < P$ and $z \cdot b \equiv a \pmod{P}$.

Input

The first line contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 500$) — the number of elements in the set $S$ and the upper bound on the value of the elements in $S$.

The second line contains $n$ integers $S_1,\,S_2,\,\dots,\,S_n$ ($1 \leq S_1 < S_2 < \ldots < S_n \leq m$) — the elements of the set $S$.

Output

Output a single integer — the expected number of seconds until $S$ is empty, modulo $1\,000\,000\,007$.

ExamplesInput

2 3
1 3

Output

750000009

Input

5 10
1 2 3 4 5

Output

300277731

Input

5 10
2 3 6 8 9

Output

695648216

Input

1 100
1

Output

100

Note

For test 1, here is a list of all the possible scenarios and their probabilities:

1. $[1, 3]$ (50% chance) $\to$ $[1]$ $\to$ $[2]$ $\to$ $[3]$ $\to$ $[]$
2. $[1, 3]$ (50% chance) $\to$ $[2, 3]$ (50% chance) $\to$ $[2]$ $\to$ $[3]$ $\to$ $[]$
3. $[1, 3]$ (50% chance) $\to$ $[2, 3]$ (50% chance) $\to$ $[3]$ $\to$ $[]$

Adding them up, we get $\frac{1}{2}\cdot 4 + \frac{1}{4} \cdot 4 + \frac{1}{4} \cdot 3 = \frac{15}{4}$. We see that $750000009 \cdot 4 \equiv 15 \pmod{1\,000\,000\,007}$.

题目大意：
你有一个由n个不同的整数组成的集合S，这些整数在1到m之间。每一秒钟，你按照以下步骤操作：

1. 从S中均匀随机选择一个元素x。
2. 将x从S中移除。
3. 如果x+1 ≤ m并且x+1不在S中，将x+1添加到S中。

问S变空所需的期望秒数是多少？

输出答案对1,000,000,007取模的结果。

输入数据格式：
第一行包含两个整数n和m（1 ≤ n ≤ m ≤ 500）——集合S中的元素数量和S中元素值的上限。
第二行包含n个整数S1, S2, …, Sn（1 ≤ S1 < S2 < … < Sn ≤ m）——集合S的元素。

输出数据格式：
输出一个整数——S变空所需的期望秒数，对1,000,000,007取模的结果。

例如：
输入：
2 3
1 3
输出：
750000009

解释：
对于第一个测试用例，所有可能的情况及其概率如下：
1. [1, 3] (50%的概率) -> [1] -> [2] -> [3] -> [] (耗时4秒)
2. [1, 3] (50%的概率) -> [2, 3] (50%的概率) -> [2] -> [3] -> [] (耗时4秒)
3. [1, 3] (50%的概率) -> [2, 3] (50%的概率) -> [3] -> [] (耗时3秒)

将这些情况加起来，得到总期望秒数为 15/4。我们可以看到750000009 * 4 ≡ 15 (mod 1,000,000,007)。题目大意： 你有一个由n个不同的整数组成的集合S，这些整数在1到m之间。每一秒钟，你按照以下步骤操作： 1. 从S中均匀随机选择一个元素x。 2. 将x从S中移除。 3. 如果x+1 ≤ m并且x+1不在S中，将x+1添加到S中。 问S变空所需的期望秒数是多少？ 输出答案对1,000,000,007取模的结果。 输入数据格式： 第一行包含两个整数n和m（1 ≤ n ≤ m ≤ 500）——集合S中的元素数量和S中元素值的上限。 第二行包含n个整数S1, S2, …, Sn（1 ≤ S1 < S2 < … < Sn ≤ m）——集合S的元素。 输出数据格式： 输出一个整数——S变空所需的期望秒数，对1,000,000,007取模的结果。 例如： 输入： 2 3 1 3 输出： 750000009 解释： 对于第一个测试用例，所有可能的情况及其概率如下： 1. [1, 3] (50%的概率) -> [1] -> [2] -> [3] -> [] (耗时4秒) 2. [1, 3] (50%的概率) -> [2, 3] (50%的概率) -> [2] -> [3] -> [] (耗时4秒) 3. [1, 3] (50%的概率) -> [2, 3] (50%的概率) -> [3] -> [] (耗时3秒) 将这些情况加起来，得到总期望秒数为 15/4。我们可以看到750000009 * 4 ≡ 15 (mod 1,000,000,007)。