圣诞彩格 2

题目描述

本题与 E 题设定类似,题面中与 E 题不同的部分以红色标出。

有一个 $H$ 行 $W$ 列的网格,每个格子被涂成红色或绿色。

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

格子 $(i,j)$ 的颜色用字符 $S_{i,j}$ 表示:当 $S_{i,j}$ 为 . 时格子 $(i,j)$ 为红色,当 $S_{i,j}$ 为 # 时格子 $(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 \lt 998244353$。请输出这个 $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

将格子 $(1,1)$ 重新涂成红色时,绿色连通分量数变为 $3$。 将格子 $(1,2)$ 重新涂成红色时,绿色连通分量数变为 $2$。 将格子 $(2,1)$ 重新涂成红色时,绿色连通分量数变为 $3$。 将格子 $(2,3)$ 重新涂成红色时,绿色连通分量数变为 $1$。 将格子 $(3,1)$ 重新涂成红色时,绿色连通分量数变为 $2$。 因此,均匀随机地选择一个绿色格子并重新涂成红色后,绿色连通分量数的期望值为 $(3+2+3+1+2)/5 = 11/5$。

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

199648872

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

399297744

数据范围

• $1 \leq H,W \leq 1000$
• $S_{i,j}$ 为 . 或 #
• 存在至少一个 $(i,j)$ 使得 $S_{i,j}$ 为 #