Дана квадратная доска, состоящая из \(n\) строк и \(n\) столбцов. Каждая клетка в ней должна быть раскрашена либо в белый, либо в черный цвет.
Назовем некоторую раскраску красивой, если каждая пара соседних строк либо совпадает полностью, либо отличается в каждой позиции. Такое же условие накладывается и на столбцы.
Назовем некоторую раскраску подходящей, если она красивая, и в ней нет ни одного прямоугольника одного цвета, состоящего не менее чем из \(k\) клеток.
Ваша задача — подсчитать количество подходящих раскрасок доски заданного размера.
Так как ответ может быть достаточно большим, выведите его по модулю \(998244353\).
Выходные данные
Выведите единственное целое число — количество подходящих раскрасок доски заданного размера по модулю \(998244353\).
Примечание
Доска размера \(1 \times 1\) — это либо единственная черная клетка, либо единственная белая клетка. Обе доски включают в себя прямоугольник одного цвета, состоящий из \(1\) клетки.
Вот красивые раскраски доски размера \(2 \times 2\), которые не включают в себя прямоугольники одного цвета, состоящие не менее чем из \(3\) клеток:
Оставшиеся красивые раскраски доски \(2 \times 2\):
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
|
0
|
|
2
|
2 3
|
6
|
|
3
|
49 1808
|
359087121
|