E. Раскраски и домино
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть большая прямоугольная доска, разделенная на $$$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$$$ символов. Символ под номером $$$j$$$ в $$$i$$$-й последовательности — *, если $$$j$$$-я клетка $$$i$$$-й строки черная; иначе этот символ — o.

Выходные данные

Выведите одно целое число — сумму ценностей по всем $$$2^w$$$ способам раскрасить доску, взятую по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3 4
**oo
oo*o
**oo
Выходные данные
144
Входные данные
3 4
**oo
oo**
**oo
Выходные данные
48
Входные данные
2 2
oo
o*
Выходные данные
4
Входные данные
1 4
oooo
Выходные данные
9