Problem Background

JohnVictor enjoys playing Clash Royale.

He favors a deck called Pekka Bridge Spam, but it has been nerfed. Now, he has lost many points in the ladder and doesn't know how to play anymore. He can only arrange his siege hammers in the arena.

Hence, this problem was created.

Problem Description

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

However, the barbarians inside the siege hammers tend to fight if they are too close, so he requires that in any $2 \times 2$ square, there are two adjacent cells that are not occupied by any siege hammer.

Already, $k$ siege hammers have been placed. JohnVictor wants to know how many ways there are to arrange these siege hammers, noting that the siege hammers are indistinguishable from each other.

Since the answer is too large, JohnVictor only wants to know the remainder of this answer when divided by a prime number $p$. It is guaranteed that the true answer before modulo is greater than 0.

To avoid confusion for players familiar with Clash Royale, the siege hammer is considered as a $1 \times 2$ domino, which is identical to its flipped version. If this is still unclear, refer to the sample cases.

Due to the large data range, C++ users can 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
}

Usage:

Suppose the number to be moduloed in the program is $p$, then call F = FastMod(p); at the beginning of the main function.

To calculate $a \bmod p$, call F.reduce(a);, which returns the value of $a \bmod p$.

Input Format

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

The next $k$ lines, each containing four integers $x_{1i}, y_{1i}, x_{2i}, y_{2i} (1 \le i \le k)$, represent the position of a siege hammer.

Note that the coordinates $x, y$ represent the $x$-th row and $y$-th column, not the horizontal and vertical coordinates.

Output Format

A single line with one integer, the answer modulo $p$.

Sample Input and Output

Input Sample #1

1 2 0 19260817

Output Sample #1

9

Input Sample #2

2 2 0 19260817

Output Sample #2

36

Input Sample #3

1 2 1 19260817
1 1 2 1

Output Sample #3

4

Input Sample #4

3 3 1 19260817
1 2 1 1

Output Sample #4

190

Notes/Hints

Sample 1 Explanation
There are 9 possible configurations as shown in the diagram.

Sample 2 Explanation
I have a brilliant explanation method, but the space here is too small to write it down.

Sample 3 Explanation
The first and second images in the first row and the first and second images in the second row of the diagram represent the 4 required configurations.

For more samples, please visit here.

Data Range

This problem uses subtask testing with a total of 7 subtasks.

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

Reminder

To ensure that suboptimal solutions with small constants are eliminated, the data range has been increased. Please be aware of the impact of constant factors on program efficiency.

见题面 Input 部分

见题面 Output 部分