CF1184D2.Parallel Universes (Hard)

Heidi enjoyed performing the simulation because she knew exactly when a new universe would be formed and where, and when a non-existent link would be broken and where.

However, the multiverse itself works in mysterious ways. Well, it works using probabilities, which to some people is mysterious.

At each unit time, when a decision is made, one of the two events will happen randomly. Let's denote $l$ as the current length of the multiverse. With a probability of $p_{create} = 1 - \frac{l}{m}$, a universe will be created. With a probability of $p_{break}=\frac{l}{m}$, a non-existent link will be broken at some position.

More specifically,

• When a universe is created, it will manifest itself between any two adjacent universes or at one of the ends. Each position occurs with a probability of $\frac{1}{l + 1}$.
• When a link is broken, it could be cut between any two adjacent universes, each with a probability of $\frac{1}{l-1}$. After separating the multiverse into two segments, the segment NOT containing the Doctor will cease to exist.

As earlier, the Doctor remains in the same universe. However, if at some point the multiverse breaks in such a way that the Doctor finds himself at the leftmost or rightmost end of it, the TARDIS stops functioning.

In such a case, the Doctor must actually walk across the multiverse to find the tools to fix it.

We are interested in the expected value of the length of the multiverse when such an event occurs.

海蒂很喜欢进行这个模拟，因为她能准确地知道新宇宙将在何时、何地形成，以及一个不存在的连接将在何时、何地被切断。

然而，多元宇宙本身以神秘的方式运行——嗯，它其实依靠概率运行，而对某些人来说，概率本身就是神秘的。

在每个单位时间，当做出一次决策时，以下两个事件之一将随机发生。记 $l$ 为当前多元宇宙的长度。以概率 $p_{\text{create}} = 1 - \frac{l}{m}$，将创建一个新宇宙；以概率 $p_{\text{break}} = \frac{l}{m}$，将在某个位置切断一个不存在的连接。

更具体地说：

• 当创建一个新宇宙时，它将出现在任意两个相邻宇宙之间，或出现在两端之一。每个位置出现的概率均为 $\frac{1}{l + 1}$。
• 当切断一个连接时，该连接可能位于任意两个相邻宇宙之间，每种情况发生的概率均为 $\frac{1}{l-1}$。切断后，多元宇宙被分为两段；不包含博士的那一段将立即消失。

如前所述，博士始终停留在同一个宇宙中。然而，若在某一时刻，多元宇宙的断裂方式导致博士发现自己处于其最左端或最右端，则TARDIS将停止运作。

此时，博士必须亲自穿越整个多元宇宙，去寻找修复它的工具。

我们关心的是：当上述事件发生时，多元宇宙长度的期望值。

The first and only line contains three integers $n$, $k$ and $m$ $(1 \le k \le n \le m \le 250)$, the initial length of the multiverse, the initial position of the Doctor, and the maximum possible length of the multiverse.

第一行且唯一一行包含三个整数 $n$、$k$ 和 $m$（$1 \le k \le n \le m \le 250$），分别表示多元宇宙的初始长度、博士的初始位置以及多元宇宙可能的最大长度。

Output a single integer on a single line, indicating the expected length of the multiverse.

If the answer is $\frac{p}{q}$, please print $r$ where $p \equiv r \cdot q (\text{mod } 10^9 + 7)$.

在单独一行上输出一个整数，表示多元宇宙的期望长度。

若答案为 $\frac{p}{q}$，请输出满足 $p \equiv r \cdot q \pmod{10^9 + 7}$ 的整数 $r$。

For the first and the second test case, without any change to the multiverse, the Doctor is already at one of the ends.

For the third test case, the multiverse can only break at a position, which renders the Doctor at one of its ends.

For the fourth case, things seem to be a little more complicated, because the multiverse can grow and then be broken again.

对于第一个和第二个测试用例，无需对多重宇宙进行任何改动，博士已经位于其某一端。

对于第三个测试用例，多重宇宙只能在某个位置断裂，从而使博士位于其某一端。

对于第四个测试用例，情况似乎稍显复杂，因为多重宇宙可以先扩张，然后再被再次断裂。