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