8986: LightOJ - Dice (II)
[Creator : ]
Description
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.
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)$.
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 $10^8 + 7$.
Sample 1 Input
5
1 6 3
2 9 8
500 6 1000
800 800 10000
2 100 10
Sample 1 Output
Case 1: 3
Case 2: 84
Case 3: 74335590
Case 4: 33274428
Case 5: 165