题目描述

在一个 $H$ 行 $W$ 列的网格中，每个格子上写有字符 X 或 Y。从上到下第 $i$ 行，从左到右第 $j$ 列的格子记作 $(i,\,j)$。网格中的字符由 $H$ 个字符串 $S_1,\,S_2,\,\dots,\,S_H$ 给出，第 $i$ 个字符串 $S_i$ 的第 $j$ 个字符表示格子 $(i,\,j)$ 上的字符。

你可以在相邻的每两行之间和每两列之间设置横向或纵向的栅栏，栅栏可以相互交叉。设置栅栏后，“从某个格子出发，只能通过上下左右相邻的格子且不跨越栅栏所能到达的所有格子”被定义为一个区画（请参考样例 1 的说明）。

栅栏的设置方式共有 $2^{H-1} \times 2^{W-1}$ 种。请计算其中满足下述条件的设置方式的个数，并对 $998244353$ 取模输出。

条件： 每个区画中恰好包含 $2$ 个写有 Y 的格子。

输入格式

输入以如下格式从标准输入给出。

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

输出满足条件的栅栏设置方式总数，对 $998244353$ 取模。

样例 1

输入

2 3
XYY
YXY

输出

2

样例 2

输入

2 3
XYX
YYY

输出

0

样例 3

输入

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

输出

164036797

说明/提示

限制条件

• $1 \leq H \leq 2000$
• $1 \leq W \leq 2000$
• $S_i\ (1 \leq i \leq H)$ 是仅由 X 和 Y 组成的长度为 $W$ 的字符串。

样例解释 1

下面是设置围栏的八种方式。

X Y Y    X|Y Y    X Y|Y    X|Y|Y
          |          |      | |
Y X Y    Y|X Y    Y X|Y    Y|X|Y


X Y Y    X|Y Y    X Y|Y    X|Y|Y
-----    -+---    ---+-    -+-+-
Y X Y    Y|X Y    Y X|Y    Y|X|Y

例如，如果在第 2 列和第 3 列之间设置一堵围栏，则划分的区画为：

XY
YX

Y
Y

每个区画都正好有两个 Y，因此满足条件。

如果在第 1 行与第 2 行之间以及第 1 列与第 2 列之间设置围栏，则划分的区画为：

X

YY

Y

XY

这些区画中，除第二个外，其余都没有正好两个 Y，因此不满足条件。

样例解释 2

无论如何设置栅栏，都无法满足条件，故答案为 0。

样例解释 3

请输出满足条件的栅栏设置方式总数，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译