B - TRAX Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

すぬけ君はTRAXというボードゲームのコマを並べて遊んでいます。TRAXのコマは下図のようなものです。

token

すぬけ君はこのコマを以下のようなルールで並べようとしています。

  • H*W 個のコマを 全て表向きで 、縦 H 行、横 W 行のマス目状に敷き詰める。コマの向きは 4 通り考えられるがいずれの向きでも構わない。
  • 赤い線は隣のコマの赤い線と、白い線は隣のコマの白い線と繋がるようにしなければならない。つまり、赤い線の端と白い線の端が隣り合ってはいけない。
  • 輪っかができてはならない。下図は輪っかの例である。右の例の白い線のような大きな輪っかもできてはいけません。
cycle

すぬけ君はすでに N 個のコマを置きました。i (1 ≦ i ≦ N) 個目のコマは R_i 行目の C_i 列目に D_i の向きで置きました。向きは 1 ～ 4 の整数で表され、それぞれの向きは下図のように対応しています。

direction

さて、残りのコマの置き方は何通りあるでしょうか？答えは非常に大きな数になることがあるので 10^9+7 で割った余りを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

H W
N
R_1 C_1 D_1
R_2 C_2 D_2
:
R_N C_N D_N
  • 1 行目には、2 つの整数 H (1 ≦ H ≦ 10^5), W (1 ≦ W ≦ 10^5) が空白区切りで与えられる。これは、すぬけ君がコマを縦 H 行、横 W 行のマス目状に敷き詰めようとしていることを表す。
  • 2 行目には、すぬけ君がすでに置いたコマの個数を表す整数 N (0 ≦ N ≦ 10^5) が与えられる。
  • 3 行目からの N 行には、すぬけ君がすでに置いたコマの情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には 3 つの整数 R_i (1 ≦ R_i ≦ H), C_i (1 ≦ C_i ≦ W), D_i (1 ≦ D_i ≦ 4) が空白区切りで与えられる。これは、すぬけ君が R_i 行目の C_i 列目に D_i の向きでコマを置いたことを表している。ただし、同じ場所は 2 回以上与えられない、すなわち 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 行に出力せよ。出力の末尾に改行を入れること。

入力例1

2 2
1
1 1 4

出力例1

4

下図のような 4 通りの置き方が考えられます。

sample

入力例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