Even Product Subsequences

Given an integer \( n \) and a list of \( n \) integers, your task is to determine the number of subsequences whose product is even. In this problem, a subsequence is defined as any non-empty subset of the given sequence (order preserved). The twist is: if there is at least one even number in the sequence, then every non-empty subsequence is considered to have an even product, and the answer is \(2^n - 1\). Otherwise, if all numbers are odd, no valid subsequence exists, and the answer is 0.

Note: This rule is a special condition for this problem and might not align with standard multiplication properties.

inputFormat

The input consists of two lines. The first line contains a single integer \( n \), representing the number of elements in the sequence. The second line contains \( n \) space-separated integers, which represent the elements of the sequence.

outputFormat

Output a single integer — the number of valid subsequences as defined by the problem. The answer is \(2^n - 1\) if there is any even number in the sequence, or 0 if all the numbers are odd.

3
1 2 3

7