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
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7;
const ll MOD=1e9+7;
ll T[LIM], tr[4*LIM][2], N=1;
map<ll,ll>mp;
vector<ll>skal;
void upd(int v, int k, ll x) {
	v+=N;
	while(v) {
		tr[v][k]=(tr[v][k]+x)%MOD;
		v/=2;
	}
}
ll cnt(int l, int r, int k) {
	l+=N; r+=N;
	ll ans=tr[l][k];
	if(l!=r) ans=(ans+tr[r][k])%MOD;
	while(l/2!=r/2) {
		if(l%2==0) ans=(ans+tr[l+1][k])%MOD;
		if(r%2==1) ans=(ans+tr[r-1][k])%MOD;
		l/=2; r/=2;
	}
	return ans;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	while(N<=n) N*=2;
	ll akt=0;
	rep(i, n) {
		cin >> T[i];
		akt=(akt+T[i])%MOD;
		skal.pb(akt);
	}
	sort(all(skal));
	akt=0;
	for(auto i : skal) if(!mp[i]) {
		++akt;
		mp[i]=akt;
	}
	akt=0;
	ll x;
	upd(0, 0, 1);
	rep(i, n) {
		akt=(akt+T[i])%MOD;
		x=cnt(0, mp[akt], akt%2)+cnt(mp[akt], N-1, (akt+1)%2);
		x%=MOD;
		upd(mp[akt], akt%2, x);
	}
	cout << x << '\n';
}