题目描述

$\red{Farmer John}$'$\red{s }$拥有 $\red{N }$头奶牛 $\red{(2 <= N <= 20)，}$其中奶牛 $\red{i }$每天生产 $\red{M(i) }$个单位的牛奶 $\red{(1 <= M(i) <= 100,000,000)}$。$\red{FJ }$想简化每天挤奶的过程，所以他在自己的牛舍里安装了一台全新的挤奶机。不幸的是，这台机器太敏感了：只有当牛舍左侧的奶牛与牛舍右侧的奶牛的总产奶量完全相同时，它才能正常工作！

如果可以将奶牛的子集划分为具有相同产奶量的两组，我们就称其为"平衡"奶牛。由于只有平衡的奶牛子集才能使挤奶机工作，$\red{FJ }$想知道他的 $\red{N }$头奶牛中有多少子集是平衡的。请帮他计算这个数 量。

输入格式

第 $\red{1 }$行：整数 $\red{N}$。

第 $\red{2..1+N }$行：第 $\red{i+1 }$行包含 $\red{M(i)}$。

输出格式

第 $\red{1 }$行：奶牛平衡子集的数量。

样例

输入样例

4 
1 
2 
3 
4

输出样例

3

提示

有 $\red{4 }$头奶牛，产奶量分别为 $\red{1}$、$\red{2}$、$\red{3 }$和 $\red{4}$。

有三个平衡子集：子集$\red{\{1,2,3\}，}$可分为$\red{\{1,2\}}$和$\red{\{3\}，}$子集$\red{\{1,3,4\}，}$可分为$\red{\{1,3\} }$和 $\red{\{4\}，}$以及子集 $\red{\{1,2,3,4\} }$可以划分为 $\red{\{1,4\} }$和 $\red{\{2,3\}}$。