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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h> 

using namespace std;

long long vectorSize;
vector<long long> numbers;
vector<long long> prefixSum;
set<long long> parzSet;
set<long long> nparzSet;
map<long long, long long> parzMap;
map<long long, long long> nparzMap;
vector<long long> parzTree;
vector<long long> nparzTree;
long long parzSize;
long long nparzSize;

void Input();
void prepareMaps();
void prepareTrees();
void updateParzVertex(long long vertex, long long toAdd);
void updateNparzVertex(long long vertex, long long toAdd);
long long sumParz(long long vertex, long long l, long long r, long long ll, long long rr);
long long sumNparz(long long vertex, long long l, long long r, long long ll, long long rr);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    Input();
    prepareMaps();
    prepareTrees();
    for (long long i = 1; i <= vectorSize; i++) {
        long long sum = prefixSum[i];
        if (sum % 2) {
            long long toAdd = sumNparz(1, nparzSize / 2, nparzSize - 1, nparzSize / 2, nparzSize / 2 + nparzMap[sum]);
            if (parzSet.lower_bound(sum) != parzSet.end()) {
                toAdd += sumParz(1, parzSize / 2, parzSize - 1, parzSize / 2 + parzMap[*parzSet.lower_bound(sum)], parzSize - 1);
            }
            updateNparzVertex(nparzSize / 2 + nparzMap[sum], toAdd);
        } else {
            long long toAdd = sumParz(1, parzSize / 2, parzSize - 1, parzSize / 2, parzSize / 2 + parzMap[sum]);
            if (nparzSet.lower_bound(sum) != nparzSet.end()) {
                toAdd += sumNparz(1, nparzSize / 2, nparzSize - 1, nparzSize / 2 + nparzMap[*nparzSet.lower_bound(sum)], nparzSize - 1);
            }
            updateParzVertex(parzSize / 2 + parzMap[sum], toAdd);
        }
    }
    long long answer = (prefixSum[vectorSize] % 2) ? nparzTree[nparzSize / 2 + nparzMap[prefixSum[vectorSize]]] : parzTree[parzSize / 2 + parzMap[prefixSum[vectorSize]]];
    cout << answer << endl;
}

void Input() {
    cin >> vectorSize;
    numbers = vector<long long>(vectorSize);
    prefixSum = vector<long long>(vectorSize + 1);
    cin >> numbers[0];
    prefixSum[0] = 0;
    prefixSum[1] = numbers[0];
    parzSet.insert(0);
    if (numbers[0] % 2 == 0) {
        parzSet.insert(numbers[0]);
    } else {
        nparzSet.insert(numbers[0]);
    }
    for (long long i = 1; i < vectorSize; i++) {
        cin >> numbers[i];
        prefixSum[i + 1] = (prefixSum[i] + numbers[i]) % 1000000007;
        if (prefixSum[i + 1] % 2 == 0) {
            parzSet.insert(prefixSum[i + 1]);
        } else {
            nparzSet.insert(prefixSum[i + 1]);
        }
    }
}

void prepareMaps() {
    long long counter = 0;
    for (auto &x : parzSet) {
        parzMap[x] = counter++;
    }
    counter = 0;
    for (auto &x : nparzSet) {
        nparzMap[x] = counter++;
    }
}

void prepareTrees() {
    parzSize = 1;
    while (parzSize < parzSet.size()) {
        parzSize *= 2;
    }
    parzSize *= 2;
    parzTree = vector<long long>(parzSize);
    updateParzVertex(parzSize / 2, 1);
    nparzSize = 1;
    while (nparzSize < nparzSet.size()) {
        nparzSize *= 2;
    }
    nparzSize *= 2;
    nparzTree = vector<long long>(nparzSize);
}

void updateParzVertex(long long vertex, long long toAdd) {
    if (vertex == 0) 
        return;
    parzTree[vertex] += toAdd;
    parzTree[vertex] %= 1000000007;
    updateParzVertex(vertex / 2, toAdd);
}

void updateNparzVertex(long long vertex, long long toAdd) {
    if (vertex == 0) 
        return;
    nparzTree[vertex] += toAdd;
    nparzTree[vertex] %= 1000000007;
    updateNparzVertex(vertex / 2, toAdd);
}

long long sumParz(long long vertex, long long l, long long r, long long ll, long long rr) {
    if(l > rr || r < ll)
        return 0;
    if(l >= ll && r <= rr)
        return parzTree[vertex];
    long long mid = (l + r) / 2;
    return (sumParz(vertex * 2, l, mid, ll, rr) + sumParz(vertex * 2 + 1, mid + 1, r, ll, rr)) % 1000000007;
}

long long sumNparz(long long vertex, long long l, long long r, long long ll, long long rr) {
    if(l > rr || r < ll)
        return 0;
    if(l >= ll && r <= rr)
        return nparzTree[vertex];
    long long mid = (l + r) / 2;
    return (sumNparz(vertex * 2, l, mid, ll, rr) + sumNparz(vertex * 2 + 1, mid + 1, r, ll, rr)) % 1000000007;
}