Alice is obsessed with chocolate cookies but her mother does not like her habit of eating chocolate cookies. So. Alice's mother restricted her to eat at most N cookies per day and the cookie she ate on the (i + 1)th day should be not more than cookies she ate on the day. Alice wants to eat at least k cookies per day. After listening to her mothers restriction, your task is to determine the number of ways in which Alice can eat the cookies. As the number of ways can be very large, print the output modulo 10 + 7.

Input format

• The first line contains T denoting the number of test cases.

• Each line of a test case contains 3 space-separated integers number N, K, and M. (where M is the number of days)

Output

Print the number of possible ways to eat cookies modulo 10^9 + 7.

Constraints

1 < T < 10^6

1 < N < 10^6

1 < k < N

M < 10^6

Sample input:

2

5 2 2

7 3 3

Output:

10

35