[SDOI2016] 储能表

有一个 $n$ 行 $m$ 列的表格，**行从 $0$ 到 $n-1$ 编号，列从 $0$ 到 $m-1$ 编号**。每个格子都储存着能量。最初，第 $i$ 行第 $j$ 列的格子储存着 $(i \oplus j)$ 点能量（$\oplus$ 表示**按位异或**）。所以，整个表格储存的总能量是 $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} i \oplus j$$ 随着时间的推移，格子中的能量会渐渐减少。每经过一个时间单位，每个格子中的能量都会减少 $1$。显然，**一个格子的能量减少到 $0$ 之后就不会再减少了。** 也就是说，$k$ 个时间单位后，整个表格储存的总能量是 $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max((i \oplus j)-k,0)$$ 给出一个表格，求 $k$ 个时间单位后它储存的总能量。 由于总能量可能较大，输出时对 $p$ 取模。

第一行一个整数 $T$，表示数据组数。接下来 $T$ 行，每行四个整数 $n,m,k,p$。

共 $T$ 行，每行一个数，表示总能量对 $p$ 取模后的结果。

3
2 2 0 100
3 3 0 100
3 3 1 100

2
12
6

对于 $100\%$ 的数据，保证 $1\le T\le 5000$，$1\le p\le 10^9$，$1\le n,m,k\le 10^{18}$。 | 测试点编号 | $T=$ | $n\le$ | $m\le$ | $k\le$ | $p\le$ | | :--: | :--: | :--: | :--: | :--: | :--: | | $1,2$ | $5000$ | $100$ | $100$ | $100$ | $10^9$ | | $3$ | $5000$ | $10^{18}$ | $10^{18}$ | $0$ | $10^9$ | | $4$ | $5000$ | $10^{18}$ | $10^{18}$ | $1$ | $10^9$ | | $5$ | $5000$ | $10$ | $10^{18}$ | $10$ | $10^9$ | | $6$ | $1$ | $10^5$ | $10^{18}$ | $10^5$ | $10^9$ | | $7$ | $1$ | $10^{18}$ | $10^{18}$ | $10^{18}$ | $10^9$ | | $8$ | $100$ | $10^{18}$ | $10^{18}$ | $10^{18}$ | $10^9$ | | $9,10$ | $5000$ | $10^{18}$ | $10^{18}$ | $10^{18}$ | $10^9$ | $\texttt{Statement fixed by Starrykiller.}$