D2. Параллельные вселенные (сложная)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хайди понравилось проводить моделирование, потому что она точно знала, где и как рождаются новые вселенные, и где и как ломаются несуществующие связи.

Однако, мультивселенная работает куда более загадочным образом. Для начала, она работает с случайным образом согласно некоторым вероятностям, что для некоторых людей уже может показаться загадочным.

В каждый момент, когда принимается решение, происходит одно из двух событий. Обозначим за $$$l$$$ текущую длину мультивселенной. С вероятностью $$$p_{create} = 1 - \frac{l}{m}$$$ создаётся новая вселенная. С вероятностью $$$p_{break}=\frac{l}{m}$$$ разрывается одна из несуществующих связей.

В частности,

  • Если создаётся вселенная, то она встраивается либо между двумя соседними вселенными, либо с одного из двух сторон. Каждая из позиций выбирается равновероятно с вероятностью $$$\frac{1}{l + 1}$$$.
  • Когда ломается одна из связей, возникает разрез между двумя соседними вселенными, где каждый из разрезов выбирается равновероятно с вероятностью $$$\frac{1}{l-1}$$$. Таким образом мультивселенная разбивается на два отрезка, и отрезок НЕ содержащий Доктора изчезает.

Как и раньше, Доктор находится в одной конкретной вселенной. Однако, если в какой-то момент времени мультивселенная изменится так, что Доктор обнаружит себя в крайней левой или крайней правой вселенной, то ТАРДИС перестанет функционировать.

В таком случае Доктору придётся обойти всю мультивселенную, чтобы найти способ её исправить.

Нас интересует математическое ожидание длины мультивселенной, к тому моменту, когда это событие произойдёт.

Входные данные

Первая и единственная строка содержит три целых числа $$$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
Примечание

В первом и втором примере Доктор уже находится на одном из концов мультивселенной, а значит не будет произведено никаких изменений.

В третьем примере мультивселенная может сломатся только в позиции, которая приведёт к тому, что Доктор окажется на одном из концов мультивселенной.

В четвёртом примере ситуация несколько более запутанная, так как мультивселенная может расширяться и сужаться много раз.