AT_keyence2021_c Robot on Grid

有一个 $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)$ 后即停止。 > > 这里，若两条路径经过的格子集合不同，则认为这两条路径不同。

输入通过标准输入给出，格式如下： > $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` 中的一个 ## 样例解释 1 - 只有 $(1,2)$ 还未被填写字符。 - 如果填写 `R`，机器人到达 $(H, W)$ 的路径有 $1$ 条。 - 如果填写 `D`，机器人到达 $(H, W)$ 的路径有 $2$ 条。 - 如果填写 `X`，机器人到达 $(H, W)$ 的路径有 $2$ 条。 - 这三种情况的总和为 $5$，请输出 $5$。 ## 样例解释 3 - 不要忘记对 $998244353$ 取模。 由 ChatGPT 4.1 翻译