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
#include <stdio.h>
using ll=long long;
const int C=350001, M=1000000007, Cv=1<<20;

ll val[2*Cv][2];
ll query(int start, int end, int parity){
	int l=start+Cv, r=end+Cv;
	if (l>r) return 0;
	ll res=val[l][parity];
	if (l!=r) res=(res+val[r][parity])%M;

	for (; l>0; l/=2,r/=2){
		if (l%2==0 && r-l>1) res = (res+val[l+1][parity])%M;
		if (r%2==1 && r-l>1) res = (res+val[r-1][parity])%M;
	}
	return res;
}

void insert(int pos, ll res, int parity){
	for (pos+=Cv; pos>0; pos/=2) val[pos][parity] = (val[pos][parity]+res)%M;
}

ll pom[C];
void Sebasort (ll tab[], int l, int r){
	int lim=2, limi=l+1, limj=l+2, j=limi, i=l, k=l;
	while (lim/2<=r-l+1){
		while (i<=r){
			if (limj>r)	limj=r+1;
			if ((j<limj&&tab[j]<tab[i])||i>=limi) pom[k]=tab[j], j++;
			else pom[k]=tab[i], i++;
			k++;
			if (i==limi&&j==limj)	limi+=lim, limj+=lim, i=j, j=limi;
		}
		for (i=l;i<=r;i++) tab[i]=pom[i];
		lim*=2, limi=l+lim/2, limj=l+lim, j=limi, i=k=l;
	}
}

inline int bin (ll v, ll tab[], int l, int r){
	int m;
	while (l<=r){
		m=(l+r)/2;
		if (tab[m]==v)	return m;
		if (tab[m]>v)	r=m-1;
		else l=m+1;
	}
	return -1;
}


ll summa[C], a[C], post_summa[C], finale[C], value[C];
int main(){
	int n, i, m;

	scanf ("%d", &n);
	for (i=0; i<n; i++) scanf ("%lld", &a[i]);

	summa[0] = a[0];
	for (i=1; i<n; i++) summa[i] = (summa[i-1] + a[i])%M;
	for (i=0; i<n; i++) post_summa[i] = summa[i];
	post_summa[n]=0;
	Sebasort(post_summa, 0, n);

	int i_values = 0;
	for (i=1; i<=n; i++){
		if (post_summa[i] != post_summa[i-1]) {
			value[i_values] = post_summa[i-1];
			i_values++;
		}
	}
	value[i_values] = post_summa[n];
	i_values++;

	ll res;
	insert(0, 1, 0); //starter
	for (i=0; i<n; i++){
		res = 0;
		m = bin(summa[i], value, 0, i_values);
		if (summa[i]%2 == 0){
			res = (res + query(0, m, 0))%M;
			res = (res + query(m+1, n, 1))%M;
		}
		if (summa[i]%2 == 1){
			res = (res + query(0, m, 1))%M;
			res = (res + query(m+1, n, 0))%M;
		}
		insert(m, res, summa[i]%2);
		finale[i] = res;
	}
	printf("%lld\n", finale[n-1]);

return 0;}