储能表 ### 题目描述 有一个 $n$ 行 $m$ 列的表格，行从 $0$ 到 $n−1$ 编号，列从 $0$ 到 $m−1$ 编号。每个格子都储存着能量。最初，第 $i$ 行第 $j$ 列的格子储存着 $(i\ xor\ j)$ 点能量。所以，整个表格储存的总能量是， $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (i \mathrm{xor} j)$$ 随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 $1$。显然，一个格子的能量减少到 $0$ 之后就不会再减少了。 也就是说，$k$ 个时间单位后，整个表格储存的总能量是 $$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \mathrm{max} ((i \mathrm{xor} j)-k,0)$$ 给出一个表格，求 $k$ 个时间单位后它储存的总能量。 由于总能量可能较大，输出时对 $p$ 取模。 ### 输入描述 第一行一个整数 $T$，表示数据组数。 接下来 $T$ 行，每行四个整数 $n、m、k、p$。 其中，$T = 5000$，$n \leq 10 ^ {18}$，$m \leq 10 ^ {18}$，$k \leq 10 ^ {18}$，$p \leq 10 ^ 9$ 。 ### 输出描述 共 $T$ 行，每行一个数，表示总能量对 $p$ 取模后的结果。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 2 2 0 100 3 3 0 100 3 3 1 100 ``` >输出 ```txt 2 12 6 ```