How Many Paths?

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 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.


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


2 2