## APIO '11 P1 - Table Coloring

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Sam and his sister Sara have a table of square cells. they want to color all of the cells in red or blue. Due to personal beliefs, they want every square of the table to have odd number of red cells (i.e. 1 or 3). For example, a valid coloring of a 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 square contain an even number of red cells.

#### Input Specification

The first line of input contains three integers, , and , respectively the number of rows and columns of the table and the number of initially-colored cells. The following lines contain a description of the colored cells. The th line of this section contains three integers , , and , where and are the row number of column number of the th initially-colored cell and shows the color of the cell. 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 cells have distinct positions.

#### Output Specification

In a single line, write the number of possible ways of coloring the table (say ) modulo (i.e. if is greater than or equal to , write its remainder in division by ).

#### Constraints

• For each description of initially colored cells, it is guaranteed that and .
• Consider and in all of the test cases.
• In of tests and .
• In of tests, and

#### Sample Input

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

#### Sample Output

8