VECTAR1 - Matrices with XOR property
Imagine A is a NxM matrix with two basic properties
- Each element in the matrix is distinct and lies in the range of 1<=A[i][j]<=(N*M)
- 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]
hide comments
:D:
2016-10-08 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;D-1> (D standing for W or H). Both problems are of course correctly described, but it's easy to miss. |
|
Rishit Sanmukhani:
2016-09-27 20:59:32
Good question! Last edit: 2016-09-27 21:24:38 |
|
rainy jain :
2016-09-09 16:53:29
Getting TLE , expected complexity?
|
Added by: | Piyush Kumar |
Date: | 2016-06-19 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |