У вас есть большая прямоугольная доска, разделенная на \(n \times m\) клетка (у доски \(n\) строк и \(m\) столбцов). Каждая клетка — либо белая, либо черная.
Вы красите каждую белую клетку либо в красный цвет, либо в синий. Очевидно, количество различных вариантов раскраски доски равно \(2^w\), где \(w\) — количество белых клеток.
После перекрашивания всех белых клеток вы начинаете класть на доску доминошки по следующим правилам:
- каждая доминошка накрывает две соседние клетки;
- каждая клетка накрыта не более чем одной доминошкой;
- если доминошка расположена горизонтально (она накрывает две соседние клетки в строке), обе накрытые ею клетки должны быть красными;
- если доминошка расположена вертикально (она накрывает две соседние клетки в столбце), обе накрытые ею клетки должны быть синими.
Пусть ценность раскраски доски — максимальное количество доминошек, которое можно расположить. Посчитайте сумму ценностей по всем \(2^w\) способам раскрасить доску. Так как сумма может быть очень большой, выведите ее по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — сумму ценностей по всем \(2^w\) способам раскрасить доску, взятую по модулю \(998\,244\,353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
**oo
oo*o
**oo
|
144
|
|
2
|
3 4
**oo
oo**
**oo
|
48
|
|
3
|
2 2
oo
o*
|
4
|
|
4
|
1 4
oooo
|
9
|