Énoncé du problème
JOI-kun est en $1$-re année d'école primaire. JOI-kun adore l'addition et la soustraction qu'il vient tout juste d'apprendre, et dès qu'il voit une suite de chiffres alignés, il s'amuse à former une égalité en insérant = entre les $2$ derniers chiffres et en insérant systématiquement + ou - entre les autres chiffres adjacents. Par exemple, à partir de 8 3 2 4 8 7 2 4 0 8 8, il peut former l'égalité 8+3-2-4+8-7-2-4-0+8=8.
Après avoir formé une égalité, JOI-kun effectue le calcul pour vérifier si l'égalité est correcte. Cependant, JOI-kun ne connaît pas encore les nombres négatifs et ne sait pas calculer avec des nombres dépassant $20$. Par conséquent, parmi les égalités correctes, seules celles pour lesquelles tous les nombres apparaissant au cours du calcul du membre de gauche, évalué de gauche à droite, sont compris entre $0$ et $20$ inclus peuvent être vérifiées par JOI-kun. Par exemple, 8+3-2-4-8-7+2+4+0+8=8 est une égalité correcte, mais comme 8+3-2-4-8, qui apparaît en cours de calcul, est un nombre négatif, JOI-kun ne peut pas vérifier si cette égalité est correcte.
Étant donné une suite de chiffres en entrée, écrivez un programme permettant de trouver le nombre d'égalités correctes que JOI-kun peut former et vérifier.
Entrée
Le fichier d'entrée se compose de $2$ lignes. La $1$-re ligne contient un entier $N$ ($3 \le N \le 100$) représentant le nombre de chiffres alignés. La $2$-e ligne contient $N$ entiers supérieurs ou égaux à $0$ et inférieurs ou égaux à $9$, séparés par des espaces.
Dans $60\%$ des données d'entrée fournies, le nombre d'égalités correctes que JOI-kun peut former et vérifier ne dépasse pas $2^{31}-1$. De plus, dans l'ensemble des données d'entrée fournies, le nombre d'égalités correctes que JOI-kun peut former et vérifier ne dépasse pas $2^{63}-1$.
Sortie
Affichez sur $1$ ligne un entier représentant le nombre d'égalités correctes que JOI-kun peut former et vérifier.
Exemples d'entrée/sortie
Exemple d'entrée 1
11 8 3 2 4 8 7 2 4 0 8 8
Exemple de sortie 1
10
Exemple d'entrée 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
Exemple de sortie 2
7069052760
Dans l'exemple d'entrée $1$, JOI-kun peut former et vérifier les $10$ égalités correctes suivantes :
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
Par conséquent, on affiche $10$.
Dans l'exemple d'entrée $2$, veuillez noter que la réponse ne tient pas dans un entier signé sur $32$ bits.
(Ajout du $21$.$2$.$2015$) Suite à la remarque d'un utilisateur, il s'est avéré qu'il y avait une erreur parmi les égalités de l'explication de l'exemple d'entrée $1$. Cela a maintenant été corrigé. La $5$-e égalité était 8+3-2-4+8-7+2+4-0-8=8 et a été corrigée en 8+3+2-4+8-7+2+4-0-8=8. De même, la $6$-e égalité était 8+3-2-4+8-7+2+4+0-8=8 et a été corrigée en 8+3+2-4+8-7+2+4+0-8=8.