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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 1050000;
const int MOD = 1000000007;

int w[2][N], M[2], i, j, j2, tab[N], act, sum, ind[2], val[2][N], n, m;
set<int> s[2];
map<int, int> mapa[2];

void insert (int in, int v, int b) {
	int s = M[in] + v;
	while (s) {
	    w[in][s] = (w[in][s] + b) % MOD;
	    s /= 2;
	}
}


int query (int in, int a, int b) {
	int va = M[in] + a, vb = M[in] + b;
	int wyn = w[in][va];
	if (va != vb) wyn = (wyn + w[in][vb]) % MOD;
	while (va / 2 != vb / 2) {
		  if (va % 2 == 0) wyn = (wyn + w[in][va + 1]) % MOD;
		  if (vb % 2 == 1) wyn = (wyn + w[in][vb - 1]) % MOD;
		  va /= 2; vb /= 2;
	}
	return wyn;
}


void init (int in) {
	M[in] = 1;
	while (M[in] < s[in].size()) M[in] *= 2;
	for (int i=1;i < 2 * M[in];i++) w[in][i] = 0;
	M[in]--;
}

void push(int x) {
	s[x % 2].insert(x);
	if (x != 0) s[1 - (x % 2)].insert(x - 1);
}

int main() {
scanf("%d", &n);
for (i=1;i<=n;i++) scanf("%d", &tab[i]);
s[0].clear();
s[1].clear();
push(1);
mapa[0].clear();
mapa[1].clear();
act = 0;
for (i=1;i<=n;i++) {
	act = (act + MOD - tab[i]) % MOD;
	push(act);
}
for (i=0;i<2;i++) {
	init(i);
	ind[i] = 0;
	for (int w : s[i]) {
		ind[i]++;
		val[i][ind[i]] = w;
		mapa[i][w] = ind[i];
	}
}

insert(0, 1, 1);

act = 0;
for (i=1;i<=n;i++) {
	act = (act + MOD - tab[i]) % MOD;
	m = act % 2;
	j = mapa[m][act];
	sum = query(m, j, ind[m]);
	if (act != 0) {
		j2 = mapa[1 - m][act - 1];
		sum = (sum + query(1 - m, 1, j2)) % MOD;
	}
	insert(m, j, sum);
}
printf("%d\n", sum);
return 0;
}