AT_arc157_d [ARC157D] YY Garden

在一个 $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 \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 翻译