Problem Background

$\text{uuku}$ waters his segment tree every day. However, since the segment tree is planar, $\text{uuku}$ uses a two-dimensional bucket to water it.

Problem Description

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

$\text{uuku}$'s method of filling the bucket with water is peculiar: he wants the water to be still at the moment of filling. That is, for any cell containing water, there must be water or a barrier to the left, right, and below. If the cell above a water-filled cell is empty, it is called a water level; if it is a barrier or outside the bucket, it is called an upper level. All water levels within a connected block of water must be at the same height, and all upper levels should not be higher than the water levels (this condition ensures that the water does not flow in a vacuum environment with gravity).

Starting from the moment the water is filled, expansion occurs every second. During each expansion, all water levels expand upwards by one layer into the empty spaces above, filling all reachable empty spaces whose heights are less than or equal to the newly expanded layer (this can be understood as still meeting $\text{uuku}$'s requirements). This process is considered to be instantaneous.

The magical water will continue to expand until all reachable empty spaces are filled with water, meaning there are no more water levels.

Now, $\text{uuku}$ wants to know the average time required for all water to stop expanding for all valid filling schemes.

Input Format

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

The next $h$ lines, each containing $w$ characters, where . represents an empty space and # represents a barrier.

Output Format

A single integer representing the average time $\text{uuku}$ needs to fill the bucket, modulo $998244353$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

110916040

Sample Input #2

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

Sample Output #2

966268884

Sample Input #3

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

Sample Output #3

581693010

Notes

Sample 1 Explanation

No time is needed to fill the water.

There are 9 possible scenarios (* represents water):

1.

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

Requires $0\text{s}$.

2.

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

Requires $1\text{s}$.

3.

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

Requires $1\text{s}$.

4.

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

Requires $1\text{s}$.

5.

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

Requires $1\text{s}$.

6.

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

Requires $1\text{s}$.

7.

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

Requires $1\text{s}$.

8.

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

Requires $1\text{s}$.

9.

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

Requires $0\text{s}$.

Thus, the expected value is $\dfrac{7}{9} \equiv 110916040 (\bmod 998244353)$.

Data Range

This problem uses bundled testing with 5 subtasks, and the final score is the sum of the scores from all subtasks.

$$ \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 data, $1 \le h,w \le 5000$.

见题面 Input 部分

见题面 Output 部分