Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Distribution of Toys
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1199Accepted: 196

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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator