У вас есть набор \(S\) из \(n\) различных целых чисел в диапазоне от \(1\) до \(m\).
Каждую секунду вы выполняете следующие действия:
- Выбираете элемент \(x\) из \(S\) равномерно случайным образом.
- Удаляете \(x\) из \(S\).
- Если \(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}\).
Выходные данные
Выведите одно целое число — ожидаемое количество секунд до того момента, когда \(S\) станет пустым, по модулю \(1\,000\,000\,007\).
Примечание
Для теста 1 приведен список всех возможных сценариев и их вероятностей:
- \([1, 3]\) (вероятность 50%) \(\to\) \([1]\) \(\to\) \([2]\) \(\to\) \([3]\) \(\to\) \([]\)
- \([1, 3]\) (вероятность 50%) \(\to\) \([2, 3]\) (вероятность 50%) \(\to\) \([2]\) \(\to\) \([3]\) \(\to\) \([]\)
- \([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
|
2 3
1 3
|
750000009
|
|
2
|
5 10
1 2 3 4 5
|
300277731
|
|
3
|
5 10
2 3 6 8 9
|
695648216
|
|
4
|
1 100
1
|
100
|