Odd Sum Subsequences Count

You are given a sequence of n integers. Your task is to calculate the number of non-empty subsequences whose sum is odd.

A subsequence of a sequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. The total number of subsequences (excluding the empty subsequence) for a sequence of length n is \(2^n - 1\).

For each subsequence, compute the sum and check if it is odd (i.e. if it satisfies \(\text{sum} \equiv 1 \pmod{2}\)). Output the count of such subsequences.

inputFormat

The first line contains a single integer n (1 \(\le\) n \(\le\) 20) representing the number of elements in the sequence.

The second line contains n space-separated integers, which are the elements of the sequence.

outputFormat

Output a single integer: the number of non-empty subsequences of the sequence which have an odd sum.

3
1 2 3

4