Farmer John possiede $N$ mucche, $2 \le N \le 20$; la mucca $i$ produce $M(i)$ unità di latte al giorno ($1 \le M(i) \le 100,000,000$). Per semplificare la mungitura quotidiana installa una macchina nuova nel granaio. Ma è troppo sensibile: funziona solo con produzione totale esattamente uguale delle mucche a sinistra e a destra!
Un sottoinsieme è «bilanciato» se può essere diviso in due gruppi con produzione uguale. Solo uno bilanciato fa funzionare la macchina, e FJ vuole contarli fra le sue $N$ mucche. Calcola il numero.
Input
- Riga 1: intero $N$.
- Righe 2..1+$N$: la riga $i+1$ contiene $M(i)$.
Output
- Riga 1: numero di sottoinsiemi bilanciati.
Esempi
Input 1
4 1 2 3 4
Output 1
3
Nota
Quattro mucche producono 1, 2, 3 e 4 unità.
Tre sottoinsiemi bilanciati: $\{1,2,3\}$ si divide in $\{1,2\}$ e $\{3\}$; $\{1,3,4\}$ in $\{1,3\}$ e $\{4\}$; $\{1,2,3,4\}$ in $\{1,4\}$ e $\{2,3\}$.
Autore del problema: Neal Wu, 2012