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
#include <bits/stdc++.h>
#define QED return 0;}
#define main() int main(){
#define ll long long
#define f first
#define s second
using namespace std;

const ll mod = 1e9 + 7;
const ll base = 1 << 19;
ll tree[2 * base][2]; ///0 - parzyste, 1 - nieparzyste
pair <ll, ll> t[300007];
map <ll, ll> mapa;
ll n, cnt, dp;

void add(ll x, ll val, bool wh){
	x += base;
	while(x > 0){
		tree[x][wh] += val;
		tree[x][wh] %= mod;
		x /= 2;
	}
}

ll give(ll x, ll y, bool wh){
	x += base - 1;
	y += base + 1;
	ll w = 0;
	while(x / 2 != y / 2){
		if(x % 2 == 0) w += tree[x + 1][wh];
		if(y % 2 == 1) w += tree[y - 1][wh];
		x /= 2;
		y /= 2;
		w %= mod;
	}
	return w;
}

main()
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> t[i].f;
		t[i].f += t[i - 1].f;
		t[i].f %= mod;
		mapa[t[i].f];	
	}
	for(auto it = mapa.begin(); it != mapa.end(); it++){
		cnt++;
		it -> second = cnt;
	}
	for(int i = 1; i <= n; i++){
		t[i].s = mapa[t[i].f];
	}
	
	add(0, 1, 0);
	for(int i = 1; i <= n; i++){
		dp = 0;
		if(t[i].f % 2 == 0){
			dp = give(0, t[i].s, 0) + give(t[i].s, n, 1);
			dp %= mod;
			add(t[i].s, dp, 0);
		}
		else{
			dp = give(0, t[i].s, 1) + give(t[i].s, n, 0);
			dp %= mod;
			add(t[i].s, dp, 1);
		}
		if(i == n) cout << dp;
	}
	
QED