Let’s define Sum = x[1]+x[2]+……+x[N]. x[i] is a positive number.
For each i, and you can select a number from 1 ~ K (K is a given positive integer) for x[i] as you like. Now give you a number S. you can select numbers for each x[i], and if Sum = S, you will get the money $P = x[1] *x[2]*…..*x[N], otherwise you will get nothing. After each selection, you will pay $1 for selection. And you won’t select the same array more than once. We assume that two selections x and y (we denote x[i] and y[i] are elements of the two arrays) are equal that for each integer range from 1 to N that x[i] = y[i]. Now you want to get the money as much as possible .And how much money that you’ll obtain. For example, when S = 3, N = 2,K = 2 you can let x[1] = 1, x[2] = 2 or x[1] = 2, x[2] = 1, you will get money $(1*2+2*1) = 4, and you will pay money $2 for two selections. Finally, you will get money $2.

Input starts with an integer T (T≤10), denoting the number of test cases.

Each test case will contain three integer N(1<= N <= 800), K(1<= K <= 2500), S(0<= S <= 15000) 

For each case print the case number and the result modulo 10000007.

64位整数请用long long，输入输出请用%lld