Expected Simplicity of the Drag Grid

Colazcy is preparing a custom Cytoid layout that is an n×m grid. Each cell of the grid can be either Drag or Click. Some cells are already fixed to a specific value (Drag or Click), while the remaining cells are undecided. Colazcy will fill each undecided cell uniformly at random with Drag or Click (each with probability \(\frac{1}{2}\)).

The simplicity of a grid is defined as the number of subrectangles (contiguous submatrices) whose every cell is Drag. Note that if a subrectangle contains a cell that is fixed as Click, then its contribution is 0. Otherwise, if there are \(k\) undecided cells in the subrectangle (and the rest are fixed Drag), then the probability that all cells become Drag is \((\frac{1}{2})^k\).

You are given the partially fixed grid. Your task is to compute the expected simplicity, i.e. the expected number of subrectangles that are completely filled with Drag. It can be shown that the answer is a rational number. Output the answer modulo 998244353 (i.e. the modular value of the rational number). All formulas are given in \(\LaTeX\) format.

Input Format: The first line contains two integers \(n\) and \(m\) denoting the number of rows and columns respectively. Then follow \(n\) lines, each containing a string of length \(m\). Each character is one of:

• D representing a fixed Drag cell,
• C representing a fixed Click cell, or
• ? representing an undecided cell.

Output Format: Output a single integer, the expected simplicity modulo \(998244353\). It is guaranteed that the expected value is a rational number, and you should output it modulo the prime.

inputFormat

The input begins with two integers \(n\) and \(m\) (the number of rows and columns respectively).

Then there are \(n\) lines, each containing a string of length \(m\). The characters are either D (fixed Drag), C (fixed Click) or ? (undecided cell). In the undecided cells, the value is chosen independently to be Drag (with probability \(\frac{1}{2}\)) or Click (with probability \(\frac{1}{2}\)).

outputFormat

Output the expected number of subrectangles which are entirely Drag, modulo \(998244353\).

sample

1 1
?

499122177