Welcome to ZOJ
156 - ZOJ Monthly, January 2019 - H
Little Sub and Zuma

Time Limit: 6 Seconds      Memory Limit: 262144 KB

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,

  • When an energy ball is inserted, it can be inserted between any two adjacent energy balls or at one of the ends, each position has the possibility of $p = \frac{1}{L+1}$;
  • When the chain breaks, it could be cut between any two adjacent energy balls, each has the possibility of $p = \frac{1}{L-1}$. After breaking the chain into two segments, the segment NOT containing BaoBao will be discarded.

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.


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


For 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 Input

2 1 2
2 2 10
3 2 3
3 2 5
10 4 20

Sample Output



For 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.

Submit    Status