P4067 [SDOI2016] Energy Storage Table

There is a table with $n$ rows and $m$ columns, with rows numbered from $0$ to $n-1$ and columns numbered from $0$ to $m-1$. Each cell stores energy. Initially, the cell in row $i$ and column $j$ stores $(i \oplus j)$ units of energy (where $\oplus$ denotes bitwise XOR). Therefore, the total energy stored in the whole table is $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} i \oplus j.$$ As time passes, the energy in the cells gradually decreases. After each unit of time, the energy in every cell decreases by $1$. Obviously, once a cell’s energy decreases to $0$, it will not decrease any further. That is, after $k$ units of time, the total energy stored in the whole table is $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max((i \oplus j)-k,0).$$ Given the table, find the total energy it stores after $k$ units of time. Since the total energy may be large, output it modulo $p$.

The first line contains an integer $T$, the number of test cases. Then $T$ lines follow, each containing four integers $n, m, k, p$.

Output $T$ lines, each containing one number: the result of the total energy modulo $p$.

For $100\%$ of the testdata, it is guaranteed that $1 \le T \le 5000$, $1 \le p \le 10^9$, $1 \le n,m \le 10^{18}$, $0 \le 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.}$ Translated by ChatGPT 5