分数: 500 点
问题陈述
我们有一个网格 H 行和 W 方格列。 (i, j) 表示 i从顶部开始的第行和 j左起第 列。
在每个方格上,我们可以写一个字母: R, D,或 X。最初,每个方块都是空的。
Snuke 选择了 K 的方块并在上面写下字符。 的 i他选择的第一个方格是 (h_i,w_i),他写了这封信 c_i 就可以了。
有 3^{HW-K} 在剩下的每个方格上写一个字母的方法。求下列问题所有答案的总和 3^{HW-K} 方式,模数 998244353.
我们有一个可以在网格上行走的机器人。 当它在 (i,j),可以移动到 (i+1, j) or (i, j+1).
但是,如果R写在 (i, j),只能移动到 (i, j+1);如果D写在 (i, j),只能移动到 (i+1, j)。如果X写在 (i, j),两种选择都是可能的。当机器人置于 (1, 1),机器人可以走多少条路径到达 (H, W) 不脱离电网?我们假设机器人在到达时停止 (H, W).
在这里,当机器人走过的方格组不同时,我们区分两条路径。
约束
- 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
- (h_i,w_i) \neq (h_j,w_j) 为 i \neq j.
- c_i is
R,D,或X.
输入
输入由标准输入按以下格式给出:
H W K h_1 w_1 c_1 \vdots h_K w_K c_K
输出
打印答案。
示例输入 1
2 2 3 1 1 X 2 1 R 2 2 R
示例输出 1
5
- 仅 (1,2) 为空。
- 如果我们写
R上面,机器人可以采取一种方式到达 (H, W). - 如果我们写
D上面,机器人可以采取两种方式到达 (H, W). - 如果我们写
X上面,机器人可以采取两种方式到达 (H, W).
- 如果我们写
- 我们应该打印这些计数的总和: 5.
示例输入 2
3 3 5 2 3 D 1 3 D 2 1 D 1 2 X 3 1 R
示例输出 2
150
示例输入 3
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
示例输出 3
139923295
- 请务必计算总和模 998244353.