Server Time: Mon Jul 6, 2020 12:28 am
Welcome ( logout
1193 - Dice (II)
  PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 32 MB

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

Output for Sample Input

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

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan