[SDOI2016]储能表

题目描述

有一个 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 行,每行一个数,表示总能量对 p 取模后的结果

输入输出样例

输入样例 #1

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

输出样例 #1

2
12
6

说明

测试点 1 ~ 2:$ T = 5000 $,$ n \leq 100 $,$ m \leq 100 $,$ k \leq 100 $,$ p \leq 10 ^ 9 $; 测试点 3:$ T = 5000 $,$ n \leq 10 ^ {18} $,$ m \leq 10 ^ {18} $,$ k = 0 $,$ p \leq 10 ^ 9 $; 测试点 4:$ T = 5000 $,$ n \leq 10 ^ {18} $,$ m \leq 10 ^ {18} $,$ k = 1 $,$ p \leq 10 ^ 9 $; 测试点 5:$ T = 5000 $,$ n \leq 10 $,$ m \leq 10 ^ {18} $,$ k \leq 10 $,$ p \leq 10 ^ 9 $; 测试点 6:$ T = 1 $,$ n \leq 10 ^ 5 $,$ m \leq 10 ^ {18} $,$ k \leq 10 ^ 5 $,$ p \leq 10 ^ 9 $; 测试点 7:$ T = 1 $,$ n \leq 10 ^ {18} $,$ m \leq 10 ^ {18} $,$ k \leq 10 ^ {18} $,$ p \leq 10 ^ 9 $; 测试点 8:$ T = 100 $,$ n \leq 10 ^ {18} $,$ m \leq 10 ^ {18} $,$ k \leq 10 ^ {18} $,$ p \leq 10 ^ 9 $; 测试点 9 ~ 10:$ T = 5000 $,$ n \leq 10 ^ {18} $,$ m \leq 10 ^ {18} $,$ k \leq 10 ^ {18} $,$ p \leq 10 ^ 9 $ 。