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
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define p_b push_back
#define m_p make_pair
#define fi first
#define se second
 
ll inf = 8000000000000000000;
ll mod = 1000000007;
const int maxn = 300003;

vector<pair<ll, ll>> tree[2];
int rdrz = 1;

void ins(int r, int v, int x, ll val){
    tree[r][v] = {x, val};
    while(v!=1){
        v >>= 1;
        tree[r][v].fi = max(tree[r][v*2].fi, tree[r][v*2+1].se);
        tree[r][v].se = tree[r][v*2].se+tree[r][v*2+1].se;
    }
}

ll snp(int r, int a, int b, int x, int y, int v){
    if(a>b || !(a>=0 && b<=rdrz-1)) return 0;
    if(x>=a && y<=b) return tree[r][v].se;
    int sr = (x+y)>>1;
    ll res = 0;
    if(sr>=a && x<=b) res += snp(r, a, b, x, sr, v*2);
    if(y>=a && sr+1<=b) res += snp(r, a, b, sr+1, y, v*2+1);
    return res;
}

int mth(vector<pair<int, int>> &t, int x){
    int p = 0, k = (int)t.size()-1, res = -1;
    while(p<=k){
        int sr = (p+k)/2;
        if(t[sr].fi>=x){
            k = sr-1;
            res = t[sr].se;
        }
        else p = sr+1;
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    int n; cin>>n;
    vector<ll> t1(n), suf(n);
    for(int i = 0; i<n; i++)
        cin>>t1[i];

    vector<pair<int, int>> pa, npa;
    for(int i = n-1; i>=0; i--){
        suf[i] = t1[i];
        if(i+1<n) suf[i] += suf[i+1];
        if(((suf[i])%mod)%2) npa.p_b({suf[i]%mod, i});
        else pa.p_b({suf[i]%mod, i});
    }

    sort(pa.begin(), pa.end());
    sort(npa.begin(), npa.end());
    vector<int> gnd(n);
    for(int i = 0; i<(int)pa.size(); i++)
        gnd[pa[i].se] = i;

    for(int i = 0; i<(int)npa.size(); i++)
        gnd[npa[i].se] = i;

    int nb = max((int)npa.size(), (int)pa.size());
    while(rdrz<nb)
        rdrz <<= 1;

    tree[0].resize(rdrz*2);
    tree[1].resize(rdrz*2);
    vector<ll> dp(n);
    //for(auto i: pa)
    //    cout<<i.fi<<" "<<i.se<<"   ";
//
    //cout<<endl;
//
    //for(auto i: npa)
    //    cout<<i.fi<<" "<<i.se<<"   ";
//
    //cout<<endl;
    //for(auto i: gnd)
    //    cout<<i<<" ";
//
    //cout<<endl;
    for(int i = 0; i<n; i++){
        ll val = 1;
        if(i) val = dp[i-1];
        if((suf[i]%mod)%2) ins(1, gnd[i]+rdrz, suf[i]%mod, val);
        else ins(0, gnd[i]+rdrz, suf[i]%mod, val);
        pair<ll, ll> mp = {0, 0};
        if(i!=n-1) mp = {suf[i+1]/mod, suf[i+1]%mod};
        int nw1 = mth(npa, mp.se), nw2 = mth(pa, mp.se), wnp = rdrz, wp = rdrz;
        if(nw1>=0) wnp = gnd[nw1];
        if(nw2>=0) wp = gnd[nw2];
        //cout<<wp<<" "<<wnp<<endl;
        if((mp.se%2)%2){
            //cout<<"^"<<endl;
            dp[i] += snp(0, 0, wp-1, 0, rdrz-1, 1);
            dp[i] += snp(1, wnp, rdrz-1, 0, rdrz-1, 1);
        }
        else{
            //cout<<"&"<<endl;
            dp[i] += snp(0, wp, rdrz-1, 0, rdrz-1, 1);
            dp[i] += snp(1, 0, wnp-1, 0, rdrz-1, 1);
        }

        //cout<<dp[i]<<"*"<<endl;
        dp[i] %= mod;
    }

    cout<<dp[n-1]<<endl;
}