Problem Description

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$.

Input Format

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 Format

Output one line with one integer, the answer.

1 4 2
1 1 1
1 3 1

0

5 6 12
1 1 2
1 2 2
1 3 1
1 5 2
1 6 2
3 1 1
3 5 1
4 1 2
4 2 2
4 5 2
4 6 2
5 3 1

2

6 6 14
1 1 2
1 2 2
1 3 1
1 5 2
1 6 2
3 1 1
3 5 1
4 1 1
4 5 1
5 1 2
5 2 2
5 5 2
5 6 2
6 3 1

1

Hint

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