#arc120b. [arc120_b]Uniformly Distributed

[arc120_b]Uniformly Distributed

题目描述:

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

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

输入格式:

第一行包含两个整数 HHWW。接下来 HH 行,每行包含一个长度为 WW 的字符串,表示该行格子的染色情况。

输出格式:

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

数据范围

1H,W20001 \leq H,W \leq 2000