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
#include<cstdio>
#include<algorithm>
#include<vector>
#define S 524288
using namespace std;
typedef long long ll;

ll mod = 1000000007;

ll pref[S];

vector < pair < ll, int > > V;
int T[S];

ll tree[2*S+7][2];

ll query(int l, int r, int l2, int r2, int w, int m){
    if(l > r2 || r < l2)
        return 0;
    if(l >= l2 && r <= r2){
        return tree[w][m];
    }
    int sr = (l+r)/2;
    ll p = query(l,sr,l2,r2,w*2,m) + query(sr+1,r,l2,r2,w*2+1,m);
    if(p >= mod)
        p -= mod;
    return p;
}

void upd(int w){
    w = w+S-1;
    while(w != 1){
        w /= 2;
        for(int i = 0; i < 2;i++){
            tree[w][i] = tree[w*2][i] + tree[w*2+1][i];
            if(tree[w][i] >= mod)
                tree[w][i] -= mod;
        }
    }
}

int main(void){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n;i++){
        scanf("%lld",&pref[i]);
        pref[i] += pref[i-1];
        if(pref[i] >= mod)
            pref[i] -= mod;
        V.push_back({pref[i],i});
    }
    sort(V.begin(),V.end());
    ll p = -1;
    int tmp = 0;
    for(int i = 0; i < V.size();i++){
        if(V[i].first != p){
            tmp++;
            p = V[i].first;
        }
        T[V[i].second] = tmp;
    }
    ll odp = 0;
    for(int i = 1; i <= n;i++){
        ll p = query(1,S,1,T[i],1,pref[i]%2) + query(1,S,T[i]+1,S,1,(pref[i]+1)%2);
        if(pref[i] % 2 == 0)
            p++;
        if(p >= mod)
            p -= mod;
        //printf("%d %d %d %lld %lld*\n",i,T[i],pref[i]%2,pref[i],p);
        tree[T[i]+S-1][pref[i]%2] += p;
        if(tree[T[i]+S-1][pref[i]%2] >= mod)
            tree[T[i]+S-1][pref[i]%2] -= mod;
        odp = p;
        upd(T[i]);
    }
    printf("%lld",odp);
    return 0;
}