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

using namespace std;

const int s = 1073741824;
const int prime = 1000000007;

unordered_map<int, int> st[2];

void add(int v, int n, int t) {
    n += s;
    while(n) {
        st[t][n] += v;
        st[t][n] %= prime;
        n /= 2;
    }
}

int _sum(int p, int q, int a, int b, int n, int t) {
    if(p <= a && b <= q) {
        return st[t][n]%prime;
    }

    int m = (a + b)/2;
    int s = 0;
    if(p <= m) {
        s += _sum(p, q, a, m, 2*n, t);
        s %= prime;
    }
    if(m + 1 <= q) {
        s += _sum(p, q, m+1, b, 2*n + 1, t);
        s %= prime;
    }

    return s%prime;
}

int sum(int p, int q, int t) {
    return _sum(p, q, 0, s - 1, 1, t);
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> ps(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        ps[i] = (ps[i - 1] + a[i])%prime;
    }

    vector<int> pos(n + 1);
    for(int i = 1; i <= n; i++) {
        pos[i] = ((a[i] - ps[i])%prime + prime)%prime;
    }

    vector<int> bs(n + 1);
    vector<int> ds(n + 1);

    bs[0] = 0;
    ds[0] = prime - 1;
    for(int i = 1; i <= n; i++) {
        bs[i] = ((bs[i - 1] - a[i])%prime + prime) % prime;
        ds[i] = ((ds[i - 1] - a[i])%prime + prime) % prime;
    }

    int r = 1;
    for(int i = 1; i <= n; i++) {
        add(r, pos[i]/2, pos[i]%2);
        if(bs[i] == 0 && ds[i] == prime - 1) {
            r = sum(0, s - 1, 0);
        } else {
            int x = ds[i]%2;
            r = (sum(0, ds[i]/2, x) + sum(bs[i]/2, s - 1, 1 - x))%prime;
        }
    }

    cout << r << "\n";

    return 0;
}