P12731 Mondrian's Nightmare.

Little Z wants to use $1\times2$ dominoes to cover an $n\times m$ board. Every cell on the board must be covered, and the dominoes must not overlap. He thinks it looks ugly when the short sides of two dominoes touch, so he does not allow this to happen. Now Little Z has already placed a ring of dominoes along the boundary of the board. Please find the number of ways to cover the remaining area with dominoes. The answer may be very large; you only need to output it modulo $998244353$.

The first line contains three integers $n, m, k$. Here $k$ denotes the number of dominoes that Little Z has already placed. The next $k$ lines each contain three integers $x, y, t$, meaning there is already a domino whose top-left corner is at row $x$, column $y$ of the board. If $t=1$, the domino is placed horizontally; if $t=2$, it is placed vertically.

Output one line with one integer, the answer.

### Sample Explanation In the first sample, the dominoes placed by Little Z are shown in the figure below:  The short sides of the two placed dominoes touch, which is invalid, so the number of solutions is $0$. --- In the second sample, the dominoes placed by Little Z are shown in the figure below:  There are two valid solutions:  ___ In the third sample, the dominoes placed by Little Z are shown in the figure below:  There is only one valid solution:  ### Constraints and Notes **This problem uses bundled testdata.** For $100\%$ of the testdata, it is guaranteed that $1\le n, m\le5\times10^5$, $\frac{3}{2}(n+m-200)\le k\le2(n+m)$. Each pre-placed domino does not overlap with others and is on the boundary, and every boundary cell is covered by the pre-placed dominoes. For different subtasks, the constraints are as follows: **subtask1 (5 pts)**: $n\le2$. **subtask2 (10 pts)**: $n, m\le10$. **subtask3 (20 pts)**: $n, m\le40$. **subtask4 (15 pts)**: $n, m\le300$. **subtask5 (20 pts)**: $n, m\le1500$. **subtask6 (10 pts)**: $k\ge\frac{3}{2}(n+m-3)$. **subtask7 (20 pts)**: No special constraints. Translated by ChatGPT 5