分糖果

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

N 个完全相同的糖果,全部分给 M 个小朋友。若每个小朋友至多得到 P 个糖果,并且可以有小朋友不得到糖果,一共有多少种分发方案?

Input

 第一行一个整数T(1<= T<=10000),表示有T 组测试数据。每组测试数据占一行,依次是三个整数N,M,P(1<= N,M,P<=1000)。

Output

 对于每组测试数据输出一个整数,表示分发方案数除以1000000007 的余数。

Sample Input

3
2 1 1
2 1 2
5 2 3

Sample Output

0
1
2

Hint

 样例说明:

第一组样例中,2 个糖果分给1 个小朋友,只能分给他2 个糖果,但是P=1,因此无

可行方案。第二组样例P=2,因此有唯一方案。第三组样例方案为(2,3)和(3,2)。

Source