
ZOJ Problem Set  4088
Recently, Little Sub is obsessed with a game called Zuma. In this game, players have a chain of $N$ energy balls, in which a demon called BaoBao lives. Initially, BaoBao stays in the $K$th upmost ball. Due to the restriction of gravity, the length of a chain could not exceed $M$.At each time unit, one of the two events will happen randomly. Let's denote $L$ as the length of the chain currently. With a possibility of $p_{insert}=1\frac{L}{M}$, a ball will be inserted into the chain; With a possibility of $p_{break} = \frac{L}{M}$, the chain will be broken at a position. More specifically,
Normally, BaoBao will never change its place. However, whenever BaoBao stays in the first ball or the last ball of the chain, it will escape from the chain and leak some energy. The amount of energy leakage is equal to the length of the chain when BaoBao escapes. Given $N$, $K$, and $M$, please calculate the expected amount of energy leakage. InputThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 1000$), indicating the number of test cases. For each test case: The first and only line contains three integers $N$, $K$ and $M$ ($1 \le K \le N \le M \le 250$). It's guaranteed that at most 10 test cases have $M \gt 20$. OutputFor each test case, output a single integer on a single line, indicating the expected amount of energy leakage. If the answer is $\frac{A}{B}$, please print $C(0\leq C<10^9+7)$ where $A\equiv C\times B\pmod{10^9+7}$. Sample Input5 2 1 2 2 2 10 3 2 3 3 2 5 10 4 20 Sample Output2 2 2 941659828 196683114 HintFor the first and the second test case, without any change to the chain, the demon will escape immediately. For the third test case, the chain can only break at a position, which renders the demon escape then. For the fourth case, things seem to be a little more complicated, because the chain can be longer and then be broken again. Author: WANG, Yuhan; CHEN, Songyang Source: ZOJ Monthly, January 2019 