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
93
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int MOD = 1e9 + 7;

struct dp{
	vector<pair<int,int>> synowie;
	vector<pair<int,int>> t;
	int pd = 1;

	void init(int n){
		t.push_back({0,0});
		synowie.push_back({0,0});
		while(pd < n)
			pd *= 2;
	}
	int as(int i,int k){
		if(k == 0){
			if(synowie[i].F != 0)
				return synowie[i].F;
			synowie.push_back({0,0});
			t.push_back({0,0});
			return synowie[i].F = t.size() - 1;
		}
		if(k == 1){
			if(synowie[i].S != 0)
				return synowie[i].S;
			synowie.push_back({0,0});
			t.push_back({0,0});
			return synowie[i].S = t.size() - 1;
		}
	}	

	void add(int a,int b,int p,int k,int i,int x){
		if(k < a || b < p)
			return;
		if(a <= p && k <= b){
			t[i].F += x;
			t[i].F %= MOD;
			return;
		}
		int s = (p + k)/2;
		add(a,b,p,s,as(i,0),x);
		add(a,b,s+1,k,as(i,1),x);
		t[i].S = ((t[as(i,0)].F + t[as(i,0)].S)%MOD + (t[as(i,1)].F + t[as(i,1)].S)%MOD) % MOD;
	}

	int spr(int p,int k,int i,int S,int l,int SUMA){
		if((((min(p-1,MOD/2)*2+l+S)%MOD)%2 == 1 && ((min(k-1,MOD/2)*2+l+S)%MOD)%2 == 1) || p > MOD)
			return 0;
		if(((min(p-1,MOD/2)*2+l+S)%MOD)%2 == 0 && ((min(k-1,MOD/2)*2+l+S)%MOD)%2 == 0){
			return ((t[i].F + t[i].S) % MOD + SUMA) % MOD;
		}
		int s = (p + k)/2;
		SUMA += t[i].F;
		SUMA %= MOD;
		return (spr(p,s,as(i,0),S,l,SUMA) + spr(s+1,k,as(i,1),S,l,SUMA)) % MOD;
	}

} tab[2];

void dodaj(int i,int x){
	i = (i + MOD) % MOD;
	tab[i%2].add(i/2 + 1, i/2 + 1, 1, tab[i%2].pd, 0, x);
}

int licz(int S){
	int wynik = 0;
	for(int i=0; i<2; i++){
		wynik += tab[i%2].spr(1,tab[i%2].pd, 0, S, (i%2),0);
	}
	return wynik%MOD;
}

int main(){
	tab[0].init((MOD+9)/2);
	tab[1].init((MOD+9)/2);
	int n;
	cin >> n;
	int S = 0;
	int wynik;
	dodaj(MOD,1);
	for(int i=0,a; i<n; i++){
		wynik = 0;
		cin >> a;
		wynik = licz((S + a)% MOD);
		dodaj((-S-a)%MOD, wynik);
		S += a;
		S %= MOD;
	}
	cout << wynik << "\n";
}