Background

JohnVictor enjoys playing Clash Royale.

He likes using a deck called Pekka Bridge Spam, but this deck was nerfed. Now he has dropped a lot of trophies on ladder and does not know how to play anymore, so he can only arrange his Battle Rams in the arena.

So this problem was created.

Problem Description

JohnVictor's Royal Arena is a $2n \times 2m$ grid (with $2n$ rows and $2m$ columns). He wants to place $n \times m$ Battle Rams of size $1 \times 2$ on it, such that no two Battle Rams overlap.

However, the Barbarians inside the Battle Ram will fight if they are too close, so he requires that in every $2 \times 2$ square, there exist two adjacent cells that are not occupied by any Battle Ram.

Now $k$ Battle Rams have already been placed. JohnVictor wants to know how many ways there are to place all these Battle Rams. Note that all Battle Rams are indistinguishable.

Since the answer is extremely large, JohnVictor only wants the remainder of the answer modulo the prime $p$. It is guaranteed that the real answer before taking modulo is greater than $0$.

To avoid misunderstandings for contestants who have played Clash Royale, here a Battle Ram can be regarded as a $1 \times 2$ domino, and after rotation it is still the same as itself. If you still do not understand, you can refer to the samples.

Because the Constraints of this problem are large, C++ users may use the following code to speed up modulo operations.

The code is from 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
}

How to use it:

Suppose the number to take modulo in the current program is $p$. Then call F = FastMod(p); at the beginning of the main function.

When computing $a\bmod p$, call F.reduce(a);, and the return value is $a\bmod p$.

Input Format

The first line contains four integers $n,m,k,p$.

The next $k$ lines each contain four integers $x_{1i},y_{1i},x_{2i},y_{2i}(1 \le i \le k)$, representing the position of one Battle Ram.

Note that the coordinates $x,y$ mean “row $x$, column $y$”, not Cartesian coordinates.

Output Format

One line with one integer, output the answer modulo $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

Hint

[Sample 1 Explanation]
The $9$ cases are shown in the figure below.

[Sample 2 Explanation]
I have a wonderful way to explain it, but this space is too small for me to write it down.

[Sample 3 Explanation]
In the figure above, the 1st and 2nd pictures in the first row and the 1st and 2nd pictures in the second row are exactly the required $4$ cases.

For more samples, please get them here.

[Constraints]

This problem uses bundled testdata, with a total of $7$ subtasks.

For $100\%$ of the testdata, $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$, and the input guarantees that a solution exists and that $p$ is prime.

[Warm Reminder]

To ensure that incorrect solutions with small constant factors can be rejected, the Constraints are set larger. Please pay attention to the impact of constant factors on the running time of your program.

Translated by ChatGPT 5