VECTAR1  Matrices with XOR property
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 calculatethe total number of matrices of size N x M which have both the properties
mentioned above.
Input format:
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 format:
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
SAMPLE OUTPUT
4
Explanation
The four possible matrices are:
[1 3]  [2 3]  [1 4]  [2 4]
[4 2]  [4 1]  [3 2]  [3 1]
hide comments
:D:
20161008 21:22:02
Please keep in mind that this problem and XORRAY have a significant difference outside of constraints. Array indexing in VECTAR1 is in range <1;D> and in XORARRAY <0;D1> (D standing for W or H). Both problems are of course correctly described, but it's easy to miss. 

Rishit Sanmukhani:
20160927 20:59:32
Good question! Last edit: 20160927 21:24:38 

rainy jain :
20160909 16:53:29
Getting TLE , expected complexity?

Added by:  Piyush Kumar 
Date:  20160619 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 