Fişierul intrare/ieşire:	pwca.in, pwca.out	Sursă	Junior Challenge 2021
Autor	Alexandru Luchianov, Mihai-Cristian Popescu	Adăugată de	Comisia •jc2021
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

PWCA

Agent P., plictisit de interactive de geometrie si de algoritmi de cuplaj in O(N) cu rucsac random, a demisionat de la Organizatia Fara Acronim Cool si s-a apucat de compus Probleme Cu Acronim Cool.

Doctorul Heinz Doofenshmirtz lucra la un nou inator, cand i s-a facut foame si s-a gandit sa comande prin FoodPlatypus niste aripioare picante de pui. Aripioarele de pui pot fi de 2 tipuri: condimentate (codificate prin 1) sau necondimentate (codificate prin 0). Comanda sa prin FoodPlatypus are urmatoarele instructiuni:

"Vreau sa primesc un sir de aripioare, impartit in N secvente alternante. Astfel, prima secventa sa contina v₁ aripioare necondimentate, a doua secventa sa contina v₂ aripioare condimentate, a treia secventa sa contina v₃ aripioare necondimentate etc."

Patronul firmei, renumitul bucatar Gordon Ramsay are acum un sir de aripioare de pui in fata lui, unele condimentate, altele nu. El defineste o subsecventa picanta maximala ca fiind o subsecventa formata din aripioare de acelasi tip care nu se poate extinde la stanga sau la dreapta. La un pas, el poate schimba tipul unei subsecvente picante maximale daca si numai aceasta are langa ea o alta subsecventa picanta maximala de lungime mai mare sau egala ca ea. Fiind in secret pasionat de probleme de algoritmica, el se intreaba care este numarul total de configuratii initiale de aripioare pe care le poate avea astfel incat, aplicand operatia de mai sus de oricate ori vrea, sa poata obtina comanda finala a Doctorului Doofenshmirtz. Fiind insa prea ocupat cu prepararea comenzii si insultarea angajatilor lui, va intreaba pe voi care este acest numar, modulo 998244353.

Date de intrare

Fişierul de intrare pwca.in va contine pe prima linie numarul natural N reprezentand numarul de secvente. Urmatoarea linie va contine N numere v₁, v₂, ..., v_N reprezentand comanda de aripioare a Doctorului Doofenshmirtz.

Date de ieşire

În fişierul de ieşire pwca.out se va afisa numarul de configuratii initiale cautat, modulo 998244353.

Restricţii

• 1 ≤ N ≤ 10⁵
• 1 ≤ v_i ≤ 200 pentru 1 ≤ i ≤ N

Subtask 1 (10 puncte)

• N = 1

Subtask 2 (15 puncte)

• Suma v[i] <= 20

Subtask 3 (20 de puncte)

• N ≤ 10

Subtask 4 (25 de puncte)

• v_i ≤ 10

Subtask 5 (30 de puncte)

• Fara restrictii suplimentare.

Exemplu

Explicaţie

Exemplul 1

Configuratia din exemplu o reprezinta sirul de biti 000. Acesta poate fi obtinut din urmatoarele configuratii:

• 000
• 111 -> 000
• 100 -> 000
• 010 -> 000
• 001 -> 000

Exemplul 2

Configuratia din exemplu o reprezinta sirul de biti 001110. Acesta poate fi obtinut din urmatoarele configuratii:

• 001110
• 101110 -> 001110
• 001010 -> 001110
• 101010 -> 001010 -> 001110

Cum se trimit solutii?