Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Distribution of Toys
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1237 Accepted: 202

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.

Sample Input

```1
4 2 2
```

Sample Output

```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

[Submit]   [Go Back]   [Status]   [Discuss]