Oppgave

JOI-kun går i $1$. klasse på barneskolen. JOI-kun elsker addisjon og subtraksjon som han nettopp har lært, og når han ser en rekke med sifre, leker han ved å sette inn = mellom de siste $2$ sifrene og alltid sette inn + eller - mellom de resterende nabosifrene for å lage en ligning. For eksempel, fra 8 3 2 4 8 7 2 4 0 8 8 kan han lage ligningen 8+3-2-4+8-7-2-4-0+8=8.

Etter å ha laget en ligning, regner JOI-kun den ut for å sjekke om det er en gyldig ligning. JOI-kun kjenner imidlertid ennå ikke til negative tall, og han kan ikke regne med tall som overstiger $20$. Blant de gyldige ligningene er det derfor bare de der alle tallene som dukker opp under utregningen når venstresiden regnes ut fra venstre mot høyre er minst $0$ og høyst $20$, som JOI-kun kan bekrefte. For eksempel er 8+3-2-4-8-7+2+4+0+8=8 en gyldig ligning, men siden 8+3-2-4-8 som dukker opp midt i utregningen er et negativt tall, kan ikke JOI-kun bekrefte om denne ligningen er gyldig.

Gitt en rekke med sifre som inndata, skriv et program som finner antallet gyldige ligninger som JOI-kun kan lage og bekrefte.

Inndata

Inndatafilen består av $2$ linjer. Den $1$. linjen inneholder et heltall $N$ ($3 \le N \le 100$) som representerer antallet oppstilte sifre. Den $2$. linjen inneholder $N$ heltall som er minst $0$ og høyst $9$, atskilt med mellomrom.

I $60\%$ av de gitte inndataene overstiger ikke antallet gyldige ligninger som JOI-kun kan lage og bekrefte $2^{31}-1$. Dessuten overstiger ikke antallet gyldige ligninger som JOI-kun kan lage og bekrefte $2^{63}-1$ i noen av de gitte inndataene.

Utdata

Skriv ut på $1$ linje et heltall som representerer antallet gyldige ligninger som JOI-kun kan lage og bekrefte.

Eksempler på inndata og utdata

Eksempel på inndata 1

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

Eksempel på utdata 1

10

Eksempel på inndata 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

Eksempel på utdata 2

7069052760

I Eksempel på inndata $1$ kan JOI-kun lage og bekrefte følgende $10$ gyldige ligninger:

• 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

Derfor skrives det ut $10$.

Merk at i Eksempel på inndata $2$ får ikke svaret plass innenfor rekkevidden til et $32$-bits heltall med fortegn.

(Tilføyelse $21$.$2$.$2015$) Etter tilbakemelding fra en bruker viste det seg at det var en feil blant ligningene i forklaringen til Eksempel på inndata $1$. Dette er nå rettet. Den $5$. ligningen var 8+3-2-4+8-7+2+4-0-8=8, men er rettet til 8+3+2-4+8-7+2+4-0-8=8. Videre var den $6$. ligningen 8+3-2-4+8-7+2+4+0-8=8, men er rettet til 8+3+2-4+8-7+2+4+0-8=8.