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_ <tex>N</tex> _secvente alternante. Astfel, prima secventa sa contina_ <tex>v_1_</tex> _aripioare $necondimentate$, a doua secventa sa contina_ <tex>v_2_</tex> _aripioare $condimentate$, a treia secventa sa contina_ <tex>v_3_</tex> _aripioare $necondimentate$ etc."_

_"Vreau sa primesc un sir de aripioare, impartit in_ $N$ _secvente alternante. Astfel, prima secventa sa contina_ $V{~1~}$ _aripioare $necondimentate$, a doua secventa sa contina_ $V{_2_}$ _aripioare $condimentate$, a treia secventa sa contina_ $v{~3~}$ _aripioare $necondimentate$ etc."_

Patronul firmei, renumitul bucatar 'Gordon Ramsay':problema/gordonramsay 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*.
h2. Date de intrare

Fişierul de intrare $pwca.in$ va contine pe prima linie numarul natural <tex>N</tex> reprezentand numarul de secvente. Urmatoarea linie va contine <tex>N</tex> numere <tex>v_1_, v_2_, ..., v_N_</tex> reprezentand comanda de aripioare a Doctorului Doofenshmirtz.

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{~1~}, V{~2~}, ..., V{~N~}$ reprezentand comanda de aripioare a Doctorului Doofenshmirtz.

h2. Date de ieşire

* <tex>1 \leq N \leq 10^5</tex>
* <tex>1 \leq v_{i} \leq 200</tex>

h2. $Subtask 1 (10 puncte)$

h3. $Subtask 1 (10 puncte)$

* <tex>N = 1</tex>

h2. $Subtask 2 (15 puncte)$

h3. $Subtask 2 (15 puncte)$

* <tex>\sum_{i = 1}^{n} v_i \leq 20</tex>

h2. $Subtask 3 (20 de puncte)$

h3. $Subtask 3 (20 de puncte)$

* <tex>N \leq 10</tex>

h2. $Subtask 4 (25 de puncte)$

h3. $Subtask 4 (25 de puncte)$

* <tex>v_i \leq 10</tex>

h2. $Subtask 5 (30 de puncte)$

h3. $Subtask 5 (30 de puncte)$

* $Fara restrictii suplimentare.$

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

* <tex>000</tex>
* <tex>111 \rightarrow 000</tex>
* <tex>100\rightarrow 000</tex>
* <tex>010\rightarrow 000</tex>
* <tex>001\rightarrow 000</tex>

* $000$
* $111$ → $000$
* $100$ → $000$
* $010$ → $000$
* $001$ → $000$

h3. Exemplul 2
Configuratia din exemplu o reprezinta sirul de biti <tex>001110</tex>. Acesta poate fi obtinut din urmatoarele configuratii:

* <tex>001110</tex>
* <tex>101110\rightarrow 001110</tex>
* <tex>001010\rightarrow 001110</tex>
* <tex>101010\rightarrow 001010\rightarrow 001110</tex>

* $001110$
* $101110$ → $001110$
* $001010$ → $001110$
* $101010$ → $001010$ → $001110$

== include(page="template/taskfooter" task_id="pwca") ==