This is the way it always was.
This is the way it always will be.
All will be forgotten again soon...
Jellyfish играет в карточную игру для одного игрока под названием «Slay the Spire». Всего есть \(n\) карт, пронумерованных от \(1\) до \(n\). У \(i\)-й карты есть сила \(c_i\).
Дана бинарная строка \(s\) длины \(n\). Если \(s_i = \texttt{0}\), то \(i\)-я карта изначально находится в колоде. Если \(s_i = \texttt{1}\), то \(i\)-я карта изначально находится в руке Jellyfish.
Jellyfish будет повторять следующий процесс до тех пор, пока либо её рука, либо колода не опустеют:
- Пусть \(x\) — это сила карты с наибольшей силой в руке.
- Поместить одну карту с силой \(x\) обратно в колоду.
- Случайным образом взять \(x\) карт из колоды. Все подмножества \(x\) карт из колоды имеют равные шансы быть вытянутыми. Если в колоде меньше \(x\) карт, Jellyfish вытянет все карты.
Найдите вероятность того, что Jellyfish сможет опустошить колоду в конце этого процесса, по модулю \(1\,000\,000\,007\).
Формально, пусть \(M=1\,000\,000\,007\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\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}\).
Выходные данные
Для каждого набора входных данных выведите вероятность того, что Jellyfish сможет опустошить колоду, по модулю \(1\,000\,000\,007\).
Примечание
В первом наборе входных данных Jellyfish будет продолжать играть картами с силой \(1\) до тех пор, пока не вытянет карту с силой \(0\) или с силой \(2\). Если Jellyfish вытянет карту с силой \(0\), она в конце концов опустошит свою руку. Если Jellyfish вытянет карту с силой \(2\), она в итоге опустошит колоду. Поскольку шансы вытянуть \(0\) или \(2\) равны, ответ будет \(\frac{1}{2}\), а \(2 \cdot 500\,000\,004 \equiv 1 \pmod {10^9+7}\).