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 109 + 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
