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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cassert>
#include<vector>

typedef long long ll;
#define PARDIF(a,b) ((sum[(a)]-sum[(b)]) %2)

const ll MODULO = 1000000007;
const int MAXN = 300000;

#define NONE (MAXN+8)

ll a[MAXN+10];
ll dp[MAXN+10][2];
ll sum[MAXN+10];
//int ind[MAXN+10];

int main() {
	std::vector<int> ind;
	int n, parz;
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[NONE][0] = 0;
	dp[NONE][1] = 0;
	sum[0] = 0;
	sum[NONE] = 0;
	scanf("%d", &n);
	ll spmod = 0, steps, lsteps;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		sum[i] = sum[i-1] + a[i];
		parz = a[i] % 2;
		//printf("i=%d pi=%d parz=%d a=%lld sum=%lld\n", i, pi, parz, a[i], sum[i]);
		if (i == 1) {
			dp[i][0] = 0;
			dp[i][1] = 0;
		} else {
			dp[i][parz^1] = 0;
			dp[i][parz] = dp[i-1][0];
	//printf("--\n");
	//for (int k =0; k<2; ++k){
	//	for(int i=0; i<=n;++i) {
	//		printf("%lld ", dp[i][k]);
	//	}
	//	putchar('\n');
	//}
			//dp[i][parz] = (dp[i-1][0] - dp[pi][PARDIF(i-1,pi)] /*+ dp[i-1][1] - dp[i-1][1]*/ + dp[pi][PARDIF(i-1,pi)^1] + MODULO) % MODULO;
			for (int j = 0, sgn=0; j<ind.size(); ++j, sgn ^= 1) {
				dp[i][parz] += (- dp[ind[j]][PARDIF(i-1,ind[j])^sgn] /*+ dp[i-1][1] - dp[i-1][1]*/ + dp[ind[j]][PARDIF(i-1,ind[j])^1^sgn] + MODULO) % MODULO;
			}
			dp[i][parz] %= MODULO;
	//for (int k =0; k<2; ++k){
	//	for(int i=0; i<=n;++i) {
	//		printf("%lld ", dp[i][k]);
	//	}
	//	putchar('\n');
	//}
		}
		//printf("dp[i][0]_1=%lld dp[i][1]_1=%lld\n", dp[i][0], dp[i][1]);
		dp[i][1] += dp[i-1][1^parz];
		dp[i][1] %= MODULO;
		dp[i][0] += dp[i-1][0^parz];
		dp[i][0] %= MODULO;
		//printf("dp[i][0]_2=%lld dp[i][1]_2=%lld\n", dp[i][0], dp[i][1]);
		//+=
		steps = sum[i] / MODULO;
		if (steps != spmod){
			ind.push_back(0);
			spmod = steps;
		}
		assert(steps == ind.size());
		lsteps = 0;
		for (auto it = ind.begin(), end=ind.end(); it != end; ++it) {
			lsteps += MODULO;
			while ( sum[i] - sum[*it] >= lsteps )
				++(*it);
			*it = *it == 0? NONE : (*it);
		}
		//pi = ind[i-1];
	}
	ll wyn = dp[n][0];
	//printf("%lld\n", wyn);
	for (int j = 0, sgn=0; j<ind.size(); ++j, sgn ^= 1) {
		wyn += (- dp[ind[j]][PARDIF(n,ind[j])^sgn] /*+ dp[i-1][1] - dp[i-1][1]*/ + dp[ind[j]][PARDIF(n,ind[j])^1^sgn] + MODULO) % MODULO;
		//printf("po j=%d %lld\n", j, wyn);
	}
	wyn %= MODULO;
	printf("%lld\n", wyn);
	//for (int k =0; k<2; ++k){
	//	for(int i=0; i<=n;++i) {
	//		printf("%lld ", dp[i][k]);
	//	}
	//	putchar('\n');
	//}
	return 0;
}