Coloring the Table

Interview

Time limit2sMemory limit256 MB

Summary

Count colorings of an n by m grid, red or blue, where every 2 by 2 block has an odd number of red cells, respecting k fixed cells.

Level: Medium7 of 10
Topics: Math, Combinatorics, Union-find, Implementation
Solved: No attempts yet

Problem

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.

Input

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\}$

Output

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.

Examples3

Example 1
Input
```
3 4 3
2 2 1
1 2 0
2 3 1
```
Expected output
```
8
```
Example 2
Input
```
2 2 0
```
Expected output
```
8
```
Example 3
Input
```
2 2 4
1 1 1
1 2 0
2 1 0
2 2 0
```
Expected output
```
1
```