Farmer John possède $N$ vaches, $2 \le N \le 20$ ; la vache $i$ produit $M(i)$ unités de lait par jour ($1 \le M(i) \le 100,000,000$). Pour simplifier la traite quotidienne, il installe une machine neuve dans la grange. Mais elle est trop sensible : elle fonctionne seulement si les vaches à gauche et à droite produisent exactement le même total !

Un sous-ensemble est « équilibré » s'il se partitionne en deux groupes de production égale. Seul un tel sous-ensemble fait fonctionner la machine, et FJ veut connaître leur nombre parmi ses $N$ vaches. Calculez ce nombre.

Entrée

• Ligne 1 : l'entier $N$.
• Lignes 2..1+$N$ : la ligne $i+1$ contient $M(i)$.

Sortie

• Ligne 1 : le nombre de sous-ensembles équilibrés.

Exemples

Entrée 1

4
1
2
3
4

Sortie 1

3

Remarque

Quatre vaches produisent 1, 2, 3 et 4 unités.

Trois sous-ensembles équilibrés : $\{1,2,3\}$ se partitionne en $\{1,2\}$ et $\{3\}$ ; $\{1,3,4\}$ en $\{1,3\}$ et $\{4\}$ ; $\{1,2,3,4\}$ en $\{1,4\}$ et $\{2,3\}$.

Auteur du problème : Neal Wu, 2012