VECTAR1 - Matrices with XOR property

no tags 

 

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.
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]

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: 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