Balanced Cow Subsets

Time limit1sMemory limit128 MB

Summary

Count how many subsets of up to 20 cows can be split into two groups with equal total milk output.

Level: Hard8 of 10
Topics: Backtracking, Bit manipulation, Hash map, Divide and conquer
Solved: No attempts yet

Problem

Farmer John owns $N$ cows ( $2 \le N \le 20$ ), where cow $i$ produces $M(i)$ units of milk each day ( $1 \le M(i) \le 10^8$ ).

John installs a new milking machine in his barn, but it only works when the cows on the left side of the barn have exactly the same total milk output as the cows on the right side.

Call a subset of cows balanced if it can be partitioned into two groups having equal total milk output. Determine how many of the subsets of the $N$ cows are balanced.

Input

The first line contains the integer $N$ .

Each of the next $N$ lines contains one integer; line $i+1$ contains $M(i)$ .

Output

Print, on a single line, the number of balanced subsets of cows.

Examples1

Example 1
Input
```
4
1
2
3
4
```
Expected output
```
3
```