You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC120B] Uniformly Distributed

题面翻译

题目描述：

给定一个大小为 $H \times W$ 的网格图，每个格子可以被染成红色（R）、蓝色（B）或为空（.）。记空格数量为 $k$，将所有空格依次染成红色或蓝色，总共有 $2^k$ 种染色方案。

现在要求在从 $(1,1)$ 出发，向下或向右移动一格到达 $(H,W)$ 的过程中，所有经过的格子（包括起点和终点）中被染成红色的格子数目相等。求有多少种方案满足条件。答案对 $998244353$ 取模。

输入格式：

第一行包含两个整数 $H$ 和 $W$。接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，表示该行格子的染色情况。

输出格式：

输出一个整数，表示满足条件的染色方案数对 $998244353$ 取模的结果。

数据范围

$1 \leq H,W \leq 500$

题目描述

$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$ で割った余りを出力してください。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

2 2
B.
.R

样例输出 #1

2

样例 #2

样例输入 #2

3 3
R.R
BBR
...

样例输出 #2

0

样例 #3

样例输入 #3

2 2
BB
BB

样例输出 #3

1

提示

制約

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

Sample Explanation 1

マス $(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$ 通りあります。

Sample Explanation 2

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

Sample Explanation 3

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