시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 1 1 50.000%

문제

Consider a regular polygon with $N$ vertices, where $N$ is odd. The vertices are numbered from $1$ to $N$ in circular order. We can select $M$ of these vertices to form a convex polygon on them. Master Zhu wants you to find how many of such possible convex polygons have exactly $K$ acute angles. As their number can be very large, find the answer modulo $10^{9} + 7$. Two polygons are considered different if the sets of numbers in their vertices differ.

입력

The first line of input contains one integer $T$, the number of test cases ($1 \le T \le 5 \cdot 10^4$).

Each test case is described by a single line containing three integers $N$, $M$, and $K$ ($3 \le N \le 10^6$, $3 \le M \le N$, $0 \le K \le M$, and $N$ is odd).

출력

For each test case, print the answer modulo $10^{9} + 7$ on a separate line.

예제 입력 1

1
5 4 2

예제 출력 1

5