Alice and Bob want to buy firecrackers. There are \(N\) types of firecrackers available in the market with an ID \(i\) ranging from \(1\) to \(N\). The cost of each firecracker is \(C_i\). Each firecracker can be bought at most once. Bob's father allows him to spend all the money in any way but his only condition is that Alice and Bob receive equal amounts of money.

Your task is to determine the number of different amounts of money both can receive from Bob's father. You are given the cost of all crackers and the money according to the condition provided.

In other words, let \(S\) be a set. For each subset of firecrackers, if the sum of the costs of these firecrackers is even, then add their sum to \(S\) and print the size of \(S\). Note that the set does not contain equal elements.

Input format

First line: \(N\) denoting the types of firecrackers
Next line: \( C_1, C_2, \ldots, C_n\) denoting the cost of the firecrackers

Output format

Print the number of different amounts of money that Bob and Alice can receive from Bob's father.

Constraints

\(1 \le n \le 20\\ 1 \le C_i \le 1000 \)