Snuke は次のタイルで遊んでいます（このタイルは TRAX というゲームで使われます）。

Snuke はこれらのタイルで $H\times W$ のマス目を埋めようとしています。各マスには、次の4通りの向きのいずれかでタイルを置きます。

これらの向きには、上の図のように $1$ から $4$ までの番号が付いています。

タイルの配置は、次の条件を満たす必要があります。

• 赤い弧が白い弧に接してはいけません。
• マス目の中に閉路があってはいけません（以下の例を参照してください）。
• 各 $i$ ($1\le i\le N$) について、上から $R_i$ 番目、左から $C_i$ 番目のマスに置くタイルの向きは $D_i$ でなければなりません。

例えば、次の図は条件を満たさない2通りの配置を示しています。左の配置には白い閉路があり、右の配置には赤い閉路と大きな白い閉路があります。

条件を満たす配置の個数を $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では、条件を満たす4通りの配置は次のとおりです。