Parallel Universes (Hard)

题意翻译

海地喜欢观察宇宙。 有一天，他发明了一个宇宙观察器，可以观察到所有的宇宙。这些宇宙目前一共有 $n$ 个，它们排成一行，海地在第 $k$ 个宇宙里。经过观察，他发现，他在每单位时间可以在任意两个宇宙之间或是所有宇宙的两端插入一个宇宙，或者将整个宇宙序列划分为非空的两部分，并丢掉不包含自己所在宇宙的那一部分，且他每单位时间必须进行一次操作，不能不操作。同时，他还发现宇宙的总个数不会超过 $m$ 个。 形式化地，他插入宇宙的概率为 $1-\dfrac{l}{m}$ ，删除宇宙的概率为 $\dfrac{l}{m}$ ，其中 $l$ 为当前宇宙的数量。显然地，一共有 $l+1$ 个位置可以插入宇宙，插入每个位置的概率相等；一共有 $l-1$ 个位置可以进行划分，每个位置进行划分的概率相等。 每当海地发现自己处于最左端或者最右端的宇宙时，他就会结束这些操作。他想知道，最后宇宙数量的期望值是多少？你只需要回答他对 $1e9+7$ 取模的结果即可。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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) $ .

输入输出样例

输入样例 #1

2 1 2

输出样例 #1

2

输入样例 #2

2 2 10

输出样例 #2

2

输入样例 #3

3 2 3

输出样例 #3

2

输入样例 #4

3 2 5

输出样例 #4

941659828

输入样例 #5

10 4 20

输出样例 #5

196683114

说明

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.