!{margin: 10px}>problema/pwca?HotWings.png!

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

_Agent P., plictisit de algoritmi de cuplaj in O(N) cu rucsac random si de interactive de geometrie, 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{~1~}$ aripioare necondimentate, a doua secventa sa contina $v{~2~}$ aripioare condimentate, a treia secventa sa contina $v{~3~}$ aripioare necondimentate etc."_
 
Bucatarul 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 care pot fi transformate astfel incat sa obtina comanda finala a Doctorului Doofenshmirtz.

Poveste şi cerinţă...

h2. Date de intrare