P6750 "MdOI R3" Pekka Bridge Spam

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.

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](https://github.com/kth-competitive-programming/kactl/blob/master/content/various/FastMod.h). ```cpp #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); ull r = a - q * b; // can be proven that 0 = b ? r - b : r; } }; FastMod F(2); int main() { int M = 1000000007; F = FastMod(M); ull x = 10ULL*M+3; cout

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.

One line with one integer, output the answer modulo $p$.

[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](https://www.luogu.com.cn/paste/b2ad2hoy). [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**. |Subtask ID|$n\leq$|$m\leq$|Other Properties|Score|Time Limit| |:-:|:-:|:-:|:-:|:-:|:-:| |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$| [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