Link with Balls

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.

Sample Input

4

1 1

2 2

3 3

1000000 1000000

Sample Output

2

6

20

192151600

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（7）