201201: [AtCoder]ARC120 B - Uniformly Distributed

Problem Statement

We have a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$-th row and $j$-th column.
You are given $H$ strings $S_1, S_2, S_3, \dots, S_H$ that describe the square, as follows:

• if the $j$-th character of $S_i$ is R, $(i, j)$ is painted red;
• if the $j$-th character of $S_i$ is B, $(i, j)$ is painted blue;
• if the $j$-th character of $S_i$ is ., $(i, j)$ is unpainted.

Let $k$ be the number of unpainted squares. Among the $2^k$ ways to paint each of those squares red or blue, how many satisfy the following condition?

• The number of red squares visited while getting from $(1, 1)$ to $(H, W)$ by repeatedly moving one square right or down, including $(1, 1)$ and $(H, W)$, is always the same regardless of the path taken.

Since the count may be enormous, print it modulo $998244353$.

Constraints

• $2 \le H \le 500$
• $2 \le W \le 500$
• $S_i$ is a string of length $W$ consisting of R, B, and ..

Input

Input is given from Standard Input in the following format:

$H$ $W$
$S_1$
$S_2$
$S_3$
$\hspace{3pt} \vdots$
$S_H$

Output

Print the count modulo $998244353$.

Sample Input 1

2 2
B.
.R

Sample Output 1

2

There are two ways to get from $(1, 1)$ to $(2, 2)$ by repeatedly moving right or down, as follows:

• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$

If we paint $(1, 2)$ and $(2, 1)$ in different colors, the above two paths will contain different numbers of red squares, violating the condition.
On the other hand, if we paint $(1, 2)$ and $(2, 1)$ in the same color, the two paths will contain the same numbers of red squares, satisfying the condition.
Thus, there are two ways to satisfy the condition.

Sample Input 2

3 3
R.R
BBR
...

Sample Output 2

0

There may be no way to satisfy the condition.

Sample Input 3

2 2
BB
BB

Sample Output 3

1

There is no unpainted square, and the current grid satisfies the condition, so the answer is $1$.