Description

One day, colazcy was again playing charts that were way above his level. In less than a minute, he threw his phone and cursed, “What a trash chart!” So he decided to make a custom chart on Cytoid to annoy others.

colazcy plans to create a super intense set of $m$ columns, with a total of $n$ rows. That is, his chart is an $n \times m$ matrix, where each position can be either Drag or Click. colazcy has already determined what some positions should be, but the rest are not decided yet.

However, colazcy noticed that if the rectangle corresponding to his chart contains a subrectangle in which all elements are Drag, then players can just hold down and slide through it. colazcy defines the simplicity of a chart as the number of subrectangles in the chart’s rectangle whose elements are all Drag.

Now colazcy gives you his unfinished chart and hopes you can tell him: if he fills the remaining undecided elements as Drag / Click uniformly at random, what is the expected simplicity of the final chart? It is not hard to see that the answer is always a rational number. 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 Numbers Modulo.

Input Format

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

The next $n$ lines each contain a string of length $m$. The $j$-th character of the $i$-th line is:

• o, meaning this position is fixed as Drag.
• x, meaning this position is fixed as Click.
• ?, meaning this position is not decided yet.

Output Format

Output one integer in one line, representing the expected simplicity modulo $998244353$.

2 2
oo
xo

5

2 2
oo
?o

7

3 4
o?o?
?xox
o?xo

499122189

Hint

Sample Explanation

Sample 1: The entire chart is already fixed, and simplicity $=$ the number of all-Drag submatrices $= 5$.

Sample 2: Only one position is undecided. If it is filled with Drag, the simplicity is $9$; if it is filled with Click, the simplicity is $5$. So the expected simplicity is $\dfrac{9+5}{2} = 7$.

Constraints

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

Subtask 1 (15 pts): There are no undecided elements (i.e., the input has no ?).

Subtask 2 (15 pts): The number of undecided elements is $\le 3$.

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

Subtask 4 (40 pts): No special constraints.

Translated by ChatGPT 5