Sam and his sister Sara have a table of 
~n \times m~ square cells. they want to color all of the cells in red or blue. Due to personal beliefs, they want every 
~2 \times 2~ square of the table to have odd number of red cells (i.e. 1 or 3). For example, a valid coloring of a 
~3 \times 5~ table is drawn in the figure below.
B B R B R
R B B B B
R R B R B
Unfortunately, last night, someone had colored some of the cells of the table with red and some of the others with blue! Sam and Sara are wondering whether they can color the rest of the table such that no ~2 \times 2~ square contain an even number of red cells.
Input Specification
The first line of input contains three integers, 
~n~, 
~m~ and 
~k~, respectively the number of rows and columns of the table and the number of initially-colored cells. The following ~k~ lines contain a description of the colored cells. The 
~i~th line of this section contains three integers 
~x_i~, 
~y_i~, and 
~c_i~, where ~x_i~ and ~y_i~ are the row number of column number of the ~i~th initially-colored cell and ~c_i~ shows the color of the cell. ~c_i~ is equal to 1 if that cell is colored in red and it is equal to 0 if the cell is colored in blue. It is guaranteed that these ~k~ cells have distinct positions.
Output Specification
In a single line, write the number of possible ways of coloring the table (say 
~W~) modulo 
~10^9~ (i.e. if ~W~ is greater than or equal to ~10^9~, write its remainder in division by ~10^9~).
Constraints
- For each description of initially colored cells, it is guaranteed that
~1 \le x_i \le n~ and 
~1 \le y_i \le m~.
- Consider
~2 \le n, m \le 10^5~ and 
~0 \le k \le 10^5~ in all of the test cases.
- In
~20\%~ of tests 
~n, m \le 5~ and 
~k \le 5~.
- In
~50\%~ of tests, 
~n,m \le 5\,000~ and 
~k \le 25~
Sample Input
3 4 3
2 2 1
1 2 0
2 3 1
Sample Output
8
Comments
Test inputs 10, 12, 14, 16, and 18 seem wrong. And the official solution on the USACO forums seems to have off-by-one errors. Please check.
The test data have been validated and cross-referenced using this blog post and several other reputable online judges. If you have further concerns, please use the "report an issue" functionality.
people have solved the question???