配点 : $500$ 点

問題文

$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$ つの移動経路が異なるとはロボットが通ったマスの集合が異なることをいいます。

制約

• $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 のいずれか

入力

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

$H$ $W$ $K$

$h_1$ $w_1$ $c_1$

$\vdots$

$h_K$ $w_K$ $c_K$

出力

答えを出力せよ。

2 2 3
1 1 X
2 1 R
2 2 R

5

• $(1,2)$ のみまだ文字が書き込まれていません。- R を書いたとき、ロボットが $(H,W)$ に到達するようなロボットの移動経路は $1$ 通りです。
  • D を書いたとき、ロボットが $(H,W)$ に到達するようなロボットの移動経路は $2$ 通りです。
  • X を書いたとき、ロボットが $(H,W)$ に到達するようなロボットの移動経路は $2$ 通りです。
• R を書いたとき、ロボットが $(H,W)$ に到達するようなロボットの移動経路は $1$ 通りです。
• D を書いたとき、ロボットが $(H,W)$ に到達するようなロボットの移動経路は $2$ 通りです。
• X を書いたとき、ロボットが $(H,W)$ に到達するようなロボットの移動経路は $2$ 通りです。
• これらの総和である $5$ を出力してください。

3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R

150

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

139923295

• $998244353$ で割ったあまりを求めるのを忘れずに。