CF1511E.Colorings and Dominoes

You have a large rectangular board which is divided into $n \times m$ cells (the board has $n$ rows and $m$ columns). Each cell is either white or black.

You paint each white cell either red or blue. Obviously, the number of different ways to paint them is $2^w$, where $w$ is the number of white cells.

After painting the white cells of the board, you want to place the maximum number of dominoes on it, according to the following rules:

• each domino covers two adjacent cells;
• each cell is covered by at most one domino;
• if a domino is placed horizontally (it covers two adjacent cells in one of the rows), it should cover only red cells;
• if a domino is placed vertically (it covers two adjacent cells in one of the columns), it should cover only blue cells.

Let the value of the board be the maximum number of dominoes you can place. Calculate the sum of values of the board over all $2^w$ possible ways to paint it. Since it can be huge, print it modulo $998\,244\,353$.

你有一个大型矩形棋盘，被划分为 $n \times m$ 个格子（棋盘有 $n$ 行和 $m$ 列）。每个格子要么是白色，要么是黑色。

你需要将每个白色格子涂成红色或蓝色。显然，涂色方案总数为 $2^w$，其中 $w$ 是白色格子的数量。

在将所有白色格子涂色后，你希望按照以下规则在棋盘上放置尽可能多的多米诺骨牌（domino）：

• 每个多米诺骨牌覆盖两个相邻的格子；
• 每个格子至多被一个多米诺骨牌覆盖；
• 若多米诺骨牌水平放置（即覆盖某一行中两个相邻格子），则它必须只覆盖红色格子；
• 若多米诺骨牌垂直放置（即覆盖某一列中两个相邻格子），则它必须只覆盖蓝色格子。

定义该棋盘的价值为所能放置的最多多米诺骨牌数量。请计算该棋盘在全部 $2^w$ 种涂色方案下的价值之和。由于结果可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 3 \cdot 10^5$; $nm \le 3 \cdot 10^5$) — the number of rows and columns, respectively.

Then $n$ lines follow, each line contains a string of $m$ characters. The $j$-th character in the $i$-th string is * if the $j$-th cell in the $i$-th row is black; otherwise, that character is o.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3 \cdot 10^5$；$nm \le 3 \cdot 10^5$），分别表示行数和列数。

接下来是 $n$ 行，每行包含一个长度为 $m$ 的字符串。第 $i$ 行字符串中的第 $j$ 个字符为 *，表示第 $i$ 行第 $j$ 列的格子是黑色的；否则该字符为 o。

Print one integer — the sum of values of the board over all $2^w$ possible ways to paint it, taken modulo $998\,244\,353$.

输出一个整数——在所有 $2^w$ 种可能的涂色方案下，棋盘的值之和，对 $998\,244\,353$ 取模。