Tehtävänanto

JOI-kun on alakoulun $1$. luokalla. JOI-kun pitää kovasti juuri oppimistaan yhteen- ja vähennyslaskuista, ja nähdessään numeroita rivissä hän leikkii muodostamalla yhtälön laittamalla merkin = viimeisen $2$ numeron väliin ja laittamalla muiden vierekkäisten numeroiden väliin aina merkin + tai -. Esimerkiksi lukujonosta 8 3 2 4 8 7 2 4 0 8 8 voidaan muodostaa yhtälö 8+3-2-4+8-7-2-4-0+8=8.

Muodostettuaan yhtälön JOI-kun laskee sen tarkistaakseen, onko se oikea yhtälö. JOI-kun ei kuitenkaan vielä tunne negatiivisia lukuja eikä osaa laskea luvuilla, jotka ylittävät luvun $20$. Näin ollen oikeista yhtälöistä vain ne, joissa yhtälön vasenta puolta vasemmalta oikealle laskettaessa kaikki laskun aikana esiintyvät luvut ovat vähintään $0$ ja enintään $20$, ovat sellaisia oikeita yhtälöitä, jotka JOI-kun pystyy varmistamaan. Esimerkiksi 8+3-2-4-8-7+2+4+0+8=8 on oikea yhtälö, mutta koska laskun aikana esiintyvä 8+3-2-4-8 on negatiivinen luku, JOI-kun ei pysty varmistamaan, onko tämä yhtälö oikea.

Kun syötteenä annetaan numerojono, kirjoita ohjelma, joka selvittää, kuinka monta oikeaa yhtälöä JOI-kun voi muodostaa ja varmistaa.

Syöte

Syötetiedosto koostuu $2$ rivistä. $1$. rivillä on kokonaisluku $N$ ($3 \le N \le 100$), joka ilmaisee rivissä olevien numeroiden lukumäärän. $2$. rivillä on $N$ välilyönnein erotettua kokonaislukua, jotka ovat vähintään $0$ ja enintään $9$.

$60\%$:ssa annetusta syötedatasta JOI-kunin muodostamien ja varmistamien oikeiden yhtälöiden lukumäärä on enintään $2^{31}-1$. Lisäksi kaikessa annetussa syötedatassa JOI-kunin muodostamien ja varmistamien oikeiden yhtälöiden lukumäärä on enintään $2^{63}-1$.

Tuloste

Tulosta $1$ riville kokonaisluku, joka ilmaisee JOI-kunin muodostamien ja varmistamien oikeiden yhtälöiden lukumäärän.

Esimerkkisyötteet ja -tulosteet

Esimerkkisyöte 1

11
8 3 2 4 8 7 2 4 0 8 8

Esimerkkituloste 1

10

Esimerkkisyöte 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

Esimerkkituloste 2

7069052760

Esimerkkisyötteessä $1$ JOI-kun voi muodostaa ja varmistaa seuraavat $10$ oikeaa yhtälöä:

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

Siispä tulostetaan $10$.

Huomaa, että esimerkkisyötteessä $2$ vastaus ei mahdu $32$-bittisen etumerkillisen kokonaisluvun arvoalueelle.

(Lisäys $21$.$2$.$2015$) Käyttäjän huomautuksen perusteella kävi ilmi, että esimerkkisyötteen $1$ selityksen yhtälöissä oli virhe. Se on nyt korjattu. $5$. yhtälö oli 8+3-2-4+8-7+2+4-0-8=8, ja se on korjattu muotoon 8+3+2-4+8-7+2+4-0-8=8. Lisäksi $6$. yhtälö oli 8+3-2-4+8-7+2+4+0-8=8, ja se on korjattu muotoon 8+3+2-4+8-7+2+4+0-8=8.