P1202

[Usaco2012 Open]Balanced Cow Subsets

[Usaco2012 Open]Balanced Cow Subsets

农夫约翰有 NN 头奶牛，第 ii 头奶牛每天产出 MiM_i 单位的牛奶。为了简化每天的挤奶流程，约翰在牛棚中安装了一台全新的挤奶机。

然而，这台挤奶机非常敏感：只有当牛棚左侧奶牛的牛奶总产量与右侧奶牛的牛奶总产量完全相等时，机器才能正常工作。

如果一个奶牛子集可以被划分为两个牛奶总产量相等的集合，则称这个子集是平衡的。约翰想知道，NN 头奶牛中有多少个平衡子集。请你帮助他计算这个数量。

输入格式

第一行包含一个整数 NN。

接下来 NN 行中，第 i+1i+1 行包含一个整数 MiM_i，表示第 ii 头奶牛每天的产奶量。

输出格式

输出一个整数，表示平衡子集的数量。

样例输入

4 1 2 3 4

样例输出

3

样例解释

共有 33 个平衡子集：

  • 子集 {1,2,3}\{1,2,3\} 可以划分为 {1,2}\{1,2\} 和 {3}\{3\}；
  • 子集 {1,3,4}\{1,3,4\} 可以划分为 {1,3}\{1,3\} 和 {4}\{4\}；
  • 子集 {1,2,3,4}\{1,2,3,4\} 可以划分为 {1,4}\{1,4\} 和 {2,3}\{2,3\}。

数据范围

  • 2≤N≤202\le N\le 20；
  • 1≤Mi≤1081\le M_i\le 10^8。

来源与许可

本题为 USACO 2012 Open 试题「Balanced Cow Subsets」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 1 2 3 4

输出

3