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
#include <bits/stdc++.h>

int n;
int mod = 1000000007;
const int base = 1024 * 1024;

int dp[300003];
int tab[300003];
int sumy[300003];
int odwr[600006];
std::map<int, int> mapa;

int drzewo[2][2 * base];

void dodaj(int x, int ktora, int wartosc) {
	x += base;
	while (x > 0) {
		drzewo[ktora][x] = drzewo[ktora][x] + wartosc;
		if (drzewo[ktora][x] >= mod)
			drzewo[ktora][x] -= mod;
		x /= 2;
	}
}

int przedzial(int x, int y, int ktora) {
	int wynik = 0;
	x += base - 1;
	y += base + 1;
	while ((x/2) != (y/2)) {
		if (x % 2 == 0) 
			wynik = wynik + drzewo[ktora][x + 1];
		if (wynik >= mod)
			wynik -= mod;

		if (y % 2 == 1) 
			wynik = (wynik + drzewo[ktora][y - 1]) % mod;
		if (wynik >= mod)
			wynik -= mod;
	
		x /= 2;
		y /= 2;	
	}
	return wynik;
}

int main() {
	scanf("%d", &n);
	dp[0] = 1;

	mapa[0] = 1;
	mapa[mod] = 1;

	int suma = 0;
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tab[i]);
		suma += tab[i];
		if (suma >= mod)
			suma -= mod;
		sumy[i] = suma;
		mapa[suma] = mapa[suma + 1] = 1;
	}
	int skal = 1;
	for (auto i : mapa) {
		mapa[i.first] = skal;
		odwr[skal] = i.first;
		skal++;
	}
	dodaj(mapa[0], 0, 1);	

	for (int i = 1; i <= n; i++) {
		int suma = mapa[sumy[i]];
		int ktora = sumy[i] & 1;
		dp[i] = przedzial(0, suma, ktora) + przedzial(suma + 1, skal - 1, ktora^1);
		if (dp[i] >= mod)
			dp[i] -= mod;
		dodaj(suma, ktora, dp[i]);
	}
	printf("%d\n", dp[n]);
}