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 <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int P = 1'000'000'007;

struct segment_tree {
    const int SIZE = 20;
    vector<long long> elems;
    segment_tree() {
        elems.resize(1 << SIZE);
    }

    long long sum(long a, long b) {
        return sum(a, b, 1, 0, 1 << (SIZE - 1));
    }

    long long sum(long a, long b, long u, long lo, long hi) {
        if (a == lo && b == hi) return elems[u];
        if (b <= a) return 0;
        long mid = (lo + hi) / 2;
        return sum(a, min(b, mid), 2 * u, lo, mid) + sum(max(a, mid), b, 2 * u + 1, mid, hi);
    }

    void add(long pos, long long v) {
        pos += (1 << (SIZE - 1));
        elems[pos] += v;
        if (elems[pos] > P) elems[pos] -= P;
        while (pos /= 2) {
            elems[pos] = elems[2 * pos] + elems[2 * pos + 1];
            if (elems[pos] > P) elems[pos] -= P;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> v;
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    set<long long> s_even, s_odd;
    vector<long long> even, odd;
    long long base{};
    for (int i = 0; i < n; ++i) {
        base += v[i];
        base %= P;
        long long elem = v[i] - base;
        if (elem < 0) elem += P;
        (elem & 1 ? s_odd : s_even).insert(elem);
    }
    unordered_map<long long, int> pos;
    int i = 0;
    odd.resize(size(s_odd));
    for (auto e: s_odd) {
        odd[i] = e;
        pos[e] = i++;
    }
    i = 0;
    even.resize(size(s_even));
    for (auto e: s_even) {
        even[i] = e;
        pos[e] = i++;
    }
    segment_tree odds{}, evens{};

    base = 0;
    long long to_add = 1;
    for (int j = 0; j < n; ++j) {
        base += v[j];
        base %= P;
        long long elem = v[j] - base;
        if (elem < 0) elem += P;
        (elem & 1 ? odds : evens).add(pos[elem], to_add);

        if (base & 1) {
            auto ep = lower_bound(begin(even), end(even), P - base) - begin(even);
            auto op = lower_bound(begin(odd), end(odd), P - base) - begin(odd);
            auto s1 = evens.sum(ep, (long) size(even));
            auto s2 = odds.sum(0, op);
            to_add = s1 + s2;
        } else {
            auto ep = lower_bound(begin(even), end(even), P - base) - begin(even);
            auto op = lower_bound(begin(odd), end(odd), P - base + 1) - begin(odd);
            auto s1 = evens.sum(0, ep);
            auto s2 = odds.sum(op, (long) size(odd));
            to_add = s1 + s2;
        }
    }
    cout << (to_add % P);
}