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