Even Sum Partition

Given a sequence (a) of length (n), count the number of ways to partition it into contiguous segments such that for each segment, the sum of its numbers modulo (10^9+7) is even. Since the answer can be very large, output it modulo (10^9+7).

Note that because (10^9+7) is an odd number, a number (x) is even if and only if (x \bmod (10^9+7)) is even.

inputFormat

The first line contains an integer (n), the length of the sequence. The second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n).

outputFormat

Output a single integer: the number of valid partitions modulo (10^9+7).

sample

3
2 2 2

4