You are at the top left corner [position (1,1)] of a R×C grid. Your destination is bottom right corner of the the grid[position (R,C)].
A 3×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 RC (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.