Description

Sam and his sister Sara have a grid with $n \times m$ cells. They want to color each cell either red or blue. Due to personal preference, they want every $2 \times 2$ square in the grid to contain an odd number ($1$ or $3$) of red cells. For example, the following is a valid coloring (R stands for red, B stands for blue):

B B R B R
R B B B B
R R B R B

However, last night, someone already colored some cells! Now Sam and Sara are very upset. Still, they want to know whether it is possible to color the remaining cells so that the entire grid still satisfies their requirement. If it is possible, how many such colorings are there?

Input Format

The first line contains three integers $n, m, k$, representing the number of rows, the number of columns, and the number of precolored cells, respectively.

The next $k$ lines describe the precolored cells. The $i$-th line contains three integers $x_i, y_i, c_i$, representing the row index, the column index, and the color of the $i$-th precolored cell, respectively. $c_i = 1$ means the cell is red, and $c_i = 0$ means the cell is blue.

Output Format

Output a single integer: the value of $w$ modulo $10^9$, where $w$ is the number of valid colorings.

3 4 3
2 2 1
1 2 0
2 3 1

8

Hint

For $20\%$ of the testdata, $n, m, k \leqslant 5$.

For $50\%$ of the testdata, $n, m \leqslant 5000$, $k \leqslant 25$.

For $100\%$ of the testdata, $2 \leqslant n, m \leqslant 10^5$, $0 \leqslant k \leqslant 10^5$, $1 \leqslant x_i \leqslant n$, $1 \leqslant y_i \leqslant m$, $\forall c_i \in \{0, 1\}$.

Translated by ChatGPT 5