题目描述
有一个 n 行 m 列的表格，行从 0 到 n−1 编号，列从 0 到 m−1 编号。
每个格子都储存着能量。最初，第 i 行第 j 列的格子储存着 (ixorj) 点能量。所以，整个表格储存的总能量是：
[
\sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} (i \mathbin{\text{xor}} j)
]
随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 1。显然，一个格子的能量减少到 0 之后就不会再减少了。
也就是说，k 个时间单位后，整个表格储存的总能量是：
[
\sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} \max((i \mathbin{\text{xor}} 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
数据范围与提示
- 测试点 1 ~ 2：T=5000，n≤100，m≤100，k≤100，p≤109；
- 测试点 3：T=5000，n≤1018，m≤1018，k=0，p≤109；
- 测试点 4：T=5000，n≤1018，m≤1018，k=1，p≤109；
- 测试点 5：T=5000，n≤10，m≤1018，k≤10，p≤109；
- 测试点 6：T=1，n≤105，m≤1018，k≤105，p≤109；
- 测试点 7：T=1，n≤1018，m≤1018，k≤1018，p≤109；
- 测试点 8：T=100，n≤1018，m≤1018，k≤1018，p≤109；
- 测试点 9 ~ 10：T=5000，n≤1018，m≤1018，k≤1018，p≤109。
