P9049 [PA 2021] Mopadulo

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$.

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

One line containing an integer, representing the required value.

#### 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