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

using namespace std;

long long PRIME = 1000000007;


struct BSTNode {
    long long sumID;
    long long result;
    long long sumLeft;
    long long sumRight;
    BSTNode* left;
    BSTNode* right;
};

BSTNode* newNode(BSTNode* node, long long sumID){
    node = new BSTNode;
    node->sumID = sumID;
    node->result = 0;
    node->sumLeft = 0;
    node->sumRight = 0;
    node->left = nullptr;
    node->right = nullptr;

    return node;
}

long long sumLessOrEqual(BSTNode* node, long long valueID) {
    if(node == nullptr)
        return 0;
    if(node->sumID <= valueID) {
        return node->result + node->sumLeft + sumLessOrEqual(node->right, valueID);
    }
    else {
        return sumLessOrEqual(node->left, valueID);
    }
}

long long sumGreater(BSTNode* node, long long valueID) {
    if(node == nullptr)
        return 0;
    if(node->sumID > valueID) {
        return node->result + node->sumRight + sumGreater(node->left, valueID);
    }
    else {
        return sumGreater(node->right, valueID);
    }
}

void updateResult(BSTNode* node, long long sumID, long long newResult) {
    if(sumID == node->sumID) {
        node->result += newResult;
    }
    else if(sumID < node->sumID) {
        updateResult(node->left, sumID, newResult);
        node->sumLeft += newResult;
    }
    else {
        updateResult(node->right, sumID, newResult);
        node->sumRight += newResult;
    }
}

BSTNode* insertFromSortedUniqueVector(vector<long long>& sums, int start, int end){
    if(start>end) {
        return nullptr;
    }
    BSTNode *root;
    int mid = (start + end)/2;
    root = newNode(root, sums[mid]);
//
    root->left = insertFromSortedUniqueVector(sums, start,mid - 1);
    root->right = insertFromSortedUniqueVector(sums, mid + 1, end);

    return root;
}

long long mopadulo(long long number, long long prime=PRIME){
    return ((number+prime) % prime) % 2;
}

BSTNode* insertFromVector(vector<long long> sums, long long modFilter) {
    sort(sums.begin(), sums.end());
    vector<long long> filtered;
    long long prev = -1;
    for(long long & sum : sums) {
        if(mopadulo(sum) == modFilter and sum != prev){
            filtered.push_back(sum);
            prev = sum;
        }
    }

    return insertFromSortedUniqueVector(filtered, 0, filtered.size()-1);
}

long long nLoGNSolution(){
    long long n, nextNumber;
    cin >> n;

    vector<long long> sums;

    long long sum = 0;
    sums.push_back(0);
    for(int i = 0; i < n; i++){
        cin >> nextNumber;

        sum += nextNumber;
        sums.push_back(sum%PRIME);
    }
    BSTNode* root0 = insertFromVector(sums, 0);
    BSTNode* root1 = insertFromVector(sums, 1);
    long long result;
    for(int i = 0; i < n; i++){
        long long mod = mopadulo(sums[i+1]);
        if(mod == 1) {
            result = sumLessOrEqual(root1, sums[i+1])
                    + sumGreater(root0, sums[i+1]);
            updateResult(root1, sums[i+1], result%PRIME);
        }
        else {
            result = sumLessOrEqual(root0, sums[i+1])
                     + sumGreater(root1, sums[i+1]) + 1;
            updateResult(root0, sums[i+1], result%PRIME);
        }
    }

    return result%PRIME;
}

int main() {
    std::ios_base::sync_with_stdio(false);

    cout<<nLoGNSolution()<<endl;

    return 0;
}