Mopadulo numbers are numbers whose remainder when divided by $p$ is even. We do not know any large prime numbers other than $10^9 + 7$, so we will only deal with mopadulo $1\,000\,000\,007$ numbers.

Calculate the number of ways to partition a given sequence of numbers $a_1, a_2, \dots, a_n$ into intervals such that the sum of numbers in each interval is a mopadulo $1\,000\,000\,007$ number. In such a partition, every element of the sequence must belong to exactly one interval. Since the number of such partitions can be very large, it is sufficient to provide its remainder when divided by (what else?) $10^9 + 7$.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 300\,000$), representing the length of the given sequence.

The second line of input contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < 10^9 + 7$).

Output

The output should contain a single integer representing the remainder of the number of valid partitions of the sequence $a_1, a_2, \dots, a_n$ when divided by $10^9 + 7$.

Examples

Input 1

4
1000000006 1 5 1000000004

Output 1

3

Note

Explanation of the example: The valid partitions into intervals are: $[1000000006, 1, 5, 1000000004]$ $[1000000006, 1], [5, 1000000004]$ * $[1000000006], [1, 5], [1000000004]$

Subtasks

• In some test groups, $a_i \le 100$.
• In other test groups, $n \le 3000$.

In both of the above cases, there is at least one such group.