海蒂喜欢进行模拟,因为她确切地知道新宇宙何时、何地形成,以及一个不存在的链接何时何地被打破。
然而,多元宇宙本身以神秘的方式运作。嗯,它是利用概率来运作的,这对某些人来说是神秘的。
在每个单位时间,当做出决定时,两个事件之一将随机发生。让我们将 $$$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处于其一端。
对于第四种情况,事情似乎有点复杂,因为多元宇宙可以增长,然后再次破碎。