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
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int mod = 1e9+7;

const int MAXN = 3e5+5, base = (1<<19);
int n;
int a[MAXN], suf[MAXN];
pair<int, int> tree[2*base+1];
int sum[2][2*base+1];
int where[MAXN];

int qry(int add, int id=1) {
	if(tree[id].st + add < mod && tree[id].nd + add < mod) {
		return sum[add%2][id];
	}
	if(tree[id].st + add >= mod && tree[id].nd + add >= mod) {
		return sum[(add+1)%2][id];
	}
	return (qry(add, id*2) + qry(add, id*2+1)) % mod;
}

void ins(int x, int v) {
	x += base;
	bool m = tree[x].st % 2;
	while(x) {
		sum[m][x] += v;
		sum[m][x] %= mod;
		x /= 2;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}
	for(int i=n; i>=1; --i) {
		suf[i] = suf[i+1] + a[i];
		suf[i] %= mod;
	}
	vector<pii> vec(n+1);
	for(int i=0; i<=n; ++i) {
		vec[i] = mp(suf[i+1], i); 
	}
	sort(vec.begin(), vec.end());

	for(int i=0; i<=n; ++i) {
		tree[i+base] = mp(vec[i].st, vec[i].st);
		where[vec[i].nd] = i;
	}
	for(int i=base-1; i>=0; --i) {
		tree[i] = mp(min(tree[i*2].st, tree[i*2+1].st), max(tree[i*2].nd, tree[i*2+1].nd));	
	}
	ins(where[0], 1);
	int val = 0;
	for(int i=1; i<=n; ++i) {
		val = qry((mod - suf[i+1]) % mod);	
		ins(where[i], val);
	}
	cout<<val<<'\n';
}