ABABABA2026

Masala tavsifi

Alifboda faqat ikkita harf mavjud: A va B.

Faqat ushbu harflardan iborat $n$ uzunlikdagi satrlar ko'rib chiqiladi.

Satr to'g'ri deb ataladi, agar quyidagi barcha shartlar bajarilsa:

• birinchi va oxirgi harflar --- A;
• satrda ketma-ket ikkita A harfi yo'q (sub-satr AA taqiqlangan);
• satrda ketma-ket uchta B harfi yo'q (sub-satr BBB taqiqlangan).

Masalan, ABBA, ABABABA, ABBABABBA to'g'ri, ABBAB, ABAABA, ABABBBA esa to'g'ri emas.

$n$ uzunlikdagi to'g'ri satrlar sonini topish talab qilinadi.

Kirish ma'lumotlari

Birinchi satrda bitta butun son $n$ $(4 \le n \le 10^6)$ --- satr uzunligi.

Chiqish ma'lumotlari

$n$ uzunlikdagi to'g'ri satrlar sonini $998244353$ ga modulyatsiya qilingan holda chiqarilsin.

Baholash tizimi

4

1

6

2