У вас есть большая прямоугольная доска, разделенная на $$$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
Название |
---|