/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
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) も 黒 である。
高橋くんは、 白 のマスを 0 個以上何個でも 黒 に塗ることができ、この操作によってグリッドを美しくしようとしています。
高橋くんが作ることのできる美しいグリッドの種類数を 998244353 で割った余りを求めてください。
但し、ある 2 つのグリッドが異なるとは、両者で色が異なるマスが存在することを指します。
制約
- 1 \le N,M \le 2000
- S_i は
.と#からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
2 2 .# ..
出力例 1
3
作ることのできる美しいグリッドは以下の 3 種類です。
.# .# ## .# ## ##
入力例 2
5 5 ....# ...#. ..#.. .#.#. #...#
出力例 2
92
入力例 3
25 25 ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... .........................
出力例 3
604936632
998244353 で割った余りを求めてください。
Score : 525 points
Problem Statement
There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is black or white, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:
- if the j-th character of S_i is
., square (i,j) is white; - if the j-th character of S_i is
#, square (i,j) is black.
The grid is said to be beautiful when the following condition is satisfied.
- For every pair of integers (i,j) such that 1 \le i \le N, 1 \le j \le M, if square (i,j) is black, the square under (i,j) and the square to the immediate lower right of (i,j) are also black (if they exist).
- Formally, all of the following are satisfied.
- If square (i,j) is black and square (i+1,j) exists, square (i+1,j) is also black.
- If square (i,j) is black and square (i+1,j+1) exists, square (i+1,j+1) is also black.
Takahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.
Find the number of different beautiful grids he can make, modulo 998244353.
Two grids are considered different when there is a square that has different colors in those two grids.
Constraints
- 1 \le N,M \le 2000
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
2 2 .# ..
Sample Output 1
3
He can make the following three different beautiful grids:
.# .# ## .# ## ##
Sample Input 2
5 5 ....# ...#. ..#.. .#.#. #...#
Sample Output 2
92
Sample Input 3
25 25 ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... ......................... .........................
Sample Output 3
604936632
Find the count modulo 998244353.