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

문제

Mr. Panda loves counting polygons. One day, he drew a circle with the unit radius and set $n$ points on the circle such that these points divide the circle into $n$ arcs with equal length. He is wondering how many different convex polygons he could generate if he selects $m$ points from these $n$ points and connects every two adjacent selected points with a line segment.

Two polygons are different if and only if they are not congruent. Two selected points are adjacent if there exist no other selected points on the arc between them. To avoid huge output data, you are only asked the answer modulo $(10^9 + 7)$.

입력

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

The first line contains two integers $n$ and $m$ ($3 \leq m \leq n \leq 10^7$).

출력

For each test case, output the number of different polygons modulo $(10^9 + 7)$ in a single line.

예제 입력 1

4
3 3
4 3
5 3
7 4

예제 출력 1

1
0
1
3