C. Expected Destructiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou have a set S of n distinct integers between 1 and m.Each second you do the following steps:   Pick an element x in S uniformly at random.  Remove x from S.  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}.InputThe 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.OutputOutput 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
NoteFor test 1, here is a list of all the possible scenarios and their probabilities:  [1, 3] (50% chance) \to [1] \to [2] \to [3] \to []  [1, 3] (50% chance) \to [2, 3] (50% chance) \to [2] \to [3] \to []  [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}.
2 3
1 3

750000009 
['combinatorics', 'dp', 'math', 'probabilities', '*2500']