Vivek has 2 identical grid of square boxes, The size of grid is N*M where N denotes the no. of rows and M.
Vivek likes even numbers a lot. So he wants to make a new grid from the blocks of the given grids which contains even no. of blocks . He called this type of grid a Even grid.
To make a Even grid, He can take out any box from the grids irrespective of their position in the grid. He believes in equality as well so he takes out equal no. of boxes from each grid.
Find the no. of ways in which he can select boxes to make a new grid. One way is different from other way if atleast one of the chosen box is different.
As the result could be very large, answer the result in 10 9 +7 modulo.
Input:
The first line contains a integer T which denotes the no. of testcases.
Next T lines contains 2 space separated integers N and M respectively.
Output:
For each test , output a integer in a new line denoting the answer for the test case.
Constraints:
1≤ T ≤ 106
1≤ a,b ≤ 106
1≤ a*b ≤ 106
In first test case, the no. of ways in which he can select boxes is only one i.e. He select the single box from both the grid.
In second test case, he can select boxes in following ways:
1. Select box (1,1) of grid 1 and box (1,1) of grid 2.
2. Select box (1,1) of grid 1 and box (1,2) of grid 2.
3. Select box (2,1) of grid 1 and box (1,1) of grid 2.
4. Select box (1,2) of grid 1 and box (1,2) of grid 2.
5. Select boxes (1,1) and (1,2) from grid 1 as well as grid 2.
All the participants need to register on the given link: Register Here
