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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;

int n;
ll arr[300009];
ll pref[300009];

ll tree[2][1<<20];
int base = 1, pref_cnt = 0;
ll dp;

set<ll> pref_set;
unordered_map<ll, int> pref_pos;

void add(int v, ll x, int which) {
    v += base-1;
    while(v >= 1) {
        tree[which][v] = (tree[which][v] + x) % MOD;
        v >>= 1;
    } 
}

ll getsum(int l, int r, int v, int tl, int tr, int which) {
    if(r < tl or tr < l)
        return 0;
    else if(l <= tl and tr <= r)
        return tree[which][v];
    else
        return (getsum(l,r,2*v,tl,(tl+tr)/2,which) + getsum(l,r,2*v+1,(tl+tr)/2+1,tr,which)) % MOD;
}

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

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        pref[i] = (pref[i-1] + arr[i]) % MOD;
        pref_set.insert(pref[i]);
    }

    for(auto x : pref_set)
        pref_pos[x] = ++pref_cnt;
    while(base <= pref_cnt)
        base <<= 1;

    add(1, 1, 0);
    for(int i = 1; i <= n; i++) {
        int pos = pref_pos[pref[i]];
        int which = pref[i] % 2;
        dp = (getsum(1,pos,1,1,base,which) + getsum(pos+1,pref_cnt,1,1,base,which^1)) % MOD;
        add(pos, dp, which);
    }

    cout << dp << "\n";

    return 0;
}