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.

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.

Sample Input

5
1 6 3
2 9 8
500 6 1000
800 800 10000
2 100 10

Sample Output

Case 1: 3
Case 2: 84
Case 3: 74335590
Case 4: 33274428
Case 5: 165

HINT

Source

NBU