One day，Alex is boring so he plays with dices，he has n dices and each of them has k faces numbered from 1 to k, You can rotate/flip any dice, Now he wants to know how many ways he can set the top faces such that the summation of all top faces equals S?

Input starts with an integer T(T <= 20) denoting the number of test cases;
Each of the test case contains three integers n, k and S(1 <= n <= 1000, 1 <= k <= 1000, 0 <= S <= 15000)

For each test case print the case number and the result modulo 100000007.