Problem : 239 - Color

Problem Statistics

Solved Member: 15　　Submission: 134　　User Tried: 15

Statement:

Sam和他的妹妹Sara 有一個包含n × m 個方格的表格。
她們想要將其的每個方格都染成紅色或藍色。
出於個人喜好，他們想要表格中每個2 × 2 的方形區域都包含奇數個（1 個或3 個）紅色方格。
例如，下圖是一個合法的表格染色方案。

可是昨天晚上，有人已經給表格中的一些方格染上了顏色！現在 Sam 和 Sara非常生氣。
不過，他們想要知道是否可能給剩下的方格染上顏色，使得整個表格仍然滿足她們的要求。
如果可能的話，滿足他們要求的染色方案數有多少呢？

Input:Output:

輸入的第一行包含三個整數n, m 和k，分別代表表格的行數、列數和已被染色的方格數目。
之後的 k 行描述已被染色的方格。
其中第i 行包含三個整數x_i, y_i 和 c_i，分別代表第 i 個已被染色的方格的行編號、列編號和顏色。
c_i為 1 表示方格被染成紅色，c_i為 0 表示方格被染成藍色。

對於20%的測試數據，n, m ≤ 5，k ≤ 5；
對於50%的測試數據，n, m ≤ 5000，k ≤ 25；
對於所有的測試數據，2 ≤ n, m ≤ 10⁵，0 ≤ k ≤ 10⁵，1 ≤ x_i ≤ n，1 ≤ y_i ≤ m。

輸出一個整數，表示可能的染色方案數目W 模10⁹得到的值。
（也就是說，如果 W 大於等於 10⁹，則輸出 W 被 10⁹除所得的餘數）。

Sample Input:Sample Output:

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

Source:

APIO 2011

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	4
2	1000ms	65536kb	4
3	1000ms	65536kb	4
4-1	1000ms	65536kb	4
4-2	1000ms	65536kb
5-1	1000ms	65536kb	4
5-2	1000ms	65536kb
6	1000ms	65536kb	4
7	1000ms	65536kb	4
8	1000ms	65536kb	4
9-1	1000ms	65536kb	4
9-2	1000ms	65536kb
10-1	1000ms	65536kb	4
10-2	1000ms	65536kb
11	1000ms	65536kb	3
12	1000ms	65536kb	3
13	1000ms	65536kb	3
14	1000ms	65536kb	3
15	1000ms	65536kb	3
16	1000ms	65536kb	3
17	1000ms	65536kb	3
18	1000ms	65536kb	3
19	1000ms	65536kb	3
20	1000ms	65536kb	3
21	1000ms	65536kb	3
22	1000ms	65536kb	3
23	1000ms	65536kb	3
24	1000ms	65536kb	3
25	1000ms	65536kb	3
26	1000ms	65536kb	3
27	1000ms	65536kb	3
28	1000ms	65536kb	3
29	1000ms	65536kb	3
30	1000ms	65536kb	3