D. Array Counting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n,m$$$.

Count the number of different arrays $$$a$$$ of size $$$n$$$ satisfy:

  • All $$$a_i(1\leq i \leq n)$$$ are positive integers;

  • $$$\Sigma^{n}_{i=1}a_i=m$$$;

  • Take $$$a_1,a_2,...,a_n$$$ as the length of $$$n$$$ edges,the $$$n$$$ edges can form an $$$n$$$-sided shape.

Since the answer may be very large,output the answer modulo $$$10^9+7$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

The only line of each test case contains two integers $$$n,m(3 \leq n \leq m \leq 10^6)$$$.

Output

For each test case,output on a new line — the number of different arrays satisfy the conditions above (modulo $$$10^9+7$$$).

Example
Input
5
3 3
3 4
3 5
500000 1000000
900000 1000000
Output
1
0
3
998348142
469853029
Note

Test case $$$1$$$:

There's only one array $$$\{1,1,1\}$$$ satisfying the conditions above.

Test case $$$2$$$:

No array satisfies the conditions above.

Test case $$$3$$$:

There're $$$3$$$ arrays $$$\{1,2,2\},\{2,1,2\},\{2,2,1\}$$$ satisfying the conditions above.