== include(page="template/taskheader" task_id="pwca") ==
!{margin: 10px}>problema/pwca?HotWings.png!
_Agent P., plictisit de interactive de geometrie şi de algoritmi de cuplaj în $O(N)$ cu rucsac random, a demisionat de la Organizaţia Fără Acronim Cool şi s-a apucat de compus Probleme Cu Acronim Cool._
Doctorul Heinz Doofenshmirtz lucra la un nou inator, când i s-a făcut foame şi s-a gândit să comande prin _FoodPlatypus_ nişte 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 următoarele instrucţiuni:
_"Vreau să primesc un şir de aripioare, împărţit în $N$ secvenţe alternante. Astfel, prima secvenţă să conţină $V{~1~}$ aripioare $necondimentate$, a doua secvenţă să conţină $V{~2~}$ aripioare $condimentate$, a treia secvenţă să conţină $v{~3~}$ aripioare $necondimentate$ etc."_
Patronul firmei, renumitul bucătar 'Gordon Ramsay':problema/gordonramsay are acum un şir de aripioare de pui în faţa lui, unele $condimentate$, altele nu. El defineşte o $subsecvenţă picantă maximală$ ca fiind o subsecvenţă formată din aripioare de acelaşi tip care nu se poate extinde la stânga sau la dreapta. La un pas, el poate schimba tipul unei $subsecvenţe picante maximale$ dacă şi numai dacă aceasta are lângă ea o altă $subsecvenţă picantă maximală$ de lungime mai mare sau egală ca ea. Fiind în secret pasionat de probleme de algoritmică, el se întreabă care este numărul total de configuraţii iniţiale de aripioare pe care le poate avea astfel încât, aplicând operaţia de mai sus de oricâte ori vrea, să poată obţine comanda finală a Doctorului Doofenshmirtz. Fiind însă prea ocupat cu prepararea comenzii şi insultarea angajaţilor, vă întreabă pe voi care este acest număr, *modulo 998244353*.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $pwca.in$ va conţine pe prima linie numărul natural $N$ reprezentând numărul de secvenţe. Următoarea linie va conţine $N$ numere $V{~1~}, V{~2~}, ..., V{~N~}$ reprezentând comanda de aripioare a Doctorului Doofenshmirtz.
Fişierul de intrare $pwca.in$ ...
h2. Date de ieşire
În fişierul de ieşire $pwca.out$ se va afişa numărul de configuraţii iniţiale căutat, *modulo 998244353*.
În fişierul de ieşire $pwca.out$ ...
h2. Restricţii
* <tex>1 \leq N \leq 10^5</tex>
* <tex>1 \leq v_{i} \leq 200</tex>
h3. $Subtask 1 (10 puncte)$
* <tex>\sum_{i = 1}^{n} v_i \leq 15 </tex>
h3. $Subtask 2 (20 puncte)$
* <tex>v_i \leq 15 </tex>
h3. $Subtask 3 (30 de puncte)$
* <tex> N = 1 </tex>
h3. $Subtask 4 (40 de puncte)$
* $Fără restricţii suplimentare.$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. pwca.in |_. pwca.out |
| 1
3
| 5 |
| 3
2 3 1
| 4
|
| 1
15
| 30626
|
h2. Explicaţie
h3. Exemplul 1
Configuraţia din exemplu o reprezintă şirul de biti $000$. Acesta poate fi obţinut din următoarele configuraţii:
* $000$
* $100$ → $000$
* $010$ → $000$
* $001$ → $000$
* $101$ → $100$ → $000$
h3. Exemplul 2
Configuraţia din exemplu o reprezintă şirul de biti $001110$. Acesta poate fi obţinut din următoarele configuraţii:
* $001110$
* $101110$ → $001110$
* $001010$ → $001110$
* $101010$ → $001010$ → $001110$
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="pwca") ==
