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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

void rec_update(int const node, vector<int> & tree) {
    if(node == 0) return;
    
    tree[node] = tree[2*node] + tree[2*node + 1];
    tree[node] %= MOD;
    rec_update(node/2, tree);
}

void tree_update(int const node, int const val, int const pow, vector<int> & tree) {
    tree[pow + node - 1] += val;
    tree[pow + node - 1] %= MOD;
    rec_update((pow + node - 1) / 2, tree);
}

int rec_query(int const node, int const node_beg, int const node_end, int const beg, int const end, vector<int> const & tree) {
    if(beg <= node_beg && end >= node_end) {
        return tree[node];
    }

    int mid = (node_beg + node_end) / 2;
    int result = 0;

    if(beg <= mid) result += rec_query(2*node, node_beg, mid, beg, end, tree);
    result %= MOD;
    if(end > mid) result +=  rec_query(2*node+1, mid+1, node_end, beg, end, tree);
    result %= MOD;
    
    return result;
}

int tree_query(int const beg, int const end, int const pow, vector<int> const & tree) {
    return rec_query(1, 1, pow, beg, end, tree);
}

void solve(){
    int n;
    cin >> n;

    vector<int> numbers(n);
    for(int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    vector<int> sum_pref(n);
    sum_pref[0] = numbers[0];
    for(int i = 1; i < n; i++) {
        sum_pref[i] = (sum_pref[i-1] + numbers[i]) % MOD; 
    }
    
    vector<int> sort_sum_pref = sum_pref;
    sort(sort_sum_pref.begin(), sort_sum_pref.end());

    vector<int> unique_sort_sum_pref[2];
    
    unique_sort_sum_pref[0].push_back(-2);
    unique_sort_sum_pref[1].push_back(-1);

    for(int i = 0; i < n; i++) {
        if(sort_sum_pref[i] % 2 == 0) {
            if(sort_sum_pref[i] != unique_sort_sum_pref[0].back()) unique_sort_sum_pref[0].push_back(sort_sum_pref[i]);
        }
        else {
            if(sort_sum_pref[i] != unique_sort_sum_pref[1].back()) unique_sort_sum_pref[1].push_back(sort_sum_pref[i]);
        }
    }

    int pow[2] = {1, 1};
    while(pow[0] <= unique_sort_sum_pref[0].size()) pow[0] *= 2;
    while(pow[1] <= unique_sort_sum_pref[1].size()) pow[1] *= 2;

    vector<int> tree[2] = {vector<int>(2*pow[0], 0), vector<int>(2*pow[1], 0)};

    for(int i = 0; i < n; i++) {
        int current_result = 0;
        
        if(sum_pref[i] % 2 == 0) {
            int indeven = lower_bound(unique_sort_sum_pref[0].begin(), unique_sort_sum_pref[0].end(), sum_pref[i]) - unique_sort_sum_pref[0].begin();
            int indodd = upper_bound(unique_sort_sum_pref[1].begin(), unique_sort_sum_pref[1].end(), sum_pref[i]) - unique_sort_sum_pref[1].begin();
            
            current_result += 1;

            current_result += tree_query(1, indeven, pow[0], tree[0]);
            current_result %= MOD;
            
            if(indodd < unique_sort_sum_pref[1].size()) current_result += tree_query(indodd, pow[1], pow[1], tree[1]);
            current_result %= MOD;
            
            tree_update(indeven, current_result, pow[0], tree[0]);
        }
        else {
            int indodd = lower_bound(unique_sort_sum_pref[1].begin(), unique_sort_sum_pref[1].end(), sum_pref[i]) - unique_sort_sum_pref[1].begin();
            int indeven = lower_bound(unique_sort_sum_pref[0].begin(), unique_sort_sum_pref[0].end(), sum_pref[i]) - unique_sort_sum_pref[0].begin();

            current_result += tree_query(1, indodd, pow[1], tree[1]);
            current_result %= MOD;
            
            if(indeven < unique_sort_sum_pref[0].size()) current_result += tree_query(indeven, pow[0], pow[0], tree[0]);
            current_result %= MOD;

            tree_update(indodd, current_result, pow[1], tree[1]);
        }
        
        if(i == n-1) cout << current_result << "\n";
    }
}

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

    solve();

    return 0;
}