hannnnah_j is a teacher in WL High school who teaches biology.

One day, she wants to test m students, thus she arranges n different seats around a round table.

In order to prevent cheating, she thinks that there should be at least k empty seats between every two students.

hannnnah_j is poor at math, and she wants to know the sum of the solutions.So she turns to you for help.Can you help her? The answer maybe large, and you need to mod 1e9+7.

First line is an integer T(T≤1000).

The next T lines were given n, m, k, respectively.

0 < m < n < 1e6,  0 < k < 1000

For each test case the output is only one integer number ans in a line.

1张圆桌有n个不同的座位，你需要留出m个座位给学生安排座位。为了防止作弊，任意两个相邻学生坐的座位至少需要隔开k个空座位。

问：有几种不同的选择座位的方式？方案数可能很大，需要对1e9+7取模。

输入

第一行T(T <= 1000)，

以下有T行，每行为n, m, k三个数字。

0 < m < n < 1e6,  0 < k < 1000

输出

输出T行，每行一个答案。

样例输入

2

4 2 6

5 2 1

样例输出

0

5