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
#include <iostream>
#include <map>
using namespace std;
const int MOD = 1e9+7;

int n;
int input[300000];
map<int,int> in_tree_idx[2]; // 0-even, 1-odd
long long tree[2][1100000]; // 0-even, 1-odd
int leaves[2]; //0-even, 1-odd

void update(int parity, int idx, long long val) {
    idx += leaves[parity];
    while(idx > 0) {
        tree[parity][idx] += val;
        tree[parity][idx] %= MOD;
        idx /= 2;
    }
}

long long query(int parity, int l, int r) {
    long long out = 0;
    l += leaves[parity];
    r += leaves[parity];
    out += tree[parity][l];
    if(l != r) out += tree[parity][r];
    while(l/2 != r/2) {
        if(l%2 == 0) out += tree[parity][l+1];
        if(r%2 == 1) out += tree[parity][r-1];
        l /= 2; r /= 2;
    }
    return out % MOD;
}

int main() {
    cin >> n;
    int sum = 0;
    in_tree_idx[0][0] = 0;
    for(int i=0; i<n; i++) {
        cin >> input[i];
        sum += input[i];
        sum %= MOD;
        in_tree_idx[sum%2][sum] = 0;
    }
    for(int parity=0; parity<2; parity++) {
        int counter = 0;
        for(auto p : in_tree_idx[parity]) in_tree_idx[parity][p.first] = counter++;
        leaves[parity] = 1;
        while(leaves[parity] < counter) leaves[parity] *= 2;
    }
    update(0, in_tree_idx[0][0], 1);
    sum = 0;
    long long out;
    for(int i=0; i<n; i++) {
        sum += input[i];
        sum %= MOD;
        int my_parity = sum % 2;
        out = 0;
        if(my_parity == 0) {
            auto bound = in_tree_idx[0].lower_bound(sum);
            if(bound != in_tree_idx[0].end()) {
                out += query(0,0,bound->second);
                out %= MOD;
            }
            bound = in_tree_idx[1].upper_bound(sum);
            if(bound != in_tree_idx[1].end()) {
                out += query(1,bound->second,leaves[1]-1);
                out %= MOD;
            }
        } else {
            auto bound = in_tree_idx[1].lower_bound(sum);
            if(bound != in_tree_idx[1].end()) {
                out += query(1,0,bound->second);
                out %= MOD;
            }
            bound = in_tree_idx[0].upper_bound(sum);
            if(bound != in_tree_idx[0].end()) {
                out += query(0,bound->second,leaves[0]-1);
                out %= MOD;
            }
        }
        update(my_parity, in_tree_idx[my_parity][sum], out);
    }
    cout << out << endl;
}