A rat is located at the top-left cell of a m*n matrix. The rat wants to get to the cheese which is at the bottom-right cell of the matrix.

The rat can move only in one of the two directions - down and right. How many unique paths can the rat take to reach the destination?

Examples

m:3, n:2
paths: 3

Explanation:
[[Down, Down, Right], [Down, Right, Down], [Right, Down, Down]]

The total number of unique paths can be larger than the largest 32 bit number. Return your answer with module 10⁹ + 7.

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case the input has two integers m and n.

Output Format 

For each test case, a line containing an integer denoting the number of unique paths. Return the answer with module 10⁹ + 7.

Sample Input

4
3 2
2 3
3 3
2 2

Expected output

3
3
6
2

Constraints

1 <= T <= 100
1 <= n, m <= 100