JohnVictor's Royal Arena

JohnVictor has a Royal Arena represented by a grid with 2n rows and 2m columns. He wants to place n×m siege hammers (which are identical 1×2 dominoes – note that a domino rotated by 90° is considered the same) on the grid so that no two siege hammers overlap. This means exactly 2n×m cells (i.e. 2·n·m cells) are covered by a domino, and the remaining cells (which total 2n×m) are left empty.

However, the barbarians inside the siege hammers tend to fight if they are too near each other. To avoid clashes, JohnVictor demands that in every 2×2 square subgrid (a contiguous block of 2 rows and 2 columns) there is at least one pair of adjacent cells (adjacent horizontally or vertically) that are not covered by any siege hammer. In other words, in every 2×2 block, at least one of the following pairs of cells must both be empty:

[ \begin{array}{cc} \text{(top row)} & \quad (\text{left, right}) \ \text{(bottom row)} & \quad (\text{left, right}) \ \text{(left column)} & \quad (\text{top, bottom}) \ \text{(right column)} & \quad (\text{top, bottom}) \end{array} ]

Initially, k dominoes have already been placed (their positions are given). The remaining dominoes must be placed on the still undetermined cells so that in total there will be exactly n×m dominoes and the above condition holds for every 2×2 square.

Your task is to count the number of valid ways to complete the placement (the pre‐placed dominoes must be part of the configuration) and output the answer modulo a given prime p. It is guaranteed that before taking the modulo the answer is greater than 0.

Note: For the purpose of clarity, each siege hammer is regarded as a 1×2 domino; flipping it does not make it different from its original orientation. If you are still not sure about the problem statement, please refer to the sample test cases.

Additionally, due to the relatively large range of the input data, C++ contestants may use the following FastMod implementation to speed up modulo operations (this is provided for reference only):

#include 
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; // 0 <= r = b ? r - b : r;
    }
};

// Usage:
// FastMod F(p);  // in main, after reading p
// To compute a % p, use F.reduce(a);

inputFormat

The first line contains four integers: n, m, k, and p (p is a prime number). The grid has 2n rows and 2m columns.

Then follow k lines. Each of these lines contains four integers: r₁, c₁, r₂, and c₂, indicating that a domino (siege hammer) has already been placed covering the cells (r₁, c₁) and (r₂, c₂). The cell coordinates are 1-indexed. It is guaranteed that these domino placements are valid and do not overlap.

outputFormat

Output a single integer: the number of valid ways to place the remaining dominoes (so that in total there are exactly n×m dominoes on the board and the condition on every 2×2 subgrid is satisfied) modulo p.

sample

1 1 0 1000000007

4