SP27301 XORRAY - 2D arrays with XOR property

我们研究一种二维数组 $A$，它从 $(0, 0)$ 开始索引，大小为 $N \times M$。对于任意 $0 \le i < N$ 和 $0 \le j < M$，满足 $0 < A_{i,j} \le N \times M$。我们的目标是计算这样类型的数组有多少种可能，数组需要符合以下两个条件： 1. 数组 $A$ 必须包含从 $1$ 到 $N \times M$ 的所有数字。换言之，若 $(i, j) \neq (k, l)$，那么 $A_{i,j}$ 必须不同于 $A_{k,l}$。 2. 对于任何两个元素，若 $(i \oplus j) > (k \oplus l)$，则必须有 $A_{i,j} > A_{k,l}$，其中 $\oplus$ 表示按位异或运算。

第一行输入测试用例的数量 $T$，以及一个质数 $P$。 接下来的 $T$ 行中，每行包含两个整数 $N$ 和 $M$，表示数组 $A$ 的大小。

对于每个测试用例，输出满足条件的数组 $A$ 的数量。由于结果可能非常大，请输出结果对 $P$ 取模后的值。

- 测试用例数 $T \ge 1$ - $P$ 是一个质数 - $1 \le N, M \le 10^5$ **本翻译由 AI 自动生成**