1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 300100;

int n, a, sum[MAXN], dp[MAXN];


int main() {
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> a;
		sum[i] = (sum[i-1] + a) % MOD;
	}
	dp[0] = 1;
	for (int i=1; i<=n; i++) {
		for (int j=0; j<i; j++) {
			dp[i] += dp[j] * (1 - ((sum[i] - sum[j] + MOD) % MOD) % 2);
			dp[i] %= MOD;
		}
	}
	cout << dp[n] << endl;
}