题目描述
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
输入格式
见题面
输出格式
见题面
样例输入
680
15 1 0
15 5 9
15 6 6
15 6 2
10 2 0
14 5 9
15 2 3
12 4 3
15 12 0
15 12 2
15 1 11
9 1 8
14 1 13
9 5 4
4 1 3
15 6 3
14 3 3
15 1 5
14 1 8
15 4 4
14 5 5
15 9 0
14 8 1
15 7 5
11 7 2
12 7 2
13 7 6
13 1 10
13 5 5
10 8 2
9 2 6
3 2 1
9 6 2
14 4 9
13 9 1
15 3 10
14 2 9
14 12 2
14 4 8
8 3 2
11 6 4
12 4 4
9 5 3
14 6 7
12 2 3
15 4 5
11 2 5
13 8 1
15 5 6
12 6 5
13 11 2
10 4 2
13 2 2
10 7 3
9 4 5
15 13 2
9 2 2
12 2 6
14 4 10
13 8 3
14 8 6
11 4 2
13 3 5
11 4 4
15 7 1
12 5 3
14 2 4
4 1 0
15 1 10
12 3 0
12 6 0
7 2 1
7 4 0
12 5 4
9 3 2
8 3 3
8 1 4
12 7 0
8 1 6
3 3 0
12 1 6
11 2 7
15 8 1
2 1 1
6 4 0
15 4 0
14 4 0
7 4 2
15 5 0
12 1 10
8 6 1
13 6 7
11 11 0
13 3 6
15 1 8
7 1 4
9 2 1
12 8 3
9 1 4
12 6 2
10 4 4
15 2 0
15 2 11
14 3 9
5 4 1
15 4 9
7 3 4
10 3 4
14 2 0
10 1 4
15 9 2
12 10 1
10 2 3
12 1 3
14 3 8
9 4 3
11 8 0
11 8 3
9 2 0
14 11 0
14 3 6
15 11 0
13 9 2
15 4 10
6 4 2
14 5 6
10 2 6
10 8 1
5 1 1
14 6 8
12 2 7
10 5 1
7 5 0
10 7 0
15 3 1
13 3 0
11 8 2
15 3 5
10 9 1
7 6 0
15 10 2
12 3 3
5 4 0
7 2 3
13 5 7
8 4 4
15 4 6
13 3 9
10 4 0
10 1 2
12 7 5
12 4 5
7 1 2
15 1 1
13 8 2
14 7 4
7 7 0
13 5 1
14 1 6
12 10 0
13 5 6
12 3 9
8 2 0
7 1 5
13 3 2
15 8 7
12 1 11
4 4 0
13 1 6
13 7 3
15 3 7
12 1 4
7 1 3
9 4 2
14 4 6
7 5 1
12 5 7
12 2 2
14 2 7
10 7 1
9 1 7
13 7 0
15 3 11
8 5 2
12 2 5
13 2 10
14 8 3
11 1 1
5 3 1
14 11 1
14 5 8
14 1 7
12 9 3
12 8 0
10 6 4
11 1 0
13 11 1
14 9 0
15 14 0
13 3 3
15 2 9
12 3 4
15 1 4
8 8 0
13 4 8
13 5 3
12 3 7
13 4 1
13 12 1
14 7 7
15 3 0
13 3 1
13 1 1
12 11 1
15 2 13
11 3 0
10 1 3
13 5 8
13 3 8
6 2 4
15 5 10
11 1 9
13 13 0
13 1 7
11 3 3
15 7 3
1 1 0
14 1 3
10 3 3
11 3 4
7 3 2
13 1 3
11 4 3
9 5 2
13 6 5
14 2 11
15 6 1
12 8 2
3 1 1
8 6 0
9 3 5
12 6 3
13 10 1
8 1 0
13 11 0
11 1 7
9 8 0
14 4 5
12 1 2
14 3 5
11 9 2
5 5 0
15 8 4
14 2 12
10 1 8
15 4 2
11 9 0
10 5 0
12 6 4
13 6 0
11 3 2
15 14 1
7 5 2
8 4 2
14 12 0
8 2 4
14 5 3
12 3 8
14 9 4
14 8 0
9 2 4
15 3 12
15 6 5
15 4 1
7 2 2
5 1 3
15 12 1
13 4 5
12 5 6
10 3 7
13 5 2
15 7 8
6 1 3
10 2 5
12 3 5
6 6 0
12 9 1
15 6 8
9 7 0
14 10 3
13 2 5
12 3 2
14 7 0
15 7 4
10 6 2
12 1 5
5 2 0
9 1 6
9 6 0
14 1 1
15 2 6
11 7 0
8 6 2
14 8 4
14 9 2
14 1 11
14 5 7
13 1 9
15 5 8
9 1 1
13 5 4
5 1 2
8 7 1
11 3 7
13 5 0
14 3 0
7 3 0
7 2 5
14 7 2
2 1 0
11 9 1
15 11 2
8 1 7
12 4 6
15 6 7
15 2 12
11 4 0
6 1 2
11 2 4
13 2 9
4 2 2
14 10 1
13 1 0
15 8 6
8 3 4
13 3 4
13 10 0
8 2 5
15 2 5
9 2 5
6 1 4
14 1 12
9 8 1
15 9 1
11 3 5
10 3 5
6 3 1
14 5 0
11 7 3
13 10 3
12 4 1
11 6 5
12 7 3
12 9 2
14 13 1
14 3 1
4 2 1
6 1 0
11 1 8
7 2 0
11 5 6
12 3 6
13 2 6
15 6 4
15 11 1
13 7 1
14 2 8
14 4 4
7 3 1
14 1 2
13 9 3
15 10 1
12 2 10
13 4 9
14 5 1
11 4 1
10 10 0
9 1 2
15 4 7
10 2 1
11 4 7
8 2 2
8 2 1
7 1 1
14 4 1
15 10 0
15 1 9
15 13 1
13 8 4
14 3 11
10 5 5
13 8 5
13 4 7
6 2 2
8 4 1
15 13 0
12 5 2
15 3 6
11 6 1
11 10 0
15 3 4
15 7 0
15 9 4
14 2 5
15 8 5
10 3 6
8 2 6
7 3 3
14 1 10
12 5 0
9 4 1
10 5 4
14 6 6
11 6 3
15 2 2
15 5 3
5 1 0
11 3 1
15 5 7
14 8 2
12 1 9
10 1 1
13 2 4
14 6 0
10 3 0
12 1 8
12 5 5
10 6 1
13 2 0
15 10 4
12 6 1
11 2 8
15 7 2
10 6 0
15 11 3
13 6 4
6 3 2
3 1 2
13 1 11
6 2 3
10 2 8
14 4 7
12 8 4
11 3 8
6 1 5
14 1 0
11 5 4
7 4 1
14 6 4
15 11 4
9 6 1
13 6 1
11 6 2
8 5 1
9 1 5
10 5 2
9 4 4
10 6 3
7 1 0
13 6 2
8 4 0
6 2 1
10 4 5
15 1 2
10 1 0
15 3 3
11 1 3
15 1 3
15 1 7
9 5 1
10 2 7
12 2 9
9 1 0
9 1 3
6 5 1
12 3 1
15 8 3
4 2 0
9 9 0
13 2 3
15 6 9
14 10 0
15 1 6
5 3 2
12 5 1
8 2 3
14 3 2
11 3 6
10 4 3
9 6 3
5 2 3
8 1 2
11 2 0
9 7 2
11 6 0
9 3 6
7 4 3
15 9 5
12 12 0
10 3 1
3 2 0
14 2 1
13 2 8
15 5 4
13 6 3
12 1 0
10 1 9
11 1 10
14 6 3
11 7 4
7 6 1
12 4 8
13 3 10
10 4 6
12 6 6
13 10 2
8 3 1
11 4 6
5 3 0
5 2 2
9 3 4
15 2 1
6 4 1
15 5 1
14 2 2
14 12 1
11 8 1
13 9 4
15 2 7
12 2 8
9 7 1
4 3 1
15 3 8
12 2 0
14 13 0
15 8 0
15 4 8
14 2 3
14 6 1
14 7 5
13 3 7
13 2 11
12 11 0
11 1 2
9 4 0
14 7 6
10 2 4
15 5 5
11 5 5
15 1 12
15 1 14
13 12 0
13 8 0
14 11 3
14 11 2
13 1 8
15 12 3
12 2 4
11 2 6
11 10 1
14 5 2
5 2 1
14 5 4
15 15 0
15 7 7
8 1 1
10 7 2
8 7 0
11 1 6
15 7 6
11 5 2
2 2 0
10 3 2
7 1 6
11 1 5
15 10 3
10 9 0
13 4 2
14 9 3
15 3 9
8 1 5
8 1 3
13 4 0
4 3 0
7 2 4
9 3 1
10 1 6
14 1 5
14 7 1
15 3 2
14 10 4
14 3 7
15 6 0
9 2 7
4 1 1
6 2 0
9 2 3
15 1 13
11 2 3
12 10 2
15 4 11
13 7 2
13 4 4
11 5 1
14 4 2
15 4 3
6 1 1
4 1 2
10 1 5
13 6 6
14 9 1
14 14 0
8 4 3
10 2 2
14 3 4
8 3 0
14 10 2
12 7 1
13 1 12
14 1 4
12 4 2
15 8 2
14 3 10
6 3 3
10 1 7
8 5 0
15 5 2
3 1 0
13 1 5
15 2 10
10 4 1
12 4 0
13 7 4
12 1 7
10 5 3
14 2 10
15 2 4
13 2 1
11 7 1
12 2 1
14 4 3
12 7 4
11 2 9
10 8 0
6 3 0
14 8 5
13 4 6
13 1 2
15 9 3
8 3 5
15 2 8
15 9 6
14 6 5
14 6 2
13 2 7
6 5 0
11 2 2
11 4 5
12 4 7
12 8 1
9 3 0
5 1 4
12 9 0
11 1 4
13 9 0
8 5 3
14 9 5
14 2 6
13 1 4
14 7 3
9 3 3
9 5 0
11 5 0
13 4 3
11 2 1
14 1 9
15 10 5
13 7 5
12 1 1
11 5 3
样例输出
116160824
399540857
745099317
0
738695757
0
0
670334286
826747560
456996821
329653637
0
0
399634725
457097938
91368977
611591038
61029356
519018131
511623737
568824631
288611286
770144651
75469921
749790307
897894641
553841723
830817987
0
0
670246128
333508943
585037157
637610705
141206276
884981127
275725725
912454535
0
567221425
744159738
79422948
0
0
197794645
0
931750954
99513127
0
0