AT_keyence2021_c Robot on Grid

[problemUrl]: https://atcoder.jp/contests/keyence2021/tasks/keyence2021_c $ H $ 行 $ W $ 列のマス目があります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と書くことにします。 それぞれのマスには `R`, `D`, `X` のいずれかの文字を書き込むことができます。はじめ、どのマスにも文字は書き込まれていません。 すぬけ君は $ K $ 個のマスを選んで文字を書き込みました。 $ i $ 番目に文字を書き込んだマスは $ (h_i,w_i) $ で、書き込んだ文字は $ c_i $ でした。 残りのマスへの文字の書き込み方は $ 3^{HW-K} $ 通りあります。それぞれの場合について以下の問題の答えを計算し、その総和を $ 998244353 $ で割ったあまりを求めてください。 > 上記のマス目上を移動可能なロボットがあります。 ロボットは $ (i,j) $ にいるとき、$ (i+1,j),(i,j+1) $ のいずれかに移動することができます。 ただし、$ (i,j) $ に `R` と書かれていた場合は $ (i,j+1) $ にのみ、`D` と書かれていた場合は $ (i+1,j) $ にのみ移動することができます。`X` と書かれていた場合はどちらにも移動可能です。 > > ロボットを $ (1,1) $ に設置したとき、ロボットがマス目の外に出ずに $ (H,W) $ に到達するようなロボットの移動経路は何通りありますか？ただし、ロボットは $ (H,W) $ に到達した時点で停止するものとします。 > > ここで、$ 2 $ つの移動経路が異なるとはロボットが通ったマスの集合が異なることをいいます。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $ $ h_1 $ $ w_1 $ $ c_1 $ $ \vdots $ $ h_K $ $ w_K $ $ c_K $

答えを出力せよ。

### 制約 - $ 2\ \leq\ H,W\ \leq\ 5000 $ - $ 0\ \leq\ K\ \leq\ \min(HW,2\ \times\ 10^5) $ - $ 1\ \leq\ h_i\ \leq\ H $ - $ 1\ \leq\ w_i\ \leq\ W $ - $ i\ \neq\ j $ ならば $ (h_i,w_i)\ \neq\ (h_j,w_j) $ - $ c_i $ は `R`, `D`, `X` のいずれか ### Sample Explanation 1 \- $ (1,2) $ のみまだ文字が書き込まれていません。 - `R` を書いたとき、ロボットが $ (H,W) $ に到達するようなロボットの移動経路は $ 1 $ 通りです。 - `D` を書いたとき、ロボットが $ (H,W) $ に到達するようなロボットの移動経路は $ 2 $ 通りです。 - `X` を書いたとき、ロボットが $ (H,W) $ に到達するようなロボットの移動経路は $ 2 $ 通りです。 - これらの総和である $ 5 $ を出力してください。 ### Sample Explanation 3 \- $ 998244353 $ で割ったあまりを求めるのを忘れずに。