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