Balanced Cow Subsets

Farmer John owns N cows (2 ≤ N ≤ 20), where cow i produces M(i) units of milk each day (1 ≤ M(i) ≤ 100,000,000). To streamline the milking process, he installs a new machine in his barn. Unfortunately, the machine is overly 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!

We call a subset of cows balanced if it can be partitioned into two groups having equal milk output. Since only a balanced subset can make the milking machine work, please compute the number of balanced subsets among all subsets of the N cows.

For a subset with total milk output \(S\), a necessary condition for being balanced is that \(S\) is even. In fact, if \(S = 2T\), then the subset is balanced if and only if there exists a nonempty proper subset whose milk output sums to \(T\). For example, if a balanced subset is represented by the multiset \(\{a_1, a_2, \dots, a_k\}\) with \(\sum_{i=1}^{k} a_i = 2T\), then there must exist a selection of indices \(I \subsetneq \{1,2,...,k\}\) such that \(\sum_{i \in I} a_i = T\).

Your task is to calculate the total number of balanced subsets.

inputFormat

The first line contains an integer N (2 ≤ N ≤ 20), the number of cows.

The second line contains N space-separated integers, where the i-th integer represents M(i), the milk output of cow i.

outputFormat

Output a single integer representing the number of balanced subsets.

sample

2
1 1

1