Colorings and Dominoes

题意翻译

你有一个大矩形板子分成了 $n \times m$ 个格子，每个格子上的颜色为黑色(`*`)和白色(`o`) 你可以给每个白色格子染成红色或蓝色，那么显然有 $2^w$种染色方案（$w$ 为白色格子数量） 对于每一种染色方案，你要尽可能往上放大小为 $1\times2$ 的多米诺骨牌，规则是： - 横着的骨牌必须在两个红色格子上 - 竖着的骨牌必须在两个蓝色格子上 现在想要计算 **“每种涂色方案的最多骨牌摆放数量”之和**。 这个数可能非常大，输出对 $998\,244\,353$ 取余后的结果即可。

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3 4
**oo
oo*o
**oo

输出样例 #1

144

输入样例 #2

3 4
**oo
oo**
**oo

输出样例 #2

48

输入样例 #3

2 2
oo
o*

输出样例 #3

4

输入样例 #4

1 4
oooo

输出样例 #4

9