#MX162. Uniformly Distributed

Uniformly Distributed

时间限制:1000ms

空间限制:512MB

题目描述

有一个 HH 行 WW 列的网格,每个格子被涂成红色(R)、蓝色(B)或未涂色(.)。

现在要把所有未涂色的格子染成红色或蓝色。设未涂色格子的数量为 kk,则共有 2k2^k 种染色方案。求有多少种染色方案满足以下条件:

从 (1,1)(1,1) 出发,每次向右或向下移动一格,最终到达 (H,W)(H,W)。无论选择哪条路径,路径上经过的格子(包括起点和终点)中,红色格子的数量都相同。

答案对 998244353998244353 取模。

输入格式

第一行两个正整数 H,WH,W。

接下来 HH 行,每行一个长度为 WW 的字符串,表示网格的状态。第 ii 行第 jj 个字符为 R 表示该格已涂成红色,为 B 表示已涂成蓝色,为 . 表示未涂色。

输出格式

输出一行一个整数,表示满足条件的染色方案数对 998244353998244353 取模的结果。

样例

样例 1 输入

2 2
B.
.R

样例 1 输出

2

样例 1 说明

从 (1,1)(1,1) 到 (2,2)(2,2) 有两条路径:

  • (1,1)→(1,2)→(2,2)(1,1)\to(1,2)\to(2,2)
  • (1,1)→(2,1)→(2,2)(1,1)\to(2,1)\to(2,2)

若 (1,2)(1,2) 和 (2,1)(2,1) 染成不同颜色,两条路径经过的红色格子数不同,不满足条件;若染成相同颜色,则两条路径经过的红色格子数相同。因此答案为 22。

样例 2 输入

3 3
R.R
BBR
...

样例 2 输出

0

样例 2 说明

可能不存在满足条件的染色方案。

样例 3 输入

2 2
BB
BB

样例 3 输出

1

样例 3 说明

没有未涂色的格子,且当前网格已经满足条件,因此答案为 11。

数据范围

对于 100%100\% 的数据,2≤H,W≤5002\le H,W\le 500,SiS_i 仅由 R、B、. 组成。