시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 (추가 시간 없음) 256 MB111100.000%

문제

An ordinary chain is a graph consisting of sequential (at least two) vertices. Every two adjacent vertices are connected by an edge. The $k$-th order Chiaki Chain looks slightly different from a chain. There are $k$ sub-chains of various lengths extended from $k$ different vertices on the main chain. At the other side of each sub-chain, there is a simple cycle of length $3, 4, \ldots, k + 2$ respectively. There is no useless vertices or edges on the $k$-th order Chiaki Chain.

Note that the main chain and the sub-chains should consist of at least two vertices.

The following image corresponds to the a $3$-rd order Chiaki Chain with $20$ vertices and $22$ edges:

Given $n$, $m$ and $k$, Chiaki would like to know the number of labelled $k$-th order Chiaki Chain with $n$ vertices and $m$ edges. Since this number may be very large, you are only asked to calculate it modulo $10^9+7$.

입력

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m, k \le 10^6$) --- the number of vertices and the number of edges in the graph and the order of Chiaki Chain.

출력

For each test case, output an integer denoting the answer.

예제 입력 1

4
1 1 1
3 3 1
4 4 1
5 5 1

예제 출력 1

0
0
0
60