Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

How Many Paths?

By Kryptonyte · Limits 1s, 512 MB

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

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

Discussion

Statistics


59% Solution Ratio

EWU_DeadLocKEarliest, Jun '16

hamza05Fastest, 0.0s

rubbyELightest, 262 kB

Mohammad_SohagShortest, 674B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.