Farmer John besitzt $N$ Kühe, $2 \le N \le 20$; Kuh $i$ produziert täglich $M(i)$ Einheiten Milch ($1 \le M(i) \le 100,000,000$). Zur Vereinfachung des täglichen Melkens installiert er eine neue Maschine in der Scheune. Doch sie ist viel zu empfindlich: Nur bei exakt gleichem gesamten Milchertrag der Kühe links und rechts arbeitet sie richtig!

Eine Teilmenge heißt «ausgewogen», wenn sie in zwei Gruppen mit gleichem Milchertrag zerlegbar ist. Nur eine ausgewogene Teilmenge lässt die Maschine arbeiten, und FJ fragt nach ihrer Zahl unter seinen $N$ Kühen. Berechne sie.

Eingabe

• Zeile 1: Ganzzahl $N$.
• Zeilen 2..1+$N$: Zeile $i+1$ enthält $M(i)$.

Ausgabe

• Zeile 1: Zahl ausgewogener Teilmengen.

Beispiele

Eingabe 1

4
1
2
3
4

Ausgabe 1

3

Hinweis

Vier Kühe geben 1, 2, 3 und 4 Einheiten Milch.

Drei ausgewogene Teilmengen: $\{1,2,3\}$ zerfällt in $\{1,2\}$ und $\{3\}$; $\{1,3,4\}$ in $\{1,3\}$ und $\{4\}$; $\{1,2,3,4\}$ in $\{1,4\}$ und $\{2,3\}$.

Aufgabenautor: Neal Wu, 2012