题目背景

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 。

#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$ 种情况。

更多样例请到这里领取。

【数据范围】

本题采用捆绑测试，共有 $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$			$5$	$1.0s$
2	$10$		$k=0$	$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$
【温馨提示】

为了确保卡掉小常数的错解本题开大了数据范围，请注意常数因子对程序运行效率的影响。