You have N dices; each of them has K faces, numbered from 1 to K. Now you can arrange the N dices in a line. If the summation of the top faces of the dices is S, you calculate the score as the multiplication of all the top faces.
Now you are given N, K, S; you have to calculate the summation of all the scores.
Input
Input starts with an integer T (≤ 25), denoting the number of test cases.
Each case contains three integers: N (1 ≤ N ≤ 1000) K (1 ≤ K ≤ 1000) S (0 ≤ S ≤ 15000).
Output
For each case print the case number and the result modulo 100000007 (108 + 7).
Sample
| Sample Input | Sample Output |
|---|---|
5 1 6 3 2 9 8 500 6 1000 800 800 10000 2 100 10 | Case 1: 3 Case 2: 84 Case 3: 74335590 Case 4: 33274428 Case 5: 165 |