Problem Statement

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.

Snuke 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.

There 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~ .

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)~ .
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.

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)~ .

Here, we distinguish two paths when the sets of squares traversed by the robot are different.

Constraints

• ~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)~ for ~i \neq j~ .
• ~c_i~ is R , D , or X .

Input

Input is given from Standard Input in the following format:

~H~ ~W~ ~K~

~h_1~ ~w_1~ ~c_1~

~\vdots~

~h_K~ ~w_K~ ~c_K~

Output

Print the answer.

Sample Input 1

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

Sample Output 1

5

• Only ~(1,2)~ is empty.
  • If we write R on it, there is one way that the robot can take to reach ~(H, W)~ .
  • If we write D on it, there are two ways that the robot can take to reach ~(H, W)~ .
  • If we write X on it, there are two ways that the robot can take to reach ~(H, W)~ .
• We should print the sum of these counts: ~5~ .

Sample Input 2

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

Sample Output 2

150

Sample Input 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

Sample Output 3

139923295

• Be sure to compute the sum modulo ~998244353~ .