Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a N×M grid? As answer can be very large, print it modulo 10^9+7.

Input Format:-
The first line contains an integer T , i.e., number of test cases. Next T lines will contain integers N and M.

Output Format:-
Print the values corresponding to each test case.

Constraints:-

1 <= T <= 10^3
1 <= N <= 500
1 <= M <= 500