销毁的期望时间

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

你有一个包含 $n$ 个不同整数的集合 $S$，这些整数的取值范围在 $1$ 到 $m$ 之间。

每一秒你会进行以下操作：

1. 从 $S$ 中等概率随机选取一个元素 $x$。
2. 将 $x$ 从 $S$ 中移除。
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}$。请输出满足 $0 \le z < P$ 且 $z \cdot b \equiv a \pmod{P}$ 的整数 $z$。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 500$）——集合 $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%概率）$\to$ $[1]$ $\to$ $[2]$ $\to$ $[3]$ $\to$ $[]$
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}$。

数据范围

对于所有数据，$1\le n\le m\le500$，$1\le S_1<\cdots<S_n\le m$。

每个测试点独立计分。