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 嘅四種合法擺法如下：