Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Background

The 'empty set' should be denoted by \varnothing (i.e., $\varnothing$).

(by somebody)

In the math class, Teacher Xu gave Alice a problem: Given the set $M=\left\{1,2,3,4\right\}$, define the cumulative product of a set as the product of all elements in the set.

Specifically, the cumulative product of the empty set $\varnothing$ is $0$. How many subsets of set $M$ have an even cumulative product.

Problem Description

Now Alice has given you another problem: Given a set $M$ with $n$ distinct elements $m_1, m_2, \ldots, m_n$, how many subsets of $M$ have a cumulative product that is even.

Since the answer can be very large, please print the answer taken modulo $\bm{10^7+7}$.

Input Format

• The first line consists a positive integer $n$, representing the number of elements in the set $M$.
• The second line consists of $n$ distinct positive integers, representing each element in the set $M$. (not guaranteed to be given in order)

Output Format

Output a single integer representing the number of subsets that meet the conditions.

Ssmples

4
1 2 4 3

13

3
2 4 6

8

Sample 1 Explanation

The sets that satisfy the conditions: $\varnothing, \left\{2\right\}, \left\{4\right\}, \left\{1,2\right\}, \left\{1,4\right\}, \left\{2,3\right\}, \left\{2,4\right\}, \left\{3,4\right\}, \left\{1,2,3\right\}, \left\{1,2,4\right\}, \left\{1,3,4\right\}, \left\{2,3,4\right\}, \left\{1,2,3,4\right\}$.

Data Range

• For $10\%$ of the data, all elements in $M$ are even numbers.
• For another $20\%$ of the data, $1 \le n \le 20$.
• For 100% of the data, ensure that $1 \le n \le 10^6$, $0 \le m_i \le 10^7$.