题目描述

本题的设定与ABC334G题相似。题目描述中的差异部分已用红色标出。

现有一个$H$行$W$列的网格，每个单元格被涂成红色或绿色。

用$(i,j)$表示网格中从上数第$i$行、从左数第$j$列的单元格。

单元格$(i,j)$的颜色由字符$S_{i,j}$表示：$S_{i,j} =$ . 表示该单元格为红色，$S_{i,j} =$ # 表示该单元格为绿色。

网格中绿色连通分量的数量定义为：以所有绿色单元格为顶点、相邻绿色单元格之间的连线为边构成的图中连通分量的数量。其中，当两个单元格$(x,y)$和$(x',y')$满足$|x-x'| + |y-y'| = 1$时，称这两个单元格相邻。

现在，从所有红色单元格中均匀随机选择一个，并将其重新涂为绿色。请你计算重新涂色后网格中绿色连通分量数量的期望值，并将结果对$998244353$取模后输出。

关于“输出对998244353取模的期望值”的说明

可以证明，本题所求的期望值一定是有理数。此外，题目约束保证：若将该期望值表示为两个互质整数$P$和$Q$构成的分数$\frac{P}{Q}$，则存在唯一的整数$R$满足$R \times Q \equiv P \pmod{998244353}$且$0 \leq R < 998244353$。请输出这个$R$。

题目约束

• $1 \leq H,W \leq 1000$
• $S_{i,j}$ 仅为 . 或 #
• 至少存在一个单元格$(i,j)$满足$S_{i,j} =$ .

输入格式

输入数据从标准输入按以下格式给出：

$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}$

输出格式

输出所求的答案。

样例输入1

3 3
##.
#.#
#..

样例输出1

499122178

若将单元格$(1,3)$重新涂为绿色，绿色连通分量的数量变为$1$； 若将单元格$(2,2)$重新涂为绿色，绿色连通分量的数量变为$1$； 若将单元格$(3,2)$重新涂为绿色，绿色连通分量的数量变为$2$； 若将单元格$(3,3)$重新涂为绿色，绿色连通分量的数量变为$2$。

因此，从所有红色单元格中均匀随机选择一个并重新涂为绿色后，绿色连通分量数量的期望值为$(1+1+2+2)/4 = 3/2$。

样例输入2

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

样例输出2

598946613

样例输入3

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

样例输出3

285212675