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
#include <bits/stdc++.h>
#define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr<<#x<<" "<<x<<endl
#define ll long long 
#define st first
#define nd second
using namespace std;

int n, t, pref[300003], a[300003], mod = 1e9 + 7, x, temp, base = 1, tree[3][1500006], ile, nie, res, sum;
map <int, int> M;
vector <int> V;

void baza(int v, int a, int b, int l, int r, int par) {
	if (a > r || b<l || l>r) return;
	if (a >= l && b <= r) {
		sum = (sum + tree[par][v]) % mod;
		return;
	}
	int mid = (a + b) / 2;
	baza(v * 2, a, mid, l, r, par);
	baza(v * 2 + 1, mid + 1, b, l, r, par);
}
int main()
{
	qio;
	cin >> n;
	M[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = (pref[i - 1] + a[i]) % mod;
		M[pref[i]] = 1;
	}
	ile = 0;
	for (auto it : M) {
		ile++;
		M[it.st] = ile;
		V.push_back(it.st);
	}

	while (base < ile) base *= 2;
	temp = base;
	while (temp > 0) {
		tree[0][temp] = 1;
		temp /= 2;
	}
	for (int i = 1; i <= n; i++) {
		auto it = lower_bound(V.begin(), V.end(), pref[i]);
		x = it - V.begin();
		sum = 0;
		baza(1, 0, base - 1, 0, x, pref[i] % 2);
		baza(1, 0, base - 1, x + 1, base - 1, 1 - (pref[i] % 2));
		temp = x + base;

		while (temp > 0) {
			tree[pref[i] % 2][temp] = (tree[pref[i] % 2][temp] + sum) % mod;
			temp /= 2;
		}
	}
	cout << sum << endl;

	/*if (pref[n] < mod) {
		if (nie % 2 == 1) {
			cout << 0 << endl;
			return 0;
		}
		nie = 0;
		for (int i = 1; i <= n; i++) {
			if (nie == 0 && a[i] % 2 == 0) ile++;
			else if (nie == 0 && a[i] % 2 == 1) nie++;
			else if (nie == 1 && a[i] % 2 == 1) {
				nie = 0;
				ile++;
			}
		}
		res = 1;
		for (int i = 1; i < ile; i++) {
			res = (res * 2) % mod;
		}
		cout << res << endl;
	}
	else {
		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < i; j++) {
				if (((pref[i] - pref[j]) % mod) % 2 == 0) dp[i] = (dp[i] + dp[j]) % mod;
			}
		}
		cout << dp[n] << endl;
	}*/


}