XORRAY  2D arrays with XOR property
We consider 2D arrays $A$, (0,0)indexed, shape $N \times M$.
With $ 0 \le i < N $ and $ 0 \le j < M $, we have $ 0< A_{i,j} \le N \times M $.
Our interest will be to count those arrays that have the two properties :
 Arrays $A$ are composed with all numbers from $1$ to $N \times M$.
i.e. we have $ (i,j) \neq (k,l) \implies A_{i,j} \neq A_{k,l} $  $(i\oplus j) > (k\oplus l) \implies A_{i,j} > A_{k,l} $, where $ \oplus $ denotes bitwise XOR.
Input
The first line contains $T$, the number of test cases, and $P$ a prime number.
Each of the next $T$ lines contains $N$ and $M$, the shape of the arrays $A$.
Output
For each test case, print the number of arrays $A$ with the given properties.
As the result may be large, the answer modulo $P$ is required.
Example
Input: 2 1000000007 2 2 997 799 Output: 4 828630475
For the first case, the 4 possible 2x2 arrays are : $ \binom{1\; 3}{4\; 2}$, $\binom{1\; 4}{3\; 2}$, $\binom{2\; 3}{4\; 1}$, and $\binom{2\; 4}{3\; 1}$.
Constraints
$1 \le T \le 10^4$,
$10^9 < P < 2\times 10^9$, a prime number,
$1 \le N \le 10^9$,
$1 \le M \le 10^5$.
Constraints allow a small kB of unoptimized PY3.4 code to get AC in the third of the TL. Have fun.
hide comments
:D:
20161008 21:22:34
Please keep in mind that this problem and VECTAR1 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. 

:D:
20160815 22:46:32
Great Franckystyled problem. Math / computation  centric and very interesting to solve.

Added by:  Francky 
Date:  20160628 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  VECTAR1 