[Apio2011]方格染色

Sam 和他的妹妹 Sara 有一个包含 $n\times m$ 个方格的表格。她们想将每个方格染成红色或蓝色，并要求表格中每个 $2\times 2$ 的方形区域都恰好包含奇数个红色方格，即包含 $1$ 个或 $3$ 个红色方格。

现在，表格中的一些方格已经被染上了颜色。请判断是否可以为剩余方格染色，使整个表格满足上述要求，并计算满足要求的染色方案总数。

输入格式

第一行包含三个整数 $n$ 、 $m$ 和 $k$ ，分别表示表格的行数、列数以及已经染色的方格数。

接下来 $k$ 行描述已经染色的方格。第 $i$ 行包含三个整数 $x_i$ 、 $y_i$ 和 $c_i$ ，分别表示第 $i$ 个已染色方格的行编号、列编号和颜色。

$c_i=1$ 表示该方格被染成红色， $c_i=0$ 表示该方格被染成蓝色。

输出一个整数，表示满足要求的染色方案数 $W$ 对 $10^9$ 取模后的结果。

本题为 APIO 2011 试题「方格染色」，题面与测试数据整理自 BZOJ 2303。