On a planet far far away from Earth, there is a crazy general in the army of Wonderland. Recently she has derived a new strategy of deploying her soldiers. She has learned that each soldier needs to watch another soldier’s back. She took the phrase literally and discovered that this can be only achieved by forming cycles, e.g. soldier A watches soldier B and B watches C and C watches A. She needs to deploy her n soldiers in two days. On the first day, she randomly selects k soldiers and deploys them by forming c1 cycles. On the next day, she deploys the remaining soldiers by forming c2 cycles. Each of these cycles must have at least r soldiers and she has to deploy at least r soldiers on each day.
The general needs to find the most efficient strategy to win the war, but first she wants to compute the number of ways to deploy her soldiers for all possible values of k, when the total number of cycles in two days’ deployment cannot be more than C, i.e. c1 + c2 ≤ C.
Input
The first line of input contains a single integer, T (T ≤ 105). Then T lines follow. Each of these T lines will contain 3 integers: n (1 ≤ n ≤ 1000), C (1 ≤ C ≤ 1000) and r (1 ≤ r ≤ 10).
Output
For each of the cases output Case <x>: <y> in a separate line, where x is the case number and y is the number of different possible deployments. As y can be quite large, output y modulo 1,000,000,007.
Sample
| Sample Input | Sample Output |
|---|---|
3 4 2 2 3 2 2 2 2 1 | Case 1: 6 Case 2: 0 Case 3: 2 |
Notes
Explanation of Sample I/O
1st case: As r = 2 and n = 4 and she needs to deploy at least r soldiers on both days, the only possible value of k is 2. Due to the same constraints, the only possible values of c1 and c2 are 1. Now, she can choose 2 soldiers for the 1st day in 6 ways and then there is only 1 way to make a cycle. For the 2nd day, we have to deploy the remaining soldiers and again we can make a cycle in only 1 way. Therefore, the total number of possible deployments is 6.
2nd Case: There are not enough soldiers to satisfy the constraints. Therefore, the total number of possible deployments is 0.
3rd Case: There are only 2 ways to deploy them. It is possible to make a cycle consisting of only 1 soldier.