问题描述

顺势君正在玩一个名为 TRAX 的桌游。TRAX 的棋子如下图所示。

顺势君正尝试按照以下规则排列这些棋子：

• 将 $H*W$ 个棋子全部以正面朝上的方式，铺满一个 $H$ 行 $W$ 列的网格。棋子的朝向有四种可能，但不论哪种朝向均可。
• 红色线条应与相邻棋子的红色线条相连，白色线条应与相邻棋子的白色线条相连。也就是说，红色线条的一端不应与白色线条的一端相邻。
• 不允许形成环。下图是环的例子。同样，不允许形成类似右侧例子中的大型白色线条的环。

顺势君已经放置了 $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$

• 第一行包含两个整数 $H (1 ≦ H ≦ 10^5)$ 和 $W (1 ≦ W ≦ 10^5)$，表示顺势君将棋子放置在一个 $H$ 行 $W$ 列的网格上。
• 第二行包含一个整数 $N (0 ≦ N ≦ 10^5)$，表示顺势君已经放置的棋子数量。
• 第三行到第 $N+2$ 行，每行包含三个整数 $R_i (1 ≦ R_i ≦ H), C_i (1 ≦ C_i ≦ W), D_i (1 ≦ D_i ≦ 4)$，以空格分隔。表示顺势君将一个棋子放置在第 $R_i$ 行第 $C_i$ 列，并朝向 $D_i$。保证不会重复放置棋子，即对于 $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

2 2
1
1 1 4

输出样例1

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

---

将上述文本翻译成中文Markdown格式的结果如下：

问题文

顺势君正在玩一个名为 TRAX 的桌游。TRAX 的棋子如下图所示。

顺势君正尝试按照以下规则排列这些棋子：

• 将 $H*W$ 个棋子全部以正面朝上的方式，铺满一个 $H$ 行 $W$ 列的网格。棋子的朝向有四种可能，但不论哪种朝向均可。
• 红色线条应与相邻棋子的红色线条相连，白色线条应与相邻棋子的白色线条相连。也就是说，红色线条的一端不应与白色线条的一端相邻。
• 不允许形成环。下图是环的例子。同样，不允许形成类似右侧例子中的大型白色线条的环。

顺势君已经放置了 $N$ 个棋子。第 $i (1 \leq i \leq 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$

• 第一行包含两个整数 $H (1 \leq H \leq 10^5)$ 和 $W (1 \leq W \leq 10^5)$，表示顺势君将棋子放置在一个 $H$ 行 $W$ 列的网格上。
• 第二行包含一个整数 $N (0 \leq N \leq 10^5)$，表示顺势君已经放置的棋子数量。
• 第三行到第 $N+2$ 行，每行包含三个整数 $R_i (1 \leq R_i \leq H), C_i (1 \leq C_i \leq W), D_i (1 \leq D_i \leq 4)$，以空格分隔。表示顺势君将一个棋子放置在第 $R_i$ 行第 $C_i$ 列，并朝向 $D_i$。保证不会重复放置棋子，即对于 $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

2 2
1
1 1