Snuke 用以下這種拼塊玩耍（這種拼塊用於一款名為 TRAX 的遊戲）：

Snuke 想用這些拼塊填滿一個 $H \times W$ 的方格。在每個格子中，他以以下四種方向之一放置一塊拼塊：

如上圖所示，這些方向編號為 1 到 4。

拼塊的擺放必須滿足以下限制：

• 紅色弧線不能與白色弧線相接。
• 方格中不能出現環（見下方的例子）。
• 對於每個 $i$（$1 \le i \le N$），從上往下第 $R_i$ 列、從左往右第 $C_i$ 欄的格子中，拼塊的方向必須為 $D_i$。

例如，下圖顯示了兩種不合法的擺放方式。左側的擺放包含一個白色環，右側的擺放包含一個紅色環和一個大的白色環。

計算合法擺放方式的數量，答案對 $10^9 + 7$ 取模。

輸入格式

$$ \begin{gathered} H\quad W\\ N\\ R_1\quad C_1\quad D_1\\ \vdots\\ R_N\quad C_N\quad D_N \end{gathered} $$

• $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)$ 兩兩不同。

輸出格式

輸出合法擺放方式的數量，答案對 $10^9 + 7$ 取模。

範例

輸入格式 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，以下是四種合法的擺放方式：