Limits 1s, 512 MB

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

A 3×83 \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)(x,y), you can move to (x+1,y)(x+1,y) or (x,y+1)(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 TT (1000≤ 1000), denoting the number of test cases.

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

Output

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

Sample

InputOutput
1
2 2
2

Submit

Login to submit.

Statistics

64% Solution Ratio
EWU_DeadLocKEarliest, Jun '16
MatrixFastest, 0.0s
rubbyELightest, 262 kB
shamimahmed822Shortest, 571B
Toph uses cookies. By continuing you agree to our Cookie Policy.