테이블 색칠하기

면접 대비

시간 제한2초메모리 제한256 MB

요약

n×m 격자의 각 칸을 빨강 또는 파랑으로 칠할 때 모든 2×2 블록의 빨강 칸 수가 홀수가 되도록 하는 색칠의 수를 k개의 고정된 칸을 지키며 구한다.

난이도: 보통10점 중 7점
유형: 수학, 조합론, 유니온 파인드, 구현
정답자: 아직 제출이 없습니다

문제

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$ 으로 나눈 나머지를 한 줄에 출력한다.

예제3

예제 1
입력
```
3 4 3
2 2 1
1 2 0
2 3 1
```
예상 출력
```
8
```
예제 2
입력
```
2 2 0
```
예상 출력
```
8
```
예제 3
입력
```
2 2 4
1 1 1
1 2 0
2 1 0
2 2 0
```
예상 출력
```
1
```