A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"

MATHE  
ATHEM  
THEMA  
HEMAT  
EMATI  
MATIC  
ATICS

There are many ways to trace this matrix in a way that helps you construct this word. You start tracing the matrix from the top-left position and at each iteration, you either move RIGHT or DOWN, and ultimately reach the bottom-right of the matrix. It is assured that any such tracing generates the same word. How many such tracings can be possible for a given word of length \(m+n-1\) written as a matrix of size \(m \times n\)?

Input

The first line of input contains an integer \(T \space (1 \le T \le 10^3)\) — the number of test cases. Next \(T\) test cases follow.
Each test case contains 2 space separated integers \(m, n \space (1 \le m,n \le 10^6)\) (in a new line) indicating that the matrix has \(m\) rows and each row has \(n\) characters.

Output

Print the number of ways (S) the word can be traced as explained in the problem statement. If the number is larger than \(10^9+7\).
print \(S \space mod \space (10^9 + 7)\) for each testcase (in a new line).

Example

<center>standard input</center>	<center>standard output</center>
1 <br />2 3	3

Note

Let's consider a word AWAY written as the matrix.

AWA
WAY

Here, the word AWAY can be traced in 3 different ways, traversing either RIGHT or DOWN.

AWA
  Y

AW
 AY

A
WAY

Hence the answer is 3.