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

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

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.