A word from the English dictionary is taken and arranged as a matrix. e.g. "MATHEMATICS"
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 * n?
The first line of input contains an integer T. T test cases follow.
Each test case contains 2 space separated integers m & n (in a new line) indicating that the matrix has m rows and each row has n characters.
1 <= T <= 103
1 ≤ m,n ≤ 106
Print the number of ways (S) the word can be traced as explained in the problem statement.
If the number is larger than 109+7,
print S mod (10^9 + 7) for each testcase (in a new line).
Let's consider a word AWAY written as the matrix
Here, the word AWAY can be traced in 3 different ways, traversing either RIGHT or DOWN.
Hence the answer is 3.
Time limit for this challenge is given here