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