← 返回题目列表

AtCoder · abc311_f

I. 又一个网格任务

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

分数: 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.