AT_codefestival_2015_ex_b TRAX

すぬけ君在玩一种叫做 TRAX 的棋盘游戏，它使用如下图所示的棋子。  他计划按照以下规则来摆放这些棋子： - 在一个 $H \times W$ 的网格中，正面朝上地放置所有棋子。每个棋子可以有4种不同的方向。 - 红线必须与相邻棋子的红线相连，白线必须与白线相连。即，红线的端点和白线的端点不能相邻。 - 避免形成封闭的环。看看下图中的例子，右图中的白线形成的大环也是不允许的。  すぬけ君已经放了 $N$ 个棋子。第 $i$ 个棋子被放在第 $R_i$ 行第 $C_i$ 列，方向为 $D_i$。方向用 $1 \sim 4$ 表示，如下图所示。  那么，剩余棋子有多少种放置方案？由于方案数可能非常大，请输出结果对 $10^9 + 7$ 取模后的结果。

输入由以下格式组成： > $H$ $W$ $N$ > $R_1$ $C_1$ $D_1$ > $R_2$ $C_2$ $D_2$ > ... > $R_N$ $C_N$ $D_N$ - 第一行给出两个整数 $H$ 和 $W$，分别表示棋盘的行数和列数，满足 $1 \le H, W \le 10^5$。 - 第二行给出一个整数 $N$，表示已经放置的棋子数，满足 $0 \le N \le 10^5$。 - 接下来的 $N$ 行，每行给出三个整数 $R_i, C_i, D_i$，分别表示第 $i$ 个棋子所在的行和列及其方向。棋子的位置各不相同，即当 $p \neq q$ 时，$(R_p, C_p) \neq (R_q, C_q)$。

输出形式为一个整数，表示剩余棋子的不同放置方法数量对 $10^9 + 7$ 取模后的结果。

- 本题有部分得分： - 对于 $N = 0$ 的情况，正确解答可得 $90$ 分。 - 对于没有额外限制的情况，正确解答可再得 $60$ 分。 ### 样例说明 1 下图展示了 4 种有效的摆放方案：  ### 样例说明 2 在这个示例中，无论怎么放置都不能达到规则要求。 **本翻译由 AI 自动生成**