Uppgift

JOI-kun går i $1$:a klass i grundskolan. JOI-kun älskar addition och subtraktion som han precis har lärt sig, och när han ser en rad med siffror leker han genom att sätta in = mellan de sista $2$ siffrorna och alltid sätta in + eller - mellan de återstående intilliggande siffrorna för att bilda en ekvation. Till exempel, från 8 3 2 4 8 7 2 4 0 8 8 kan han bilda ekvationen 8+3-2-4+8-7-2-4-0+8=8.

Efter att ha bildat en ekvation räknar JOI-kun ut den för att kontrollera om det är en giltig ekvation. JOI-kun känner dock ännu inte till negativa tal, och han kan inte räkna med tal som överstiger $20$. Bland de giltiga ekvationerna är det därför endast de där alla tal som dyker upp under uträkningen när vänsterledet beräknas från vänster till höger är minst $0$ och högst $20$ som JOI-kun kan kontrollera. Till exempel är 8+3-2-4-8-7+2+4+0+8=8 en giltig ekvation, men eftersom 8+3-2-4-8 som dyker upp mitt i uträkningen är ett negativt tal kan JOI-kun inte kontrollera om denna ekvation är giltig.

Givet en sekvens av siffror som indata, skriv ett program som bestämmer antalet giltiga ekvationer som JOI-kun kan bilda och kontrollera.

Indata

Indatafilen består av $2$ rader. Den $1$:a raden innehåller ett heltal $N$ ($3 \le N \le 100$) som anger antalet uppradade siffror. Den $2$:a raden innehåller $N$ heltal som är minst $0$ och högst $9$, åtskilda av mellanslag.

I $60\%$ av given indata överstiger antalet giltiga ekvationer som JOI-kun kan bilda och kontrollera inte $2^{31}-1$. Dessutom överstiger antalet giltiga ekvationer som JOI-kun kan bilda och kontrollera i all given indata inte $2^{63}-1$.

Utdata

Skriv ut på $1$ rad ett heltal som anger antalet giltiga ekvationer som JOI-kun kan bilda och kontrollera.

Exempel på indata och utdata

Exempel på indata 1

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

Exempel på utdata 1

10

Exempel på indata 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

Exempel på utdata 2

7069052760

I Exempel på indata $1$ kan JOI-kun bilda och kontrollera följande $10$ giltiga ekvationer:

• 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

Därför skrivs $10$ ut.

Observera att i Exempel på indata $2$ ryms svaret inte inom intervallet för ett $32$-bitars heltal med tecken.

(Tillägg den $21$/$2$ $2015$) Efter påpekande från en användare visade det sig att det fanns ett fel bland ekvationerna i förklaringen till Exempel på indata $1$. Detta är nu åtgärdat. Den $5$:e ekvationen var 8+3-2-4+8-7+2+4-0-8=8, vilket har ändrats till 8+3+2-4+8-7+2+4-0-8=8. Vidare var den $6$:e ekvationen 8+3-2-4+8-7+2+4+0-8=8, vilket har ändrats till 8+3+2-4+8-7+2+4+0-8=8.