Even Sum Partition

Given an array \( A = [A_0, A_1, ..., A_{N-1}] \) of length \( N \), we want to choose a subset \( R_1 \) of indices from \( I = \{0, 1, 2, ..., N-1\} \). Let the complement of \( R_1 \) be \( R_2 \). Define \( S_1 = \sum_{r \in R_1} A_r \) and \( S_2 = \sum_{r \in R_2} A_r \). When a subset (either \( R_1 \) or \( R_2 \)) is empty, its sum is considered \(0\). Your task is to count how many ways there are to choose \( R_1 \) such that both \( S_1 \) and \( S_2 \) are even.

Note: Using the condition \( S_1 \equiv 0 \pmod{2} \) and \( S_2 = (\text{total sum} - S_1) \equiv 0 \pmod{2} \), it can be deduced that the total sum must be even. If the total sum is odd, the answer is \(0\). Otherwise, the problem reduces to counting the subsets of indices such that the sum of selected \( A_i \) is even.

Hint: Let \( e \) be the number of even numbers and \( o \) be the number of odd numbers in \( A \). If \( o > 0 \), then the number of ways to choose a subset with even sum is \(2^{e} \times \left(\sum_{j \text{ even}} \binom{o}{j}\right) = 2^{e} \times 2^{o-1} = 2^{N-1}\). Otherwise (i.e. when all elements are even), every subset has an even sum, so there are \(2^N\) ways.

inputFormat

The first line contains an integer \( N \) representing the length of array \( A \). The second line contains \( N \) space-separated integers, representing the elements of \( A \).

outputFormat

Output a single integer: the number of valid subsets \( R_1 \) such that both \( S_1 \) and \( S_2 \) are even.

sample

3
1 2 3

4