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