Description

There are m classes in the Stars Kindergarten. And each class has exactly k children. Every day Ms. Lee is to distribute n different toys to the m classes and make sure that each class obtains no less than k toys. Otherwise a fight among the children may break out in the class due to the lack of toys. Ms. Lee wants to know how many ways there are for her to distribute the toys.

Input

There are multiple test cases.
The first line contains the number of test cases, T.
Each of the next T lines describes a test case which consists of three integers n, m, k (0 ≤ n, m, k ≤ 1000)

Output

For each test case output the answer modulo 9973 in a separate line. Output 0 if the distribution is impossible.

1
4 2 2

3

Hint

The classes are considered identical. So the 3 ways are {{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}

Source

POJ Founder Monthly Contest – 2008.06.29, Huang Jinsong