C. Ожидаемое разрушение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть набор $$$S$$$ из $$$n$$$ различных целых чисел в диапазоне от $$$1$$$ до $$$m$$$.

Каждую секунду вы выполняете следующие действия:

  1. Выбираете элемент $$$x$$$ из $$$S$$$ равномерно случайным образом.
  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}$$$. Выведите целое число, равное $$$a \cdot b^{-1} \bmod P$$$. Другими словами, выведите такое целое число $$$z$$$, что $$$0 \le z < P$$$ и $$$z \cdot b \equiv a \pmod{P}$$$.

Входные данные

Первая строка содержит два целых числа $$$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$$$.

Выходные данные

Выведите одно целое число — ожидаемое количество секунд до того момента, когда $$$S$$$ станет пустым, по модулю $$$1\,000\,000\,007$$$.

Примеры
Входные данные
2 3
1 3
Выходные данные
750000009
Входные данные
5 10
1 2 3 4 5
Выходные данные
300277731
Входные данные
5 10
2 3 6 8 9
Выходные данные
695648216
Входные данные
1 100
1
Выходные данные
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}$$$.