Counting Polygons

Time limit2sMemory limit256 MB

Summary

Count the convex polygons with m vertices chosen from n equally spaced points on a circle, up to congruence, modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Number theory, Math
Solved: No attempts yet

Problem

Mr. Panda loves counting polygons. One day, he drew a circle with unit radius and placed $n$ points on it so that they split the circle into $n$ arcs of equal length. He wonders how many different convex polygons he can form by selecting $m$ of these $n$ points and connecting 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 no other selected point lies on the arc between them. To keep the output small, print the answer modulo $(10^9 + 7)$ .

Input

There are multiple test cases. The first line contains an integer $T$ ( $1 \le T \le 10^4$ ), the number of test cases. Each test case has one line with two integers $n$ and $m$ ( $3 \leq m \leq n \leq 10^7$ ).

Output

For each test case, print the number of different polygons modulo $(10^9 + 7)$ on its own line.

Examples1

Example 1
Input
```
4
3 3
4 3
5 3
7 4
```
Expected output
```
1
0
1
3
```