AT_codefestival_2015_ex_b TRAX

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-exhibition/tasks/codefestival_2015_ex_b すぬけ君はTRAXというボードゲームのコマを並べて遊んでいます。TRAXのコマは下図のようなものです。 すぬけ君はこのコマを以下のようなルールで並べようとしています。 - $ H*W $ 個のコマを **全て表向きで** 、縦 $ H $ 行、横 $ W $ 行のマス目状に敷き詰める。コマの向きは $ 4 $ 通り考えられるがいずれの向きでも構わない。 - 赤い線は隣のコマの赤い線と、白い線は隣のコマの白い線と繋がるようにしなければならない。つまり、赤い線の端と白い線の端が隣り合ってはいけない。 - 輪っかができてはならない。下図は輪っかの例である。右の例の白い線のような大きな輪っかもできてはいけません。 すぬけ君はすでに $ N $ 個のコマを置きました。$ i\ (1\ ≦\ i\ ≦\ N) $ 個目のコマは $ R_i $ 行目の $ C_i $ 列目に $ D_i $ の向きで置きました。向きは $ 1\ ～\ 4 $ の整数で表され、それぞれの向きは下図のように対応しています。 さて、残りのコマの置き方は何通りあるでしょうか？答えは非常に大きな数になることがあるので $ 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 $ を満たすことが保証される。

残りのコマの置き方の個数を $ 10^9+7\ (1,000,000,007) $ で割った余りを $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ =\ 0 $ を満たすデータセットに正解した場合は、$ 90 $ 点が与えられる。 - 追加の制約のないデータセットに正解した場合は、上記とは別に $ 60 $ 点が与えられる。 ### Sample Explanation 1 下図のような $ 4 $ 通りの置き方が考えられます。 !\[sample\](https://code-festival-2015-exhibition.contest.atcoder.jp/img/other/code\_festival\_2015\_final/ex/traxsample.jpg) ### Sample Explanation 2 どのように置いてもルールを満たすような置き方はできません。