分数: 525 点
问题陈述
有一个 N \times M 网格和站在其上的玩家。
让 (i,j) 表示 i从顶部开始的第行和 j- 该网格左侧的第列。
这个网格的每个方格都是黑色或白色,用下式表示 N 字符串 S_1,S_2,\dots,S_N 长度 M 如下:
- 如果 j- 第一个字符 S_i is
.,方形 (i,j) 为白色; - 如果 j- 第一个字符 S_i is
#,方形 (i,j) 是黑色的。
网格据说是 美丽 当满足以下条件时。
- 对于每对整数 (i,j) 这样 1 \le i \le N, 1 \le j \le M,如果是正方形 (i,j) 是黑色的,下面的方块 (i,j) 和紧邻右下角的方块 (i,j) 也是黑色(如果存在)。
- 正式而言,满足以下所有条件。
- 如果是正方形 (i,j) 为黑色方形 (i+1,j) 存在,正方形 (i+1,j) 也是黑色的。
- 如果是正方形 (i,j) 为黑色方形 (i+1,j+1) 存在,正方形 (i+1,j+1) 也是黑色的。
高桥可以将零个或多个白色方块涂成黑色,他会这样做以使网格变得漂亮。
求他可以制作的不同漂亮网格的数量,取模 998244353.
当两个网格中存在一个具有不同颜色的正方形时,这两个网格被认为是不同的。
约束
- 1 \le N,M \le 2000
- S_i 是一个长度为的字符串 M 组成
.和#.
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N
输出
将答案打印为整数。
示例输入 1
2 2 .# ..
示例输出 1
3
他可以制作以下三种不同的漂亮网格:
.# .# ## .# ## ##
示例输入 2
5 5 ....# ...#. ..#.. .#.#. #...#
示例输出 2
92
示例输入 3
25 25 ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... .........................
示例输出 3
604936632
求计数模数 998244353.