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
#include <cstdio>
#include <map>

constexpr int N = 300 * 1000 + 1;
constexpr int B = 1 << 19;
constexpr int S = B << 1;
constexpr long long M = 1000 * 1000 * 1000LL + 7;

long long nums[N];
long long even[S];
long long odd[S];

long long new_zero;
std::map<long long, int> scale;

void insert(long long* tree, int where, long long num)
{
	where += B;
	while (where > 0)
	{
		tree[where] = (tree[where] + num) % M;
		where /= 2;
	}
}

long long read(long long* tree, int ob_w, int ob_p, int ob_k, int sz_p, int sz_k)
{
	if (ob_p >= sz_k || ob_k <= sz_p)
		return 0;
	if (ob_p >= sz_p && ob_k <= sz_k)
		return tree[ob_w];
	int mid = (ob_p + ob_k) / 2;
	return (read(tree, ob_w * 2, ob_p, mid, sz_p, sz_k) + read(tree, ob_w * 2 + 1, mid, ob_k, sz_p, sz_k)) % M;
}

long long get_even() {
    if (new_zero == 0) {
        return even[1];
    }
    if (new_zero & 1) {
        return (read(odd, 1, 0, B, scale[new_zero], scale[M]) + read(even, 1, 0, B, scale[0], scale[new_zero])) % M;
    } else {
        return (read(even, 1, 0, B, scale[new_zero], scale[M]) + read(odd, 1, 0, B, scale[0], scale[new_zero])) % M;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &nums[i]);
    }
    scale[0] = 0;
    scale[M] = 0;
    int s = 0;
    for (int i = 0; i < n; ++i) {
        new_zero = (new_zero - nums[i] + M) % M;
        scale[new_zero] = 0;
    }
    for (auto& it : scale) {
        it.second = s++;
    }

    new_zero = 0;
    insert(even, scale[0], 1);
    new_zero = (new_zero + M - nums[0]) % M;
    for (int i = 1; i < n; ++i) {
        long long evens = get_even();
        insert((new_zero & 1) ? odd : even, scale[new_zero], evens);
        new_zero = (new_zero + M - nums[i]) % M;
    }
    long long evens = get_even();
    printf("%lld\n", evens);
}