Problema

JOI-kun está en $1$-er grado de primaria. A JOI-kun le encantan la suma y la resta que acaba de aprender, y cada vez que ve una fila de dígitos juega a formar una ecuación colocando = entre los últimos $2$ dígitos y colocando siempre + o - entre el resto de los dígitos adyacentes. Por ejemplo, a partir de 8 3 2 4 8 7 2 4 0 8 8, puede formar la ecuación 8+3-2-4+8-7-2-4-0+8=8.

Después de formar una ecuación, JOI-kun la calcula para comprobar si es una ecuación correcta. Sin embargo, JOI-kun aún no conoce los números negativos y no puede calcular números que superen $20$. Por lo tanto, de entre las ecuaciones correctas, solo aquellas en las que al evaluar el lado izquierdo de izquierda a derecha todos los números que aparecen durante el cálculo son mayores o iguales a $0$ y menores o iguales a $20$ son ecuaciones correctas que JOI-kun puede comprobar. Por ejemplo, 8+3-2-4-8-7+2+4+0+8=8 es una ecuación correcta, pero como 8+3-2-4-8, que aparece en medio del cálculo, es un número negativo, JOI-kun no puede comprobar si esta ecuación es correcta.

Dada una secuencia de dígitos como entrada, escribe un programa para encontrar la cantidad de ecuaciones correctas que JOI-kun puede formar y comprobar.

Entrada

El archivo de entrada consta de $2$ líneas. La $1$-ra línea contiene un entero $N$ ($3 \le N \le 100$) que representa la cantidad de dígitos en la fila. La $2$-da línea contiene $N$ enteros mayores o iguales a $0$ y menores o iguales a $9$, separados por espacios.

En el $60\%$ de los datos de entrada proporcionados, la cantidad de ecuaciones correctas que JOI-kun puede formar y comprobar no supera $2^{31}-1$. Además, en todos los datos de entrada proporcionados, la cantidad de ecuaciones correctas que JOI-kun puede formar y comprobar no supera $2^{63}-1$.

Salida

Imprime en $1$ línea un entero que represente la cantidad de ecuaciones correctas que JOI-kun puede formar y comprobar.

Ejemplos de entrada y salida

Ejemplo de entrada 1

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

Ejemplo de salida 1

10

Ejemplo de entrada 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

Ejemplo de salida 2

7069052760

En el Ejemplo de entrada $1$, JOI-kun puede formar y comprobar las siguientes $10$ ecuaciones correctas:

• 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

Por lo tanto, se imprime $10$.

En el Ejemplo de entrada $2$, ten en cuenta que la respuesta no cabe en el rango de un entero con signo de $32$ bits.

(Añadido el día $21$ del mes $2$ de $2015$) Gracias al aviso de un usuario, se descubrió que había un error en las ecuaciones de la explicación del Ejemplo de entrada $1$. Ya ha sido corregido. La $5$-ta ecuación era 8+3-2-4+8-7+2+4-0-8=8, y se corrigió a 8+3+2-4+8-7+2+4-0-8=8.Asimismo, la $6$-ta ecuación era 8+3-2-4+8-7+2+4+0-8=8, y se corrigió a 8+3+2-4+8-7+2+4+0-8=8.