Snuke 正在玩一种名为 TRAX 的游戏，他使用的瓷砖如下所示：

Snuke 想要用这些瓷砖填满一个 $H \times W$ 的网格。在网格的每个单元格中，他将瓷砖放置为以下四种方向之一：

这些方向在上面的图片中编号为 1 到 4。瓷砖的放置必须满足以下约束：

• 红色弧线不能接触白色弧线。
• 网格中不能包含环（参见下方的示例）。
• 对于每个 $i(1 \le i \le N)$，位于从上往下第 $R_i$ 行、从左往右第 $C_i$ 列的单元格中，瓷砖的方向必须为 $D_i$。

例如，下图展示了两种无效的放置方式。左侧的放置包含一个白色环，右侧的放置包含一个红色环和一个白色大环。

环的示例

计算有效放置的数量，对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $H$ 和 $W$。 第二行包含一个整数 $N$。 接下来的 $N$ 行，每行包含三个整数 $R_i, C_i, D_i$。

输出格式

输出有效放置的数量，对 $10^9 + 7$ 取模。

数据范围

• $1 \le H, W \le 10^5$
• $0 \le N \le 10^5$
• $1 \le R_i \le H$
• $1 \le C_i \le W$
• $1 \le D_i \le 4$
• $(R_i, C_i)$ 两两不同。

样例

输入 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

说明

对于样例 1，以下是四种有效的放置方式：