Хайди понравилось проводить моделирование, потому что она точно знала, где и как рождаются новые вселенные, и где и как ломаются несуществующие связи.
Однако, мультивселенная работает куда более загадочным образом. Для начала, она работает с случайным образом согласно некоторым вероятностям, что для некоторых людей уже может показаться загадочным.
В каждый момент, когда принимается решение, происходит одно из двух событий. Обозначим за \(l\) текущую длину мультивселенной. С вероятностью \(p_{create} = 1 - \frac{l}{m}\) создаётся новая вселенная. С вероятностью \(p_{break}=\frac{l}{m}\) разрывается одна из несуществующих связей.
В частности,
- Если создаётся вселенная, то она встраивается либо между двумя соседними вселенными, либо с одного из двух сторон. Каждая из позиций выбирается равновероятно с вероятностью \(\frac{1}{l + 1}\).
- Когда ломается одна из связей, возникает разрез между двумя соседними вселенными, где каждый из разрезов выбирается равновероятно с вероятностью \(\frac{1}{l-1}\). Таким образом мультивселенная разбивается на два отрезка, и отрезок НЕ содержащий Доктора изчезает.
Как и раньше, Доктор находится в одной конкретной вселенной. Однако, если в какой-то момент времени мультивселенная изменится так, что Доктор обнаружит себя в крайней левой или крайней правой вселенной, то ТАРДИС перестанет функционировать.
В таком случае Доктору придётся обойти всю мультивселенную, чтобы найти способ её исправить.
Нас интересует математическое ожидание длины мультивселенной, к тому моменту, когда это событие произойдёт.
Выходные данные
Выведите единственное целое число — математическое ожидание длины вселенной.
В случае если ответом является \(\frac{p}{q}\), то выведите \(r\), где \(p \equiv r \cdot q (\text{mod } 10^9 + 7)\).
Примечание
В первом и втором примере Доктор уже находится на одном из концов мультивселенной, а значит не будет произведено никаких изменений.
В третьем примере мультивселенная может сломатся только в позиции, которая приведёт к тому, что Доктор окажется на одном из концов мультивселенной.
В четвёртом примере ситуация несколько более запутанная, так как мультивселенная может расширяться и сужаться много раз.