Coloring the Table

Sam and his younger sister Sara want to color every cell of an $n \times m$ table either red or blue. Because of their personal belief, they want every $2 \times 2$ square block of the table to contain an odd number of red cells (that is, exactly 1 or 3). For example, such a valid coloring also exists for a $3 \times 5$ table.

Last night, however, someone painted some of the cells red and some blue in advance. Keeping the colors of those already-painted cells, Sam and Sara want to know whether they can color the remaining cells so that every $2 \times 2$ square block contains an odd number of red cells. If it is possible, they also want to know how many different ways there are to do so.

The first line contains three integers $n$, $m$, and $k$: the number of rows, the number of columns, and the number of pre-colored cells, respectively. Each of the next $k$ lines describes one pre-colored cell with three integers $x_i$, $y_i$, and $c_i$, where $x_i$ and $y_i$ are the row and column of the cell and $c_i$ is its color: $c_i = 1$ if it is red and $c_i = 0$ if it is blue. The positions of the $k$ pre-colored cells are all distinct.

• $2 \le n, m \le 10^5$
• $0 \le k \le 10^5$
• $1 \le x_i \le n$
• $1 \le y_i \le m$
• $c_i \in {0, 1}$

Let $W$ be the number of ways to color the table so that the condition holds. Print $W$ modulo $10^9$ on a single line.