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.
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.
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~).
- 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~
3 4 3 2 2 1 1 2 0 2 3 1