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 ⁹ +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 ≤ 10⁶
1≤ a,b ≤ 10⁶
1≤ a*b ≤ 10⁶