You are given an array a of n positive integers.

Partition the array into one or more contiguous segments such that every element belongs to exactly one segment.

Let the sum of each segment be computed. A partition is considered valid if the parity (odd/even) of the segment sums alternates between every pair of adjacent segments.

In other words, if the segment sums are

S1, S2, ..., Sk

then for every 1 ≤ i < k,

(Si % 2) != (Si+1 % 2)

Your task is to determine the number of valid partitions.

Since the answer can be large, output it modulo 10^9 + 7.

Since the answer can be large, output it modulo 10^9 + 7.

Input

n a1 a2 ... an

Output

Print a single integer — the number of valid partitions modulo 10^9 + 7.

Example 1

Input

4 1 2 3 3

Output

2

Explanation

The valid partitions are:

[1,2,3,3] [1,2,3] | [3] [1,2] | [3,3] [1] | [2,3,3]

The partition

[1] | [2] | [3] | [3]

is invalid because the segment sum parities are

odd, odd, odd, odd

which do not alternate.