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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define gp gp_hash_table<ll, ll, chash>

const ll N = 1e9+100;
const int MOD = 1e9+7;
const int MAXN = 3e5;

ll a[MAXN], pref[MAXN+1], dp[MAXN+1];

unsigned hash_f(unsigned x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}
 
struct chash {
    ll operator()(ll x) const { return hash_f(x); }
};

gp even, odd;
 
ll get(ll x, gp *seg) {
    auto res = seg->find(x);
    return (res == seg->end()) ? 0 : res->second;
}

void modify(ll p, ll val, gp *seg) {
    for ((*seg)[p += N] += val; p > 0; p >>= 1) {
        (*seg)[p >> 1] = get(p, seg) + get(p ^ 1, seg);
    }
}
 
ll query(ll l, ll r, gp *seg) {
    ll res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += get(l++, seg);
        if (r & 1)
            res += get(--r, seg);
    }
    return res;
}

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

    int n;
    cin>>n;

    for (int i=0; i<n; ++i) cin>>a[i];

    pref[0] = 0;
    for (int i=1; i<=n; ++i) {
        pref[i] = (pref[i-1]+a[i-1])%MOD;
    }

    dp[0] = 1;
    modify(0, 1, &even);

    for (int i=1; i<=n; ++i) {
        if (pref[i]%2 == 0) {
            dp[i] = (query(0, pref[i]+1, &even) + query(pref[i]+1, MOD+1, &odd))%MOD;
            modify(pref[i], dp[i], &even);
        } else {
            dp[i] = (query(0, pref[i]+1, &odd) + query(pref[i]+1, MOD+1, &even))%MOD;
            modify(pref[i], dp[i], &odd);
        }
    }

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