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.


Added by:Francky
Date:2016-06-28
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:VECTAR1

hide comments
2016-10-08 21:22:34 :D
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;D-1> (D standing for W or H). Both problems are of course correctly described, but it's easy to miss.
2016-08-15 22:46:32 :D
Great Francky-styled problem. Math / computation - centric and very interesting to solve.

=(Francky)=> Congrats for #1 rank, and many thanks for your appreciation.

Last edit: 2016-08-20 12:21:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.