ABABABA2026

Описание задачи

В алфавите есть только две буквы: A и B.

Рассматриваются строки длины $n$, состоящие только из этих букв.

Строка называется правильной, если выполняются все условия:

• первая и последняя буквы --- A;
• в строке нет двух букв A, идущих подряд (подстрока AA запрещена);
• в строке нет трёх букв B, идущих подряд (подстрока BBB запрещена).

Например, строки ABBA, ABABABA, ABBABABBA являются правильными, а строки ABBAB, ABAABA, ABABBBA --- нет.

Требуется найти количество правильных строк длины $n$.

Входные данные

В первой строке задано одно целое число $n$ $(4 \le n \le 10^6)$ --- длина строки.

Выходные данные

Выведите количество правильных строк длины $n$ по модулю $998244353$.

Система оценки

4

1

6

2