You are given a grid of size \(N \times M\). You are at cell (1,1) and you want to go to the cell (N,M). In each step from each cell you can either move right or down. How many different paths exist ?
Two paths are different if at a given step the two paths lead to different cells.
The first line of the input contains one integer \(T\) the number of test cases (\( 1 \leq T \leq 1000\)).
Each test case consists of a line with two integers \(N\) and \(M\) (\( 1 \leq N,M \leq 1000\)).
For each test case output one line containing the number of different paths to go from the top left to bottom right.
As this number can be very big, print it modulo \(1000000007\).
3 2 3 1 5 3 3
3 1 6