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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>


using namespace std;

typedef long long ll;

const int N = 3e5+3;
const ll Q = 1e9 + 7;

int n;
ll T[N+3],sp[N+3],dp[N+3];
bool flag = true;

ll mod(ll a, ll b){
	ll x = (a+b)%Q;
	if(x<0){
		x+=Q;
	}
	return x;
}

void solve2(){
	ll s1 = 0;
	ll s2 = 0;
	for(int i = 1;i<=n;i++){
		if(T[i] % 2 == 0){
			s1 *= 2;
			s2 *= 2;
			if(sp[i] % 2 == 0 && (sp[i-1] % 2 == 1 || i == 1)){
				s1 += 1;
			}
		}else{
			ll s2n = s1*2;
			ll s1n = s2;
			s1 = s1n;
			s2 = s2n;
		}
		//cout<<s1<<","<<s2<<endl;
	}
	cout<<s1;
}

int main(){
	
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>T[i];
		if(T[i]>100){
			flag = false;
		}
		T[i] %= Q;
		sp[i] = (T[i] + sp[i-1])%Q;
	}
	if(flag){
		solve2();
		return 0;
	}
	sp[0]=0;
	dp[0]=1;
	for(int i = 1;i<=n;i++){
		//cout<<i<<" -> ";
		for(int j = 1;j<=i;j++){
			//cout<<j<<","<<mod(sp[i],-sp[j-1])<<","<<dp[j-1]<<" ";
			if(mod(sp[i],-sp[j-1])%2 == 0){
				dp[i] += dp[j-1];
			}
		}//cout<<endl;
	}
	/*for(int i = 0;i<=n;i++){
		cout<<dp[i]<<" ";
	}*/
	cout<<dp[n];
	
	
	
	return 0;
	
}