Background

$\text{uuku}$ waters his segment tree every day. But since the segment tree is planar, $\text{uuku}$ uses a 2D bucket to water it.

Problem Description

The bucket can be described as a vertical plane of size $h\times w$, where . means empty space and # means a barrier. It is guaranteed that all boundaries except the top side are #.

$\text{uuku}$ fills the bucket in a very special way: he wants the water to be motionless at the instant when filling finishes. That is, for any cell that contains water, its left, right, and bottom neighbors must all be either water or barriers. Also, if the cell above a water cell is empty, it is called a horizontal surface; if the cell above is a barrier or outside the bucket, it is called an upper boundary surface. Within each 4-connected component of water, all horizontal surfaces must be at the same height, and all upper boundary surfaces must not be higher than the horizontal surface (this condition means that in a vacuum with gravity, the water will not flow).

Starting from the moment filling finishes, time is counted. Every second, an expansion happens. In each expansion, all horizontal surfaces expand upward by one layer into empty cells, and all reachable empty cells with height less than or equal to the newly expanded layer are filled (this can be understood as still satisfying $\text{uuku}$'s requirements above). All of this can be considered to happen instantly.

This magical water keeps expanding until all reachable empty cells are filled, and then it stops expanding, i.e. no horizontal surface remains.

Now $\text{uuku}$ wants to know: among all filling plans that satisfy his requirements, what is the average time needed until all water stops expanding.

Input Format

The first line contains two integers $h$ and $w$, representing the height and width of the bucket.

The next $h$ lines each contain $w$ characters, where . means empty space and # means a barrier.

Output Format

Output one integer: the average time for $\text{uuku}$ to fill the bucket, modulo $998244353$, since the answer may be very large.

3 9
#...#...#
#.#...#.#
#########

110916040

10 20
###...###....#######
##..#.####.##.######
##.##.####.#.#.#####
#.#..##..###.#.....#
#..##.#.#....###.#.#
####....#.##.#..##.#
##..###.#.#..#.##..#
###...#..##.##..##.#
#.#.#.##.##.##..####
####################

966268884

10 20
#####.######.####.##
####.#.#####.###.###
###.###.####.##.####
###.###.####.#.#####
##.#####.###..######
##.......###.#.#####
#..#####..##.##.####
#.#######.##.###.###
#.#######.##.####.##
####################

581693010

Hint

Explanation of Sample 1

Filling the water takes no time.

There are $9$ cases (* means water):

$1$:

#...#...#
#.#...#.#
#########

Needs $0\text{s}$.

$2$:

#...#...#
#*#...#.#
#########

Needs $1\text{s}$.

$3$:

#...#...#
#*#***#.#
#########

Needs $1\text{s}$.

$4$:

#...#...#
#*#***#*#
#########

Needs $1\text{s}$.

$5$:

#...#...#
#.#***#.#
#########

Needs $1\text{s}$.

$6$:

#...#...#
#.#***#*#
#########

Needs $1\text{s}$.

$7$:

#...#...#
#*#...#*#
#########

Needs $1\text{s}$.

$8$：

#...#...#
#.#...#*#
#########

Needs $1\text{s}$.

$9$:

#***#***#
#*#***#*#
#########

Needs $0\text{s}$.

Therefore the expectation is $\dfrac{7}{9}\equiv 110916040(\bmod 998244353)$.

Constraints

This problem uses bundled testdata, with $5$ $\text{subtask}$ in total. The final score is the sum of the scores of all $\text{subtask}$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & h,w\le \cr\hline 1 & 10 & 10 \cr\hline 2 & 20 & 100 \cr\hline 3 & 20 & 500 \cr\hline 4 & 20 & 2000 \cr\hline 5 & 30 & 5000 \cr\hline \end{array}$$

For $100\%$ of the testdata, $1 \le h,w \le 5000$.

Translated by ChatGPT 5