[Usaco2012 Open]Balanced Cow Subsets

内存限制：128 MiB 时间限制：10 Sec

Farmer John's owns N cows (2 <= N <= 20), where cow i produces M(i) units of milk each day (1 <= M(i) <= 100,000,000). FJ wants to streamline the process of milking his cows every day, so he installs a brand new milking machine in his barn. Unfortunately, the machine turns out to be far too sensitive: it only works properly if the cows on the left side of the barn have the exact same total milk output as the cows on the right side of the barn! Let us call a subset of cows "balanced" if it can be partitioned into two groups having equal milk output. Since only a balanced subset of cows can make the milking machine work, FJ wonders how many subsets of his N cows are balanced. Please help him compute this quantity.

给出N（1≤N≤20）个数M(i) (1 <= M(i) <= 100,000,000)，在其中选若干个数，如果这几个数可以分成两个和相等的集合，那么方案数加1。问总方案数。

Line 1: The integer N.

Lines 2..1+N: Line i+1 contains M(i).

* Line 1: The number of balanced subsets of cows.

样例输入


			4 1 2 3 4 

INPUT DETAILS: There are 4 cows, with milk outputs 1, 2, 3, and 4.

样例输出


			 3 

OUTPUT DETAILS: There are three balanced subsets: the subset {1,2,3}, which can be partitioned into {1,2} and {3}, the subset {1,3,4}, which can be partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be partitioned into {1,4} and {2,3}.

#2679. [Usaco2012 Open]Balanced Cow Subsets

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示