Problem Background

As we all know, despite being not very skilled, colazcy still enjoys playing Cytus.

Problem Description

One day, colazcy was attempting to play a chart above his level. Within a minute, he threw his phone down in frustration and exclaimed, "What a terrible chart!" So, he decided to create a custom chart on Cytoid to annoy others.

colazcy planned to create a chart with intense $m$-note patterns, arranged in $n$ rows. That is, his chart is an $n \times m$ matrix, where each position can be either a Drag or a Click. colazcy has already determined the elements for some positions, but the rest are yet to be decided.

However, colazcy noticed that if there is a sub-rectangle in his chart where all elements are Drags, players can simply hold down and pass through. colazcy defines the simplicity of a chart as the number of sub-rectangles in the chart that are entirely composed of Drags.

Now, colazcy has given you his unfinished chart and hopes you can tell him: if he randomly fills the remaining undecided elements with Drag or Click with equal probability, what is the expected simplicity of the final chart? It is easy to observe that the answer is always a rational number, and you only need to output the result modulo $998244353$. If you do not know how to take a rational number modulo a prime, you can refer to Rational Number Modulo Prime.

Input Format

The first line contains two positive integers $n, m$, representing the number of rows and columns of the matrix, respectively.

The next $n$ lines each contain a string of length $m$. The $j$-th character of the $i$-th line is o if the position is determined to be Drag, x if it is determined to be Click, and ? if the position is yet to be determined.

Output Format

A single integer representing the expected simplicity modulo $998244353$.

Sample Input and Output

Input Sample #1

2 2
oo
xo

Output Sample #1

5

Input Sample #2

2 2
oo
?o

Output Sample #2

7

Input Sample #3

3 4
o?o?
?xox
o?xo

Output Sample #3

499122189

Notes

Sample Explanation

Sample 1: The entire chart is already determined, and the simplicity = the number of sub-rectangles that are entirely Drags = $5$.

Sample 2: There is only one undecided position: when this position is filled with Drag, the simplicity is $9$; when it is filled with Click, the simplicity is $5$. Thus, the expected simplicity is $\dfrac{9+5}{2} = 7$.

Data Range

For all data, $1 \le n, m \le 100$.

Subtask 1 (15 pts): Guaranteed that there are no undecided elements (i.e., no ? in the input).

Subtask 2 (15 pts): Guaranteed that the number of undecided elements $\le 3$.

Subtask 3 (30 pts): Guaranteed that $n \le 30$.

Subtask 4 (40 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分