该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 3F. Time to empty

Description

在数集 \(S\) 中有在 \(1\) 和 \(m\) 之间的 \(n\) 个不同整数。从第0秒开始，你可以在每一秒进行以下操作：

1. 均匀随机选择 \(S\) 中的一个元素 \(x\)
2. 从 \(S\) 中删除 \(x\)
3. 如果 \(x+1 \leq m\) 且 \(x+1\) 不在 \(S\) 中，则将 \(x+1\) 添加到 \(S\) 中。

请问在 \(S\) 变为空集之前预期的秒数是多少? 输出答案对 \(1e9+7\) 取模。

正式地，让 \(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\) 。

Input Format

第一行包含两个整数 \(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\) 中的元素。

Output Format

输出一行一个整数，表示直到 \(S\) 为空的期望秒数，对 \(1e9+7\) 取模。

Test Case 1

input

2 3
1 3

output

750000009

Test Case 2

input

5 10
1 2 3 4 5

output

300277731

Test Case 3

input

5 10
2 3 6 8 9

output

695648216

Note

对于样例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}\) 。