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

Here is the Problem Statement:

Given array A of N Integers a1 ,a2, a3...... aN . You are also given two integers S and M. You can pick subarray of size S where you have to perform M operation by incrementing the value of each element value by 1. Find the maximum value of minimum value in array A.

Example

Input:

N = 6 ,M = 5 ,S =2

1 2 3 4 5 6

Output:

4

Explaination:

1st opertaion subarray index range (0,1) 2 3 3 4 5 6

2nd opertaion subarray index range (0,1) 3 4 3 4 5 6

3rd opertaion subarray index range (0,1) 4 5 3 4 5 6

4th opertaion subarray index range (2,3) 4 5 4 5 5 6

5th opertaion subarray index range (0,1) 5 6 4 5 5 6

PS: what level problem do you think this will be classified as for a Div.2 round?

I am not very good when it comes to DP. Do you have any problem which you think helped your understanding of approaching/solving DP problems. Please share it in the comments.

Problem Statement Two players are playing a game. They have A bundles of pencils of size B each.

They also have a number C that they chose randomly. They move in turns and the person who's unable to make a move loses.

For each move a person chooses a bundle and divides it into some number (more than one) of equal parts/bundles, the size of each one is expressed by an integer and is no less than C.

Each resulting part is also a bundle which can be divided in future by any player.

Find the winner of the game.

Problem Constraints 1 <= A <= 105

1 <= B, C <= 109

Input Format First argument is the integer A.

Second argument is the integer B.

Third argument is the integer C.

Output Format Return 1 of the First player wins, 0 if Second player wins.

Example Input Input 1:

A = 4 B = 8 C = 6 Input 2:

A = 1 B = 9 C = 2

Example Output Output 1:

0 Output 2:

1

Example Explanation Explanation 1:

Player 1 cannot divide any of the bundle, so that the divided bundles have size not less than 6. Hence he loses. Explanation 2:

They have only 1 bundle to start with. Player 1 has only one valid move where he divides this bundle into 3 bundles of size 3. After this Player 2 cannot divide bundles of size 3 further. Hence Player 2 loses.

Intuition

if A is even, player2 wins because player2 can mimic player1's move. But what if A is odd?