Codah ClubTrain. Submit. Improve.
Sign in
English
#000587

Table Coloring

Sam and his sister Sara have a table of n x m square cells. They want to color all of the cells in red or blue. Due to personal beliefs, they want every 2 x 2 square of the table have odd number of red cells (i.e. 1 or 3).



Unfortunately, last night, someone had colored some cells of the table with red and some of the others with blue. Sam and Saraare wondering whether they can color the rest of the table according to their rules or not. If it is possible, they want to know in how many ways they can color the table such that no 2 x 2 square contain an even number of red cells.



InputThe first line of input contains 3 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 description of colored cells. The ith line of this section contains 3 integer x[i] , y[i] and c[i] , where x[i] and y[i] are the row number and column number of the ith 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.


OutputIn a single line, write number of possible ways of coloring the table modulo 10^9. (i.e. its remainder in division by 10^9).


CONSTRAINTS

For each description of initially-colored cells, it is guaranteed that 1 <= x[i] <= n and 1 <= y[i] <= m.
Consider 2 <= n, m <= 10^5 and 0 <= k <= 10^5 for all test cases.
In 20% of tests n, m <=5 and k <=5.
In 50% of tests n, m <=5000 and k <=25.



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

Output
8

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.