ל-Farmer John יש $N$ פרות, $2 \le N \le 20$; פרה $i$ מייצרת $M(i)$ יחידות חלב ביום ($1 \le M(i) \le 100,000,000$). לפישוט החליבה היומית התקין מכונה חדשה באסם. אך היא רגישה מדי: פועלת רק כשסך החלב של הפרות משמאל ומימין זהה בדיוק!

תת-קבוצה היא «מאוזנת» אם ניתן לחלקה לשתי קבוצות בעלות תפוקה שווה. רק תת-קבוצה מאוזנת מפעילה את המכונה, ו-FJ רוצה לדעת כמה יש בין $N$ פרותיו. חשבו זאת.

קלט

• שורה 1: שלם $N$.
• שורות 2..1+$N$: שורה $i+1$ מכילה $M(i)$.

פלט

• שורה 1: מספר תת-הקבוצות המאוזנות.

דוגמאות

קלט 1

4
1
2
3
4

פלט 1

3

הערה

ארבע הפרות מייצרות 1, 2, 3 ו-4 יחידות.

שלוש תת-קבוצות מאוזנות: $\{1,2,3\}$ מתחלקת ל-$\{1,2\}$ ו-$\{3\}$; $\{1,3,4\}$ ל-$\{1,3\}$ ו-$\{4\}$; $\{1,2,3,4\}$ ל-$\{1,4\}$ ו-$\{2,3\}$.

מחבר הבעיה: Neal Wu, 2012