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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <queue>



using namespace std;

long long int MOD = 1000000007LL;

long long int a[300000+1];
long long int front_sum[300000+1];
long long int back_sum[300000+1];
unordered_map<string,long long int> memo;

long long int rek(int start, int stop, int deep){
	string s=to_string(start)+"X"+to_string(stop)+"Y"+to_string(deep);
	if(memo.find(s)!=memo.end()){
		return memo[s];
	}
	if(start >= stop) return 0;
	long long int wynik=0;
	if(deep > 1) {
		long long int sum=0;
		for(int i = start; i < stop-deep+1; ++i){
			sum+=a[i];
			if((sum%MOD)%2==0){
				wynik+=rek(i+1,stop,deep-1);
				wynik%=MOD;
			}
		}
	} else {
		long long int sum=0;
		for(int i = start; i < stop-1; ++i){
			if( ((front_sum[i]-((start==0)?0:front_sum[start-1]))%MOD)%2 == 0 && ((back_sum[i+1]-back_sum[stop])%MOD)%2 == 0 ){
				wynik++;
			}
		}
		wynik%=MOD;
	}
	//if(wynik > 0) {
	//	cout << "(" << start << "): " << wynik << "(" << deep <<")" << "\n";
	//}
	memo[s]=(wynik%MOD);
	return (wynik%MOD);
}


int main(){
	int n;
	cin >> n;
	long long int S = 0;
	for(int i =0; i < n; ++i){
		cin >> a[i];
		S+=a[i];
		front_sum[i]=S;
	}
	S=0;
	back_sum[n]=0;
	for(int i = n-1; i >= 0; --i){
		S+=a[i];
		back_sum[i]=S;
	}
	
	long long int wynik = 1-((back_sum[0]%MOD)%2);
	for(int i = 1; i < n; ++i){
		wynik += rek(0, n, i);
//		cout << "-------------------\n";
	}
	
	cout << (wynik%MOD) << "\n";
	
	return 0;
}