## XORRAY - 2D arrays with XOR property

no tags

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: 2016-10-08 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;D-1> (D standing for W or H). Both problems are of course correctly described, but it's easy to miss. :D: 2016-08-15 22:46:32 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

 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