AT_abc311_f [ABC311F] Yet Another Grid Task

[problemUrl]: https://atcoder.jp/contests/abc311/tasks/abc311_f $ 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 $ つのグリッドが異なるとは、両者で色が異なるマスが存在することを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

答えを整数として出力せよ。

### 制約 - $ 1\ \le\ N,M\ \le\ 2000 $ - $ S_i $ は `.` と `#` からなる長さ $ M $ の文字列 ### Sample Explanation 1 作ることのできる美しいグリッドは以下の $ 3 $ 種類です。 ``` .# .# ## .# ## ## ``` ### Sample Explanation 3 $ 998244353 $ で割った余りを求めてください。