_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:

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*.

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

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

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

h2. Restricţii

* $1 ≤ N ≤ 10^5^$
* $1 ≤ v{~i~} ≤ 200$ pentru $1 ≤ i ≤ N$

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

h2. Subtask 1 (10 puncte)

h2. $Subtask 1 (10 puncte)$

* $N = 1$

* <tex>N = 1</tex>

h2. Subtask 2 (15 puncte)

h2. $Subtask 2 (15 puncte)$

* Suma v[i] <= 20

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

h2. Subtask 3 (20 de puncte)

h2. $Subtask 3 (20 de puncte)$

* $N ≤ 10$

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

h2. Subtask 4 (25 de puncte)

h2. $Subtask 4 (25 de puncte)$

* $v{~i~} ≤ 10$

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

h2. Subtask 5 (30 de puncte)

h2. $Subtask 5 (30 de puncte)$
 
* $Fara restrictii suplimentare.$

* Fara restrictii suplimentare.

h2. Exemplu

h3. Exemplul 1

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

Configuratia din exemplu o reprezinta sirul de biti $000$. 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:

Configuratia din exemplu o reprezinta sirul de biti $001110$. 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") ==