테이블 색칠하기

Sam과 여동생 Sara는 $n \times m$ 크기의 테이블에 있는 모든 칸을 빨간색 또는 파란색으로 칠하려고 한다. 두 사람은 자신들의 믿음에 따라, 테이블 안의 모든 $2 \times 2$ 정사각형 영역에서 빨간색 칸의 개수가 홀수(즉 1개 또는 3개)가 되기를 원한다. 예를 들어 $3 \times 5$ 테이블에서도 이 조건을 만족하도록 칠하는 방법이 존재한다.

그런데 어젯밤 누군가가 테이블의 일부 칸을 미리 빨간색 또는 파란색으로 칠해 두었다. Sam과 Sara는 이미 칠해진 칸의 색을 그대로 유지하면서, 모든 $2 \times 2$ 정사각형 영역의 빨간색 칸 개수가 홀수가 되도록 나머지 칸을 칠할 수 있는지 알고 싶다. 만약 가능하다면, 그렇게 칠하는 서로 다른 방법이 몇 가지인지도 구하고자 한다.

첫째 줄에 세 정수 $n$, $m$, $k$가 주어진다. 각각 테이블의 행의 수, 열의 수, 그리고 미리 칠해져 있는 칸의 수이다. 이어지는 $k$개의 줄에 미리 칠해진 칸의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 세 정수 $x_i$, $y_i$, $c_i$가 있으며, $x_i$와 $y_i$는 그 칸의 행 번호와 열 번호이고, $c_i$는 그 칸의 색이다. 빨간색이면 $c_i = 1$, 파란색이면 $c_i = 0$이다. 미리 칠해진 $k$개 칸의 위치는 모두 서로 다르다.

• $2 \le n, m \le 10^5$
• $0 \le k \le 10^5$
• $1 \le x_i \le n$
• $1 \le y_i \le m$
• $c_i \in {0, 1}$

조건을 만족하도록 테이블을 칠하는 방법의 수를 $W$라 할 때, $W$를 $10^9$으로 나눈 나머지를 한 줄에 출력한다.