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