又一个网格任务

题目描述

有一个 $N \times M$ 的网格,一名玩家站在上面。

用 $(i,j)$ 表示该网格第 $i$ 行(从上往下数)、第 $j$ 列(从左往右数)的格子。

网格中的每个格子要么是黑色,要么是白色,用 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\dots,S_N$ 表示如下:

• 若 $S_i$ 的第 $j$ 个字符为 .,则格子 $(i,j)$ 是白色;
• 若 $S_i$ 的第 $j$ 个字符为 #,则格子 $(i,j)$ 是黑色。

当满足以下条件时,称网格是美丽的:

对每一对满足 $1 \le i \le N$、$1 \le j \le M$ 的整数 $(i,j)$,若格子 $(i,j)$ 是黑色,则它下方的格子和它右下方相邻的格子也都是黑色(如果存在的话)。

形式化地说,以下条件都成立:

• 若格子 $(i,j)$ 是黑色,且格子 $(i+1,j)$ 存在,则格子 $(i+1,j)$ 也是黑色。
• 若格子 $(i,j)$ 是黑色,且格子 $(i+1,j+1)$ 存在,则格子 $(i+1,j+1)$ 也是黑色。

高桥君可以将零个或多个白色格子涂成黑色,他要通过这样的操作使网格变得美丽。

求他能够得到的不同的美丽网格的数量,对 $998244353$ 取模。

当两个网格存在某个格子颜色不同时,认为它们不同。

输入格式

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

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

以整数形式输出答案。

样例

2 2
.#
..

3

他能得到以下三种不同的美丽网格:

.#  .#  ##
.#  ##  ##

5 5
....#
...#.
..#..
.#.#.
#...#

92

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

604936632

注意答案需要对 $998244353$ 取模。

数据范围

• $1 \le N,M \le 2000$
• $S_i$ 是长度为 $M$、由 . 和 # 组成的字符串。