Problem Description

There were a lot of balls in the factory of Ball Illusion Technology(BIT). Link, a boy, went there to get some balls, but suddenly, he found that there were too many ways to get balls.

There are $2n$ buckets in the factory. Link may get $kx$ balls from the $2x-1^{th}$ bucket, where $k$ is a non-negtive integer. He may also get at most $x$ balls from the $2x^{th}$ bucket.

Link wanted to get $m$ balls, and he wondered how many ways there were to take out exactly $m$ balls. While Link is calculating the answer, he wants you to calculate it as well, and you should output the answer modulo $10^9+7$.

Input

The input consists of multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 10^5$) -- the number of test cases.

Each test case contains two integers $n$ and $m$($1 \leq n,m \leq 10^6$).

Output

For each test case, print the answer modulo $10^9+7$ in a single line.

4
1 1
2 2
3 3
1000000 1000000

2
6
20
192151600