题目描述

$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$

输出格式

答えを出力せよ。

题目大意

有 $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+1,j)$、$(i,j+1)$中的任意一个。但是，如果$(i,j)$中写着 $R$，则只能在$(i,j+1)$中移动，如果写着 $D$，则只能在$(i+1,j)$中移动。写着 $X$ 的情况下都可以任意移动。

在 $(1,1)$ 中设置机器人时，机器人不出网格而到达 $(H,W)$ 的移动路径有几种？注意：机器人在到达 $(H,W)$ 时停止。

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

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

提示

制約

• $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$ で割ったあまりを求めるのを忘れずに。