Minesweeper State Configurations

In this problem, you are given an n × m grid representing a simplified Minesweeper board. Each cell is either a mine (denoted by '*') or an empty cell (denoted by '.'). The game rules are as follows:

• The connectivity is defined using 8-connected components.
• If a mine is opened (clicked), all mines explode simultaneously and the game immediately ends.
• If an empty cell is opened and it has no adjacent mines, then it recursively opens all of the eight neighbors.
• As shown in the figure, clicking any cell in the red-bordered region produces the current board state.

Every cell has two possible states:

• If the cell is a mine, it can be exploded or not exploded.
• If the cell is empty, it can be either open or closed.

Two board states are considered different if and only if there exists at least one cell whose state differs between the two boards.

To determine the size of the arrays, you need to count the number of distinct board states modulo \(998244353\). However, note that empty cells that have no adjacent mines (zero cells) obey a special rule: if one zero cell in a connected (8-connected) component is open then all zero cells in that component must be open. (Otherwise, they can all be closed.) Meanwhile, empty cells that are adjacent to at least one mine can be opened independently.

Thus, if we denote:

• \(M\) = number of mine cells,
• \(N\) = number of empty cells that are adjacent to at least one mine,
• \(Z\) = number of connected components formed by zero cells (empty cells with no adjacent mines),

the total number of distinct configurations is given by:

[ 2^{M + N + Z} \pmod{998244353} ]

You are guaranteed that \(Z \le 37\).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of rows and columns.

Each of the following \(n\) lines contains a string of length \(m\) consisting of characters '*' (mine) and '.' (empty).

outputFormat

Output a single integer, the number of different possible configurations modulo \(998244353\).

sample

2 2
*.
..

16