問題文
Snuke 正在玩一种名为 TRAX 的棋盘游戏,通过排列棋子来玩。 TRAX 框架如下图所示。
Snuke 试图根据以下规则排列这些碎片。
- H*W 件 全部正面朝上 、縦 H 行、横 W 将其放置在行网格中。框架的方向 4 有很多可能性,但任一方向都可以。
- 红线必须连接到相邻棋子的红线,白线必须连接到相邻棋子的白线。换句话说,红线的端点和白线的端点不能彼此相邻。
- 不应有循环。下图是一个环的示例。也不应该出现像右例中的白线这样的大环。
Snuke 已经 我放置了 N 块。i (1 ≦ i ≦ N) 框架是 R_i 线 C_i 在栏中 我将其放置在 D_i 方向。方向是 表示为 1 ~ 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
- 1 行中,2 整数 编写一个程序来查找 H (1 ≦ H ≦ 10^5), W (1 ≦ W ≦ 10^5) 用空格分隔。这是 Snuke 君将框架垂直移动的样子。 H 行、横 W 指示行将以网格模式布局。
- 2 行是一个整数,表示 Snuke 已经放置的棋子数量。 N (0 ≦ N ≦ 10^5) 。 来自行
- 3 来自行 N 行给出了 Snuke 已经放置的棋子的信息。其中 i (1 ≦ i ≦ N) 在线 3 整数 编写一个程序来查找 R_i (1 ≦ R_i ≦ H), C_i (1 ≦ C_i ≦ W), D_i (1 ≦ D_i ≦ 4) 用空格分隔。这是斯努克 这表明该棋子被放置在 R_i 线 C_i 在栏中 我将其放置在 D_i 方向。然而,同一个地点 未给予超过 2 次,即 当 p \neq q 什么时候 R_p \neq R_q 或 如果 C_p \neq C_q 保证得到满足。 如果正确答案是满足
部分点
针对此问题设置了部分分数。
- N = 0 的数据集,90 分被给予。
- 除了上述内容之外,如果答案对于没有附加约束的数据集是正确的, 60 分被给予。
出力
剩余件数 10^9+7 (1,000,000,007) 取模之后的余数 1 行输出。在输出末尾插入换行符。
入力例1
2 2 1 1 1 4
出力例1
4
如下图 4 你可以想想如何放置街道。
入力例2
2 10 2 1 1 1 1 2 1
出力例2
0
无论怎么放置,都不可能是满足规则的放置方式。
入力例3
2015 1114 0
出力例3
711460824
入力例4
2 2 2 1 1 1 2 2 3
出力例4
0
入力例5
5 6 3 1 2 2 4 1 1 5 6 4
出力例5
12
入力例6
5 6 2 3 3 4 3 4 2
出力例6
39