平衡奶牛子集

【题目描述】

Farmer John有N头奶牛（2<=N<=20），其中第i头牛每天能生产M(i)个单位的牛奶（1<=M(i)<=100000000）。FJ希望简化每天挤奶的过程，因此他在谷仓里装了一台崭新的挤奶机。不幸的是，他发现这台机器非常敏感：只有当谷仓左右两侧的奶牛产奶数量完全相等时，它才能正常工作！

我们称所有奶牛的一个子集是“平衡的”，如果它能被分成产奶数量完全相等的两组。因为只有一个平衡的奶牛子集才能让挤奶机工作，FJ希望知道在他的N头奶牛中有多少个子集是平衡的。请你帮助他计算出这个数目。

【输入格式】

第1行：一个整数N。

第2到N+1行：第i+1行包含M(i)。

【输出格式】

第1行：平衡子集的数量。

【输入样例】

4

1

2

3

4

【输出样例】

3

【提示】

有4头奶牛，产奶数量为1,2,3,4.

有三个平衡子集：{1,2,3}，可以被分成{1,2}和{3}；{1,3,4}可以被分成{1,3}和{4}；{1,2,3,4}可以被分成{1,4}和{2,3}。

【来源】

USACO 2012 US Open, Gold Division, Balanced Cow Subsets