Descripción

¿Te gustan las pirámides numéricas? Dada una secuencia numérica que representa la base, normalmente se supone que debes construir el resto de la "pirámide" de abajo hacia arriba: Para cada par de números adyacentes, calculas su suma y la escribes encima. Por ejemplo, dada la secuencia base [~1, 2, 3~], la secuencia inmediatamente superior sería [~3, 5~], y la cúspide de la pirámide sería [~8~]:

Sin embargo, no me interesa completar la pirámide, sino que prefiero ir bajo tierra. Así, para una secuencia de ~n~ enteros no negativos, escribiré debajo una secuencia de ~n + 1~ enteros no negativos tal que cada número de la secuencia original sea la suma de los dos números que puse debajo. Sin embargo, puede haber varias secuencias posibles o incluso ninguna que cumpla esta condición. Entonces, ¿podrías decirme cuántas secuencias hay para que yo elija?

Entrada

La entrada consiste en:

• una línea con el entero ~n~ (~1 \le n \le 10^6~), la longitud de la secuencia base.
• una línea con n enteros ~a1, ... , an~ (~0 \le ai \le 10^8~ para cada ~i~), que forman la secuencia base.

Salida

Da salida a un único entero, el número de secuencias de enteros no negativos que tendrían la secuencia de entrada como siguiente nivel en una pirámide numérica.

Subtareas

• 10 puntos. Para n ≤ 10:
• 70 puntos. Para el resto sin resticciones

Ejemplos de Entrada y salida

Ejemplos de Entrada #1

6
12 5 7 7 8 4

Ejemplos de Salida #1

2

Ejemplos de Entrada #2

3
10 1000 100

Ejemplos de Salida #2

0