Problema
JOI-kun frequenta la $1$-a classe della scuola elementare. A JOI-kun piacciono moltissimo l'addizione e la sottrazione che ha appena imparato e, ogni volta che vede una sequenza di cifre allineate, gioca a costruire un'uguaglianza inserendo = tra le ultime $2$ cifre e inserendo sempre + oppure - tra le restanti cifre adiacenti. Ad esempio, da 8 3 2 4 8 7 2 4 0 8 8 può costruire l'uguaglianza 8+3-2-4+8-7-2-4-0+8=8.
Dopo aver costruito un'uguaglianza, JOI-kun esegue il calcolo per verificare se si tratta di un'uguaglianza corretta. Tuttavia, JOI-kun non conosce ancora i numeri negativi e non è in grado di calcolare numeri superiori a $20$. Pertanto, tra le uguaglianze corrette, solo quelle in cui, calcolando il membro sinistro da sinistra verso destra, tutti i numeri che compaiono durante il calcolo sono maggiori o uguali a $0$ e minori o uguali a $20$ sono uguaglianze corrette che JOI-kun può verificare. Ad esempio, 8+3-2-4-8-7+2+4+0+8=8 è un'uguaglianza corretta, ma poiché 8+3-2-4-8, che compare durante il calcolo, è un numero negativo, JOI-kun non può verificare se questa uguaglianza sia corretta.
Data in input una sequenza di cifre, scrivi un programma per trovare il numero di uguaglianze corrette che JOI-kun può costruire e verificare.
Input
Il file di input è composto da $2$ righe. Nella $1$-a riga è scritto un intero $N$ ($3 \le N \le 100$) che rappresenta il numero di cifre allineate. Nella $2$-a riga sono scritti $N$ interi maggiori o uguali a $0$ e minori o uguali a $9$, separati da spazi.
Nel $60\%$ dei dati di input forniti, il numero di uguaglianze corrette che JOI-kun può costruire e verificare non supera $2^{31}-1$. Inoltre, in tutti i dati di input forniti, il numero di uguaglianze corrette che JOI-kun può costruire e verificare non supera $2^{63}-1$.
Output
Stampa su $1$ riga un intero che rappresenta il numero di uguaglianze corrette che JOI-kun può costruire e verificare.
Esempi di input/output
Esempio di input 1
11 8 3 2 4 8 7 2 4 0 8 8
Esempio di output 1
10
Esempio di input 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
Esempio di output 2
7069052760
Nell'Esempio di input $1$, JOI-kun può costruire e verificare le seguenti $10$ uguaglianze corrette:
8+3-2-4+8-7-2-4-0+8=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-3+2-4+8+7+2-4+0-8=8
Pertanto, stampa $10$.
Nell'Esempio di input $2$, fai attenzione al fatto che la risposta non rientra nell'intervallo degli interi con segno a $32$ bit.
(Aggiunta del giorno $21$ del mese $2$ del $2015$) Su segnalazione di un utente, è emerso un errore tra le uguaglianze nella spiegazione dell'Esempio di input $1$. Ora è stato corretto. La $5$-a uguaglianza era 8+3-2-4+8-7+2+4-0-8=8, ed è stata corretta in 8+3+2-4+8-7+2+4-0-8=8. Inoltre, la $6$-a uguaglianza era 8+3-2-4+8-7+2+4+0-8=8, ed è stata corretta in 8+3+2-4+8-7+2+4+0-8=8.