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
#include <algorithm>
#include <cstdio>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define ALL(c) (c).begin(),(c).end()
#define INT(x) int x; scanf("%d", &x)

typedef vector<int> VI;

const int mod = 1000000007;
int a[300000];
unordered_map<int, int> index;
int h, nn, n2;
int s[2][1 << 20];
VI offsets;
int offset;

void add(int i, int v) {
	int p = offsets[i] & 1;
	i += n2;
	s[p][i] = (s[p][i] + v) % mod;
	i >>= 1;
	while (i) {
		REP(q,2) s[q][i] = (s[q][i << 1] + s[q][(i << 1) + 1]) % mod;
		i >>= 1;
	}
}

int get(int x, int y, int p, int node = 1, int level = 0) {
	if (x >= y) return 0;
	int start = (node - (1 << level)) << (h - level);
	int end = start + (1 << (h - level));
	if (x == start && y == end) return s[p][node];
	int mid = (start + end) >> 1;
	return (get(x, min(y, mid), p, node << 1, level + 1) + get(max(x, mid), y, p, (node << 1) + 1, level + 1)) % mod;
}

int getEven() {
	int x = index[mod - offset];
	return (get(0, x, offset & 1) + get(x, nn, !(offset & 1))) % mod;
}

int main() {
	INT(n);
	REP(i,n) scanf("%d", &a[i]);
	set<int> offsetsSet;
	offsetsSet.insert(0);
	int ns = 0;
	REP(i,n) {
		ns = (ns + mod - a[i]) % mod;
		offsetsSet.insert(ns);
	}
	offsets = VI(ALL(offsetsSet));
	FORE(it,offsetsSet) index[*it] = nn++;
	index[mod] = nn;
	h = 0;
	while ((1 << h) < nn) ++h;
	n2 = 1 << h;
	add(0, 1);
	REP(i,n) {
		if (i) add(index[(mod - offset) % mod], getEven());
		offset = (offset + a[i]) % mod;
	}
	printf("%d\n", getEven());
}