{"problem":{"name":"Robot on Grid","description":{"content":"We have a grid with $H$ rows and $W$ columns of squares. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. On each square, we can write a letter: `R`, `D","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"keyence2021_c"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $H$ rows and $W$ columns of squares. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. On each square, we can write a letter: `R`, `D`, or `X`. Initially, every square is empty.\nSnuke chose $K$ of the squares and wrote characters on them. The $i$\\-th square he chose was $(h_i,w_i)$, and he wrote the letter $c_i$ on it.\nThere are $3^{HW-K}$ ways to write a letter on each of the remaining squares. Find the sum of the answers to the problem below for all those $3^{HW-K}$ ways, modulo $998244353$.\n\n> We have a robot that can walk on the grid. When it is at $(i,j)$, it can move to $(i+1, j)$ or $(i, j+1)$.  \n> However, if `R` is written on $(i, j)$, it can only move to $(i, j+1)$; if `D` is written on $(i, j)$, it can only move to $(i+1, j)$. If `X` is written on $(i, j)$, both choices are possible.\n> When the robot is put at $(1, 1)$, how many paths can the robot take to reach $(H, W)$ without going out of the grid? We assume the robot halts when reaching $(H, W)$.\n> Here, we distinguish two paths when the sets of squares traversed by the robot are different.\n\n## Constraints\n\n*   $2 \\leq H,W \\leq 5000$\n*   $0 \\leq K \\leq \\min(HW,2 \\times 10^5)$\n*   $1 \\leq h_i \\leq H$\n*   $1 \\leq w_i \\leq W$\n*   $(h_i,w_i) \\neq (h_j,w_j)$ for $i \\neq j$.\n*   $c_i$ is `R`, `D`, or `X`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $K$\n$h_1$ $w_1$ $c_1$\n$\\vdots$\n$h_K$ $w_K$ $c_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"keyence2021_c","tags":[],"sample_group":[["2 2 3\n1 1 X\n2 1 R\n2 2 R","5\n\n*   Only $(1,2)$ is empty.\n    *   If we write `R` on it, there is one way that the robot can take to reach $(H, W)$.\n    *   If we write `D` on it, there are two ways that the robot can take to reach $(H, W)$.\n    *   If we write `X` on it, there are two ways that the robot can take to reach $(H, W)$.\n*   We should print the sum of these counts: $5$."],["3 3 5\n2 3 D\n1 3 D\n2 1 D\n1 2 X\n3 1 R","150"],["5000 5000 10\n585 1323 R\n2633 3788 X\n1222 4989 D\n1456 4841 X\n2115 3191 R\n2120 4450 X\n4325 2864 X\n222 3205 D\n2134 2388 X\n2262 3565 R","139923295\n\n*   Be sure to compute the sum modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}