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
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;
typedef unsigned int uint;
const unsigned int P = 1e9 + 7;
const unsigned int PP = 2*P;

vector<uint> sums;
vector<uint> input;
map<uint, uint> sumnames;

typedef array<uint, 2> S;
S comb(S a, S b) {
    return {(a[0] + b[0]) % P,
            (a[1] + b[1]) % P};
}

const int DELTA = 1 << 19;
S T[2 * DELTA];

void add_pos(uint sum, int pos) {
    int v = sumnames[sum] + DELTA;
    T[v][sum % 2] += pos;
    T[v][sum % 2] %= P;
    v /= 2;
    while (v) {
        T[v] = comb(T[2*v], T[2*v+1]);
        v /= 2;
    }
}

S get_total(uint Ls, uint Rs, int v, int vL, int vR) {
    uint vLs = vL < sums.size() ? sums[vL] : UINT_MAX;
    uint vRs = vR < sums.size() ? sums[vR] : UINT_MAX;
    if (Ls <= vLs && vRs <= Rs) return T[v];
    if (Rs < vLs || vRs < Ls) return {0, 0};
    int mid = (vL + vR) / 2;
    return comb(get_total(Ls, Rs, 2*v, vL, mid),
                get_total(Ls, Rs, 2*v+1, mid+1, vR));
}

S range(uint start, uint end) {
    //cerr << "[" << start << "; " << end << "] -> ";
    S result;
    if (start <= end) result = get_total(start, end, 1, 0, DELTA - 1);
    else result = comb(get_total(start, PP - 1, 1, 0, DELTA - 1),
                get_total(0, end, 1, 0, DELTA - 1));
    //cerr << result[0] << ", " << result[1] << endl;
    return result;
}

int main() {
    std::ios::sync_with_stdio(false); std::cin.tie();
    int n; cin >> n;
    input.resize(n);
    uint total = 0;
    sums.push_back(total);
    for (int i = 0; i < n; i++) {
        cin >> input[i];
        total += input[i];
        total %= PP;
        sums.push_back(total);
    }

    sort(sums.begin(), sums.end());
    auto last = unique(sums.begin(), sums.end());
    sums.erase(last, sums.end());

    for (int i = 0; i < sums.size(); i++) {
        sumnames[sums[i]] = i;
    }

    add_pos(0, 1);

    total = 0;
    uint r = 0;
    for (int i = 0; i < n; i++) {
        total += input[i];
        total %= PP;
        int A = range((total + P + 1) % PP, total)[total % 2];
        int B = range((total + 1) % PP, (total + P) % PP)[(total % 2) ^ 1];
        //cerr << total << " -> " << A << " + " << B << endl;
        r = (A + B) % P;
        add_pos(total, r);
    }

    cout << r << '\n';
}