『MdOI R3』Pekka Bridge Spam

JohnVictor 比较喜欢玩 Clash Royale。 他喜欢玩一套叫做 Pekka Bridge Spam 的卡组，然而这卡组被削弱了。现在他天梯已经掉了很多分了，不会玩了，只能在竞技场上给他的攻城锤安排地方了。 于是就有了这道题。

JohnVictor 的皇室竞技场是一个 $2n \times 2m$（$2n$ 行，$2m$ 列）的方格表，他要在上面放 $n\times m$ 个 $1 \times 2$ 的攻城锤，使得任意两个攻城锤不相交。 然而攻城锤里面的野蛮人靠太近会打架，所以他要求任意一个 $2 \times 2$ 的正方形中有两个相邻的格子没有被任何攻城锤占有。 现在已经摆好了 $k$ 个攻城锤了，JohnVictor 想要知道有多少种方法能摆放这些攻城锤，注意，攻城锤两两之间没有区别。 由于这个答案实在是太大了，JohnVictor 只想知道这个答案对素数 $p$ 取模后的余数。**保证取模前的真实答案大于 $0$**。 为了避免玩过皇室的参赛者对题目理解产生问题，这里的攻城锤看做一个 $1 \times 2$ 的多米诺，翻转后也与自身一样。如果还是不理解可以参考样例。 **由于本题数据范围较大，使用 C++ 的选手可以使用以下代码来加快取模速度。** 代码出自 [KATCL](https://github.com/kth-competitive-programming/kactl/blob/master/content/various/FastMod.h) 。 ```cpp #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef __uint128_t L; struct FastMod { ull b, m; FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {} ull reduce(ull a) { ull q = (ull)((L(m) * a) >> 64); ull r = a - q * b; // can be proven that 0 <= r < 2*b return r >= b ? r - b : r; } }; FastMod F(2); int main() { int M = 1000000007; F = FastMod(M); ull x = 10ULL*M+3; cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3 } ``` 使用方法： 假设当前程序中需要取模的数为 $p$，那么就在 `main` 函数开头处调用 `F = FastMod(p);`。 计算 $a\bmod p$ 的时候调用 ` F.reduce(a); `， 返回值就是 $a\bmod p$ 的值。

第一行为四个整数 $n,m,k,p$。 接下来 $k$ 行，每行四个整数 $x_{1i},y_{1i},x_{2i},y_{2i}(1 \le i \le k)$，代表一块攻城锤的位置。 注意这里 $x,y$ 坐标表示的是在第 $x$ 行第 $y$ 列，并不是横纵坐标。

一行一个整数，输出答案对 $p$ 取模后的值。

1 2 0 19260817

9

2 2 0 19260817

36

1 2 1 19260817
1 1 2 1

4

3 3 1 19260817
1 2 1 1

190

【样例 1 解释】 $9$ 种情况如下图所示。  【样例 2 解释】 我有一种绝妙的解释方法，可惜这里位置太小，我写不下。 【样例 3 解释】 上图中第一行的第 $1,2$ 幅和第二行的第 $1,2$ 幅图就是要求的 $4$ 种情况。 更多样例请[到这里](https://www.luogu.com.cn/paste/b2ad2hoy)领取。 【数据范围】 本题采用捆绑测试，共有 $7$ 个子任务。 对于 $100\%$ 的数据，$1 \le n \le 9 \times 10^3$，$1 \le m \le 10^{18}$，$0 \le k \le 10^5$，$|x_{1i}-x_{2i}|+|y_{1i}-y_{2i}|=1$，$1 \le x_{1i},x_{2i} \le 2n$，$1 \le y_{1i},y_{2i} \le 2m$，$10^7\le p \le 10^9 + 9 $，**输入数据保证有解且 $p$ 为素数**。 |子任务编号|$n\leq$|$m\leq$|其他性质|分值|时间限制| |:-:|:-:|:-:|:-:|:-:|:-:| |1|$3$|$3$||$5$|$1.0s$| |2|$10$|$10$|$k=0$|$10$|$1.0s$| |3|$5 \times 10^3$|$5 \times 10^3$||$13$|$2.0s$| |4|$80$|||$17$|$1.0s$| |5|$2\times 10^3$||$p=998244353$|$20$|$3.0s$| |6||||$35$|$3.0s$| 【温馨提示】 为了确保卡掉小常数的错解本题开大了数据范围，请注意常数因子对程序运行效率的影响。