CF1854C.Expected Destruction

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 \lt P$ and $z \cdot b \equiv a \pmod{P}$.

你有一个由 $n$ 个互不相同的整数组成的集合 $S$，其中每个整数均在 $1$ 到 $m$ 之间（含端点）。

每秒钟，你执行以下步骤：

1. 在 $S$ 中均匀随机地选取一个元素 $x$；
2. 将 $x$ 从 $S$ 中移除；
3. 若 $x+1 \leq m$ 且 $x+1 \notin 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$。换言之，输出满足 $0 \le z < P$ 且 $z \cdot b \equiv a \pmod{P}$ 的整数 $z$。

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 \lt S_2 \lt \ldots \lt S_n \leq m$) — the elements of the set $S$.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 500$）—— 分别表示集合 $S$ 中的元素个数以及集合 $S$ 中元素值的上界。

第二行包含 $n$ 个整数 $S_1,\,S_2,\,\dots,\,S_n$（$1 \leq S_1 \lt S_2 \lt \ldots \lt S_n \leq m$）—— 表示集合 $S$ 的元素。

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

输出一个整数——即 $S$ 变为空集所需的期望秒数，对 $1\,000\,000\,007$ 取模。

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}$.

对于测试 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}$。