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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

constexpr size_t MOD = 1e9+7;
int n;
vector<int> a, b;

int dfs(int p) {
	if(b[p]!=-1) return b[p];
	int s = 0, ss = 0;
	for(int i=p;i<n; ++i) {
		ss = (ss+a[i])%MOD;
		if(ss%2	== 0)
			s = (s+dfs(i+1))%MOD;
	}
	b[p] = s;
	return s;
}


int podtest() {
	bool parzyste = true;
	int n = (MOD+1)/2;
	for(auto &&e : a) {
		parzyste = parzyste ^ (e&1);
		if(parzyste) n = (n*2)%MOD;
	}
	if(!parzyste) return 0;
	return n;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	unsigned long long suma = 0;
	a.resize(n); b.resize(n+1);
	for(auto &&e : a) {
		cin >> e;
		suma += e;
	}
	for(auto &&e : b) e = -1;
	b[n] = 1;
	if(suma < MOD) cout << podtest() << '\n';
	else cout << dfs(0) << '\n';
	return 0;
	
}