配点 : $400$ 点

問題文

$H$ 行 $W$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と呼ぶことにします。 マス目の状態を表す $H$ 個の文字列 $S_1, S_2, S_3, \dots, S_H$ が与えられます。マス $(i, j)$ の状態は以下の通りです。

• $S_i$ の $j$ 文字目が R ならば赤く塗られている
• $S_i$ の $j$ 文字目が B ならば青く塗られている
• $S_i$ の $j$ 文字目が . ならば色が塗られていない

色が塗られていないマスの個数を $k$ とすると、そのようなマスそれぞれを赤と青のどちらかで塗る方法は $2^k$ 通りありますが、このうち以下の条件を満たすものの個数を求めてください。

• マス $(1, 1)$ からマス $(H, W)$ に、右または下へ $1$ マス移動することを繰り返して辿り着くとき、途中で通過するマス (マス $(1, 1), (H, W)$ を含む) のうち赤に塗られたものの数が、通る経路によらず一定である

ただし、答えは非常に大きくなることがあるので、$998244353$ で割った余りを出力してください。

制約

• $2 \le H \le 500$
• $2 \le W \le 500$
• $S_i$ は R, B, . からなる長さ $W$ の文字列

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$S_1$

$S_2$

$S_3$

$\hspace{3pt} \vdots$

$S_H$

出力

答えを $998244353$ で割った余りを出力せよ。

2 2
B.
.R

2

マス $(1, 1)$ からマス $(2, 2)$ に、右または下へ $1$ マス移動することを繰り返して辿り着く方法は以下の $2$ 通りあります。

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

マス $(1, 2)$ とマス $(2, 1)$ を異なる色で塗った場合、上記の $2$ 通りの移動方法のどちらを選ぶかによって、通過する赤く塗られたマスの数が変わってしまうため条件を満たしません。 一方で、マス $(1, 2)$ とマス $(2, 1)$ を同じ色で塗った場合、通過する赤く塗られたマスの数は移動方法によって変わらないため、条件を満たします。 よって条件を満たす塗り方は $2$ 通りあります。

3 3
R.R
BBR
...

0

条件を満たす塗り方が存在しないかもしれません。

2 2
BB
BB

1

色が塗られていないマスが存在せず、現在のマス目は条件を満たすため、答えは $1$ となります。