How Many Paths?

EWU Team Programming Batt...
Limits 1s, 512 MB

You are at the top left corner [position $(1,1)$] of a $R \times C$ grid. Your destination is bottom right corner of the the grid[position $(R, C)$].

A $3 \times 8$ grid. Yellow is the starting position. Green is the ending position. Red line shows a valid path.

If your current position is $(x,y)$, you can move to $(x+1,y)$ or $(x,y+1)$ [if it is a valid position]. How many valid unique paths are there from your initial position to destination.

Input

Input starts with an integer $T$ ($≤ 1000$), denoting the number of test cases.

Each case starts with a line containing two integers $R$ $C$ ($1 ≤ R, C ≤ 10000$), where $R$ denotes the number of rows and $C$ denotes the number of columns of the grid.

Output

For each test case output number of unique path modulo $1000000000+7$.

Sample

InputOutput
1
2 2
2