Verkefni

JOI-kun er í $1$. bekk í grunnskóla. JOI-kun hefur mjög gaman af samlagningu og frádrætti sem hann var nýbúinn að læra, og þegar hann sér runu af tölustöfum í röð leikur hann sér að því að búa til jöfnu með því að setja = á milli síðustu $2$ tölustafanna og setja alltaf + eða - á milli hinna aðliggjandi tölustafanna. Til dæmis getur hann búið til jöfnuna 8+3-2-4+8-7-2-4-0+8=8 úr 8 3 2 4 8 7 2 4 0 8 8.

Eftir að JOI-kun hefur búið til jöfnu reiknar hann hana út til að ganga úr skugga um hvort hún sé rétt jafna. Hins vegar þekkir JOI-kun ekki enn neikvæðar tölur og hann getur ekki reiknað með tölum sem eru hærri en $20$. Þess vegna eru, af réttum jöfnum, aðeins þær jöfnur þar sem allar tölur sem koma fyrir í útreikningnum þegar vinstri hliðin er reiknuð frá vinstri til hægri eru að minnsta kosti $0$ og í mesta lagi $20$ réttar jöfnur sem JOI-kun getur sannreynt. Til dæmis er 8+3-2-4-8-7+2+4+0+8=8 rétt jafna, en þar sem 8+3-2-4-8 sem kemur fyrir í miðjum útreikningi er neikvæð tala getur JOI-kun ekki sannreynt hvort þessi jafna sé rétt.

Þegar runa af tölustöfum er gefin sem inntak, skrifið forrit til að finna fjölda réttra jafna sem JOI-kun getur búið til og sannreynt.

Inntak

Inntaksskráin samanstendur af $2$ línum. Í $1$. línu er heiltala $N$ ($3 \le N \le 100$) sem táknar fjölda tölustafa í röðinni. Í $2$. línu eru $N$ heiltölur sem eru að minnsta kosti $0$ og í mesta lagi $9$, aðskildar með bilum.

Í $60\%$ af gefnum inntaksgögnum fer fjöldi réttra jafna sem JOI-kun getur búið til og sannreynt ekki yfir $2^{31}-1$. Einnig fer fjöldi réttra jafna sem JOI-kun getur búið til og sannreynt ekki yfir $2^{63}-1$ í öllum gefnum inntaksgögnum.

Úttak

Skrifið út í $1$ línu heiltölu sem táknar fjölda réttra jafna sem JOI-kun getur búið til og sannreynt.

Dæmi um inntak og úttak

Inntaksdæmi 1

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

Úttaksdæmi 1

10

Inntaksdæmi 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

Úttaksdæmi 2

7069052760

Í Inntaksdæmi $1$ getur JOI-kun búið til og sannreynt eftirfarandi $10$ réttar jöfnur:

• 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

Því er $10$ skrifað út.

Í Inntaksdæmi $2$ skal athuga að svarið rúmast ekki innan sviðs $32$-bita heiltölu með formerki.

(Viðbót $21$. $2$. $2015$) Vegna ábendingar frá notanda kom í ljós að villa var í jöfnunum í skýringunni við Inntaksdæmi $1$. Búið er að leiðrétta hana. $5$. jafnan var 8+3-2-4+8-7+2+4-0-8=8, en henni var breytt í 8+3+2-4+8-7+2+4-0-8=8. Einnig var $6$. jafnan 8+3-2-4+8-7+2+4+0-8=8, en henni var breytt í 8+3+2-4+8-7+2+4+0-8=8.