← 返回题目列表

Codeforces · 1184/D2

D2. 平行宇宙(难)

中文机器翻译题面 查看原题

海蒂喜欢进行模拟,因为她确切地知道新宇宙何时、何地形成,以及一个不存在的链接何时何地被打破。

然而,多元宇宙本身以神秘的方式运作。嗯,它是利用概率来运作的,这对某些人来说是神秘的。

在每个单位时间,当做出决定时,两个事件之一将随机发生。让我们将 $$$l$$$ 表示为多重宇宙的当前长度。以 $$$p_{create} = 1 - \frac{l}{m}$$$ 的概率,将创建一个宇宙。不存在的链接将在某个位置被破坏,概率为 $$$p_{break}=\frac{l}{m}$$$。

更具体地说,

- 当一个宇宙被创建时,它会在任何两个相邻的宇宙之间或一端出现。每个位置出现的概率为 $$$\frac{1}{l + 1}$$$。
- 当链接被破坏时,它可以在任意两个相邻宇宙之间被切断,每个宇宙的概率为 $$$\frac{1}{l-1}$$$。将多元宇宙分成两部分后,不包含博士的部分将不复存在。

和之前一样,博士仍然在同一个宇宙中。然而,如果在某个时刻多元宇宙以某种方式破裂,以至于博士发现自己处于它的最左端或最右端,TARDIS 就会停止运行。

在这种情况下,博士实际上必须穿越多元宇宙来寻找修复它的工具。

我们感兴趣的是当此类事件发生时多元宇宙长度的预期值。

输入

第一行也是唯一一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ $$$(1 \le k \le n \le m \le 250)$$$、多元宇宙的初始长度、Doctor 的初始位置以及多元宇宙的最大可能长度。

输出

在一行上输出一个整数,表示多重宇宙的预期长度。

如果答案是 $$$\frac{p}{q}$$$,请打印 $$$r$$$,其中 $$$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

注意

对于第一个和第二个测试用例,在多元宇宙没有任何变化的情况下,博士已经位于其中一个末端。

对于第三个测试用例,多元宇宙只能在一个位置破裂,这使得Doctor处于其一端。

对于第四种情况,事情似乎有点复杂,因为多元宇宙可以增长,然后再次破碎。