Для отслеживания курса криптовалют трейдер Василий изобрел удивительный прибор, состоящий из \(n\) лампочек, расположенных в ряд. Прибор работает следующим образом:
Изначально все лампочки в приборе Василия выключены. На очередной итерации прибор Василия равновероятно выбирает выключенную лампочку и включает её, подсказывая Василию, в какую криптовалюту ему стоит вложиться. Если после этой итерации среди каких-то \(k\) подряд идущих лампочек находится более одной включенной, то прибор Василия завершает свою работу.
Василий не любит неопределенности, поэтому просит вас посчитать матожидание количества включенных лампочек в приборе после завершения его работы.
Выходные данные
Для каждого тестового примера выведите ответ по модулю \(10^9+7\). Формально, пусть \(M = 10^9+7\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, и \(q \not \equiv 0 \pmod{M}\). Выведите целое число, равное \(p \cdot q^{-1} \bmod M\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p \pmod{M}\).
Примечание
Объяснение первого тестового примера:
Выпишем все возможные последовательности включений лампочек, которые завершают работу прибора:
- \((1, 2)\) — включены \(2\) лампочки
- \((1, 3, 2)\) — включены \(3\) лампочки
- \((2, 1)\) — включены \(2\) лампочки
- \((2, 3)\) — включены \(2\) лампочки
- \((3, 2)\) — включены \(2\) лампочки
- \((3, 1, 2)\) — включены \(3\) лампочки
Тогда итоговое матожидание будет равняться \(\frac{2}{6}\) + \(\frac{3}{6}\) + \(\frac{2}{6}\) + \(\frac{2}{6}\) + \(\frac{2}{6}\) + \(\frac{3}{6}\) = \(\frac{14}{6}\) = \(\frac{7}{3}\).
Тогда требуемый для вывода ответ это \(333333338\), так как \(333333338 \cdot 3 \equiv 7 \pmod{10^9+7}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
15 2
40 15
|
333333338
141946947
329622137
|