APIO '11 P1 - Table Coloring

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.


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 ith 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 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.

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).


  • 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



There are no comments at the moment.