Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.

Natsubi moves on this grid from $(1,1)$ to $(H,W)$. When he is at $(i,j)$, he can move to $(i+1,j)$ or $(i,j+1)$. He cannot move outside the grid.

For a given path, its zigzag degree is defined as follows.

• The number of cells on the path at which the path turns

Here, "the path turns" at a cell $(i, j)$ means that at least one of the following conditions holds.

• $(i-1,j),\ (i,j),\ (i,j+1)$ all exist, and the path passes through all of them.
• $(i,j-1),\ (i,j),\ (i+1,j)$ all exist, and the path passes through all of them.

Given $H,W$, find the zigzag degree of each of the $\displaystyle \binom{H+W-2}{H-1}$ possible paths, and report the sum of these values.

Since the answer can be very large, output it modulo $10^9+7$ (a prime).

Solve $T$ test cases.

Input

The input is given from standard input. The $1$st line of the input is as follows.

$T$

Then, $T$ test cases are given on the following $T$ lines. Each of them is in the following format.

$H\ W$

• All input values are integers.
• $1 \leq T \leq 10^5$
• $1 \leq H,W \leq 2 \times 10^5$

Output

For each test case, output the answer. Print a newline after each test case.

Sample

Sample 1

Input

4
2 3
1 10
1 1
200000 200000

Output

4
0
0
316943316

• For the $1$st case: the possible paths are the $3$ shown in the figure below. Their zigzag degrees are $1,2,1$ respectively, so the answer is $4$.
• For the $2$nd case: there is no way to turn in the first place.
• For the $3$rd case: he does not even move, but the answer is still $0$.
• For the $4$th case: do not forget to output the answer modulo $10^9+7$.