[ABC334G] Christmas Color Grid 2

给定 $n\times m$ 的字符矩阵，`#` 表示绿色，`.` 表示红色。 均匀随机一个**绿色**块换成**红色**，求绿色**四连通**块的期望数量，对 $998244353$ 取模。 $1\le n,m\le 1000$

[problemUrl]: https://atcoder.jp/contests/abc334/tasks/abc334_g **この問題は問題 E と似た設定です。問題文の相違点を赤字で示します。** $ H $ 行 $ W $ 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。 グリッドの上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と表記します。 マス $ (i,j) $ の色は文字 $ S_{i,j} $ で表され、$ S_{i,j}\ = $ `.` のときマス $ (i,j) $ は赤色、$ S_{i,j}\ = $ `#` のときマス $ (i,j) $ は緑色に塗られています。 グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った $ 2 $ つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を **緑の連結成分数** と呼びます。ただし、$ 2 $ つのマス $ (x,y) $ と $ (x',y') $ が隣り合っているとは、$ |x-x'|\ +\ |y-y'|\ =\ 1 $ であることを指します。 **緑色**に塗られたマスを一様ランダムに $ 1 $ つ選び、**赤色**に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を $ \text{mod\ }\ 998244353 $ で出力してください。 「期待値を $ \text{mod\ }\ 998244353 $ で出力」とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $, $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、 $ R\ \times\ Q\ \equiv\ P\pmod{998244353} $ かつ $ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ がただ $ 1 $ つ存在することが証明できます。この $ R $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{1,1} $$ S_{1,2} $$ \ldots $$ S_{1,W} $ $ S_{2,1} $$ S_{2,2} $$ \ldots $$ S_{2,W} $ $ \vdots $ $ S_{H,1} $$ S_{H,2} $$ \ldots $$ S_{H,W} $

答えを出力せよ。

3 3
##.
#.#
#..

598946614

4 5
..#..
.###.
#####
..#..

199648872

3 4
#...
.#.#
..##

399297744

### 制約 - $ 1\ \leq\ H,W\ \leq\ 1000 $ - $ S_{i,j}\ = $ `.` または $ S_{i,j}\ = $ `#` - $ S_{i,j}\ = $ `#` なる $ (i,j) $ が存在する。 ### Sample Explanation 1 マス $ (1,1) $ を赤色に塗り替えたとき、緑の連結成分数は $ 3 $ となります。 マス $ (1,2) $ を赤色に塗り替えたとき、緑の連結成分数は $ 2 $ となります。 マス $ (2,1) $ を赤色に塗り替えたとき、緑の連結成分数は $ 3 $ となります。 マス $ (2,3) $ を赤色に塗り替えたとき、緑の連結成分数は $ 1 $ となります。 マス $ (3,1) $ を赤色に塗り替えたとき、緑の連結成分数は $ 2 $ となります。 よって、緑色に塗られたマスを一様ランダムに $ 1 $ つ選び、赤色に塗り替えた後の緑の連結成分数の期待値は $ (3+2+3+1+2)/5\ =11/5 $ となります。