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
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);

	using ui = int;

	const ui mod = 1e9 + 7;
	const ui roz = 31e6;
	ui nw = 2;
	vector<array<ui,4>> d(roz);
	const ui rr = (1ll << 30) - 1;
	int n;
	cin >> n;
	vector<ui> aa(n);
	REP(i,n) cin >> aa[i];
	debug(aa);
	auto bud = [&](ui w) {
		if (d[w][2] != 0) return;
		d[w][2] = nw;
		++nw;
		d[w][3] = nw;
		++nw;
	};
	ui p, k, v, g;
	function<void(ui,ui,ui)> akt = [&](ui w, ui a, ui b) {
		if (a > k || b < p)
			return;
		if (a >= p && b <= k) {
			d[w][g] += v;
			if (d[w][g] >= mod) {
				d[w][g] -= mod;
			}
			debug(w, a, b, p, k, v, g);
			return;
		}
		bud(w);
		akt(d[w][2], a, (a + b) / 2);
		akt(d[w][3], (a + b) / 2 + 1, b);
	};
	function<ui(ui,ui,ui)> zap = [&](ui w, ui a, ui b) {
		if (p < a || p > b)
			return 0;
		ui ans = 0;
		ans += d[w][p % 2];
		if (d[w][2]) {
			ans += zap(d[w][2], a, (a + b) / 2);
			if (ans >= mod) {
				ans -= mod;
			}
			ans += zap(d[w][3], (a + b) / 2 + 1, b);
			if (ans >= mod) {
				ans -= mod;
			}
		}
		debug(w, a, b, p, ans);
		return ans;
	};
	p = 0;
	k = mod - 1;
	v = 1;
	g = 0;
	akt(1, 0, rr);
	vector<ui> dp(n);
	ui pref = 0;
	REP(i,n) {
		pref += aa[i];
		if (pref >= mod) {
			pref -= mod;
		}

		p = pref;
		dp[i] = zap(1, 0, rr);

		p = 0;
		k = pref - 1;
		v = dp[i];
		g = (pref + 1) % 2;
		akt(1, 0, rr);

		p = pref;
		k = mod - 1;
		g = pref % 2;
		akt(1, 0, rr);
	}
	cout << dp[n - 1] << '\n';
}