题目描述

有一个 $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$			$10^9$
$3$		$10^{18}$	$10^{18}$	$0$
$4$				$1$
$5$		$10$		$10$
$6$	$1$	$10^5$		$10^5$
$7$		$10^{18}$		$10^{18}$
$8$	$100$
$9,10$	$5000$

$\texttt{Statement fixed by Starrykiller.}$