Problem Description

Given a sequence $a$ of length $n$, find how many ways there are to divide $a$ into several intervals, such that for every interval, the sum of all numbers in this interval modulo $10^9 + 7$ is even.

Since the answer may be very large, you only need to output the value of the answer modulo $10^9 + 7$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

One line containing an integer, representing the required value.

4
1000000006 1 5 1000000004

3

Hint

Sample #1 Explanation

The three ways to divide are as follows.

• $[1, 4]$
• $[1, 2], [3, 4]$
• $[1], [2, 3], [4]$

Constraints

For all testdata, $1 \leq n \leq 3 \times 10^5$, $0 \leq a_i < 10^9 + 7$.

Translated by ChatGPT 5