← 返回题目列表

AtCoder · arc157_d

D. YY花园

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个网格 H 行和 W 列,其中每个方格都有一个字符 上面写着 X 和 Y 。 让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。 网格上的字符给出为 H 字符串 S_1, S_2, \dots, S_H: j- 第一个字符 S_i 是方块上的字符 (i, j).

您可以在相邻行和列之间的网格上设置栅栏。 栅栏可能相交。 设置好围栏后, 块 被定义为从某个方格重复向上、向下、向左或向右移动到相邻方格而不跨越栅栏可到达的方格集合。 (另请参见示例输出 1。)

有 2^{H-1} \times 2^{W-1} 设置围栏的方法。其中有多少满足以下条件,取模 998244353?

条件: 每个块正好有两个正方形 Y 。

约束

  • 1 \leq H \leq 2000
  • 1 \leq W \leq 2000
  • S_i \ (1 \leq i \leq H) 是一个长度为的字符串 W 组成 X 和 Y.

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
\vdots
S_H

输出

打印满足条件的设置围栏的方式数,模数 998244353.


示例输入 1

2 3
XYY
YXY

示例输出 1

2

以下是设置围栏的八种方法。

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-nd 和 3-rd 列,块是:

XY
YX
Y
Y

每个块都有两个 Ys,因此满足条件。

如果在 1-st 和 2-nd 行和 1-st 和 2-nd 列,块是:

X
YY
Y
XY

这些块,除了第二个之外,没有恰好两个 Ys,所以条件不满足。


示例输入 2

2 3
XYX
YYY

示例输出 2

0

无法设置围栏来满足条件。


示例输入 3

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

示例输出 3

164036797

打印模数的方式数 998244353.