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

#define maxn 300010
#define mod 1000000007

using namespace std;

long long tab[maxn], sum[maxn], v[maxn], drzewo[4*maxn][2];
map <int,int> skal;
int r = 1;

void inserty(int x, int gdzie, long long ile) {
    x += r - 1;
    drzewo[x][gdzie] = (drzewo[x][gdzie]+ile)%mod;
    x/=2;
    while(x != 0) {
        drzewo[x][gdzie] = (drzewo[2*x][gdzie]+drzewo[2*x+1][gdzie])%mod;
        x/=2;
    }
}

long long query(int gdzie, int pp, int pk, int zp, int zk, int ktore) {
    if (zp > pk || zk < pp)
        return 0;
    if (zp <= pp && zk >= pk)
        return drzewo[gdzie][ktore];
    int sr = (pp + pk)/2;
    return (query(2*gdzie, pp, sr, zp, zk, ktore) + query(2*gdzie+1, sr+1,pk, zp, zk, ktore))%mod;
}

void skaluj(int n) {
    int wsk = 2;
    skal[v[0]] = 1;
    for (int i = 1; i < n; ++i) {
        if (v[i] != v[i-1]) {
            skal[v[i]] = wsk;
            ++wsk;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> tab[i];
        tab[i] = tab[i]%mod;
        sum[i] = (sum[i-1] + tab[i])%mod;
        //cout << sum[i] << " ";
        v[i] = sum[i];
    }
    //cout << endl;
    sort(v, v+n+1);
    skaluj(n+1);
    while (r < n+1)
        r *= 2;
    long long last = 1;
    for (int i = n; i > 0; --i) {
        if (i == n) {
            inserty(skal[sum[i]], sum[i] % 2, 1);
            last = (tab[i]+1)%2;
            if (i == 1)
                cout << (tab[i]+1)%2 << "\n";
        }
        else {
            long long x = ((tab[i]+1)%2)*last;
            int suma = sum[i-1];
            if (suma % 2 == 0) {
                x = (x + query(1,1,r,skal[suma], r, 0))%mod;
                if (skal[suma] > 1)
                    x = (x + query(1,1,r,1, skal[suma] - 1, 1))%mod;    
            }
            else {
                x = (x + query(1,1,r,skal[suma], r, 1))%mod;
                if (skal[suma] > 1)
                    x = (x + query(1,1,r,1, skal[suma] - 1, 0))%mod;  
            }
            inserty(skal[sum[i]], sum[i] % 2, last);
            //cout << x << endl;
            last = x;
            if (i == 1)
                cout << x << "\n";
        }
        
    }
}