connected-components-1

There are N marbles in a line, numbered 1 through N from left to right.  Count numbers of ways to remove exactly M marbles such that there are exactly C remaining connected components. A part [a,b] of sequence is called a connected component if for all a ≤ i ≤ b there is a marble at position i and also there are no marbles at positions a-1 and b+1 (either because those marbles have been removed or because they are out of range [1,N]).

Input

The first line contains T - the number of test cases. Then T test cases follow.

Each test consists of 1 line containing 3 positive integers N, M and C. 

Output

For each test, print the number of ways of removing marbles satisfying our condition. Since this number can be very large, you must print it modulo 10^9 + 7.

Constraints
1 ≤ T ≤ 100000
1 ≤ M ≤ N, 0 ≤ C ≤ N - M
1 ≤ N ≤ 100000
20% number of tests in which N ≤ 15.
30% number of tests in which T ≤ 100, N ≤ 200
20% number of tests in which N ≤ 1000

SAMPLE INPUT
3
3 1 2
3 2 1
5 2 3

SAMPLE OUTPUT
1
3
1

Source: hackerearth | Difficulty: HARD


Solutions: