Imagine A is a NxM matrix with two basic properties

1. Each element in the matrix is distinct and lies in the range of 1<=A[i][j]<=(N*M)
2. For any two cells of the matrix, (i1,j1) and (i2,j2), if (i1^j1) > (i2^j2) then A[i1][j1] > A[i2][j2], where

1 ≤ i1, i2 ≤ N

1 ≤ j1, j2 ≤ M.

^ is bitwise XOR

Given N and M, you have to calculate the total number of matrices of size N x M which have both the properties mentioned above.  

Input

First line contains T, the number of test cases. 2*T lines follow with N on the first line and M on the second, representing the number of rows and columns respectively.

Output

Output the total number of such matrices of size N x M. Since, this answer can be large, output it modulo 10^9+7

Constraints

1 ≤ N, M, T ≤ 1000

Sample

Input
1
2
2

Output
4

Explanation

The four possible matrices are:

[1 3] | [2 3] | [1 4] | [2 4]

[4 2] | [4 1] | [3 2] | [3 1]