2175: color
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：0
题目描述
Sam和他的妹妹Sara有一个包含n×m个方格的表格。他们想要将其中的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2×2的方形区域都包含奇数个（1个或3个）红色方格。
例如：下面是一个合法的表格染色方案（R表示红色，B表示蓝色）：
B B R B R
R B B B B
R R B R B
可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格依然满足他们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？
例如：下面是一个合法的表格染色方案（R表示红色，B表示蓝色）：
B B R B R
R B B B B
R R B R B
可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格依然满足他们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？
输入
输入文件中的第一行为三个整数n，m，k，分别表示表格的行数，列数和已被染色的方格数目。
接下来的k行描述了已被染色的方格。其中：第i行中为三个整数x[i]，y[i]，c[i]，分别表示第i个已被染色的方格的行编号、列编号和颜色。c[i]为1表示方格被染成红色，c[i]为0表示方格被染成蓝色。
输出
输出文件中仅一行为一个整数，表示可能的染色方案数W模10^9得到的值。（也就是说，如果W大于等于10^9，则输出W被10^9除所得到的余数）
样例输入 复制
3 4 3
2 2 1
1 2 0
2 3 1
样例输出 复制
8提示
知识点及提示
对于20%的数据，满足：n，m<=5，k<=5。
对于50%的数据，满足：n，m<=5000，k<=25。
对于100%的数据，满足：2<=n，m<=10^6，0<=k<=10^6，1<=x[i]<=n，1<=y[i]<=m。