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

using namespace std;

const int N = 300'007;
const int T = 1 << 19;
const int MOD = 1'000'000'007;

int n;
int in[N];

int order[N];
long long pref[N];

int dp[N];
long long tree[4][T + T];

void add(int type, int p, int v)
{
    p += T;
    while (p) {
        tree[type][p] += v;
        p >>= 1;
    }
}

long long ask(int type, int from, int to) 
{
    long long ret = 0;
    from += T, to += T;

    while (from <= to) {
        if (from & 1) {
            ret += tree[type][from];
        }
        
        if (!(to & 1)) {
            ret += tree[type][to];
        }
        
        from = (from + 1) >> 1;
        to = (to - 1) >> 1;
    }

    return ret;
}

void renumber()
{
    vector <int> values;
    for (int i = 0; i <= n; ++i) {
        values.push_back(pref[i] % MOD);
    }

    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    map <int, int> Mapping;
    for (int i = 0; i < (int)values.size(); ++i) {
        Mapping[values[i]] = i + 1;
    }

    for (int i = 0; i <= n; ++i) {
        order[i] = Mapping[pref[i] % MOD];
    }
}

int main() 
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &in[i]);
        pref[i] = pref[i - 1] + in[i];
    }

    renumber();
    
    dp[0] = 1;
    add(0, order[0], dp[0]);
    
    for (int i = 1; i <= n; ++i) {
        long long cur = 0;
        int base = ((pref[i] / MOD & 1) << 1) + (pref[i] & 1);

        for (int t = 0; t < 4; ++t) {
            if (__builtin_popcount(t ^ base) & 1) {
                cur += ask(t, order[i] + 1, n + 1);
            } else {
                cur += ask(t, 1, order[i]);
            }
        }

        dp[i] = cur % MOD;
        add(base, order[i], dp[i]);
//        printf("dp[%d] = %d, base[%d] = %d, order[%d] = %d\n", i, dp[i], i, base, i, order[i]);
    }

    printf("%d\n", dp[n]);
}