Dice (II)

Medium Hard

LOJ-1193

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 (10⁸ + 7).

Sample

Sample Input	Sample Output
Click to copy 5 1 6 3 2 9 8 500 6 1000 800 800 10000 2 100 10	Click to copy Case 1: 3 Case 2: 84 Case 3: 74335590 Case 4: 33274428 Case 5: 165

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
// Reads two integers and prints their sum
void basicIO() {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
}
​
int main() {
    // basicIO();
    // Your cpp code here
    return 0;
}
​

Input

Output

Sample

Total Submissions

Users Tried

Users Solved