你有一个大的矩形板,它分为 $$$n \times m$$$ 个单元格(板有 $$$n$$$ 行和 $$$m$$$ 列)。每个单元格要么是白色的,要么是黑色的。
将每个白色单元格涂成红色或蓝色。显然,绘制它们的不同方式的数量为$$$2^w$$$,其中$$$w$$$是白色单元格的数量。
绘制板上的白色单元格后,您要根据以下规则在其上放置最大数量的多米诺骨牌:
- 每个多米诺骨牌覆盖两个相邻的单元格;
- 每个单元最多被一个多米诺骨牌覆盖;
- 如果多米诺骨牌水平放置(它覆盖其中一行中的两个相邻单元格),它应该只覆盖红色单元格;
- 如果多米诺骨牌垂直放置(它覆盖其中一列中的两个相邻单元格),它应该只覆盖蓝色单元格。
让棋盘的值为您可以放置的多米诺骨牌的最大数量。计算所有 $$$2^w$$$ 可能的绘制方法的板值总和。因为它可能很大,所以打印它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$; $$$nm \le 3 \cdot 10^5$$$) — 分别是行数和列数。
接下来是 $$$n$$$ 行,每行包含 $$$m$$$ 个字符的字符串。如果第 $$$i$$$ 行中的第 $$$j$$$ 单元格为黑色,则第 $$$i$$$ 字符串中的第 $$$j$$$ 字符为 *;否则,该字符为 o。
输出
打印一个整数 — 棋盘上所有 $$$2^w$$$ 可能的绘制方式的值之和,以 $$$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