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
//Jakub Rozek
//Mopadulo
//czas: n*log(n)
//pamiec: n*log(n)

#include "bits/stdc++.h"
using namespace std;

const int mod=1000000007;
const int mod2=2000000014;

struct node{
    int wp,wn,l,r;
};

vector <node> tree;

void add(int w, long long a, long long b, int x, int e)
{
    if(x%2==0) tree[w].wp=(tree[w].wp+e)%mod;
    else tree[w].wn=(tree[w].wn+e)%mod;
    
    if(a==b) return;
    if(x<=(a+b)/2)
    {
        if(tree[w].l==0)
        {
            tree[w].l=tree.size();
            tree.push_back({0,0,0,0});
        }
        add(tree[w].l,a,(a+b)/2,x,e);
    }
    else
    {
        if(tree[w].r==0)
        {
            tree[w].r=tree.size();
            tree.push_back({0,0,0,0});
        }
        add(tree[w].r,(a+b)/2+1,b,x,e);
    }
}

int ile(int w, long long a, long long b, int c, int d, int e)
{
    if(a>d || b<c) return 0;
    if(c<=a && b<=d)
    {
        if(e==0) return tree[w].wp;
        else return tree[w].wn;
    }
    int odp=0;
    if(tree[w].l) odp+=ile(tree[w].l,a,(a+b)/2,c,d,e);
    if(tree[w].r) odp+=ile(tree[w].r,(a+b)/2+1,b,c,d,e);
    return odp%mod;
}

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

    long long n,a,b,c,d,x,wyn,f;

    a=0;
    b=mod-1;
    c=mod;
    d=mod2-1;

    cin>>n;
    wyn=1;
    f=0;
    tree.push_back({0,0,0,0});
    for(int i=1; i<=n; ++i)
    {
        cin>>x;
        if(x%2) f=1-f;

        a=(a+mod2-x)%mod2;
        b=(b+mod2-x)%mod2;
        c=(c+mod2-x)%mod2;
        d=(d+mod2-x)%mod2;

        add(0,0,mod2-1, (a+x)%mod2, wyn);

        wyn=0;
        if(a<b) wyn+=ile(0,0,mod2-1, a,b,f);
        else wyn+=ile(0,0,mod2-1, 0,b,f) + ile(0,0,mod2-1, a,mod2-1,f);
        wyn%=mod;
        if(c<d) wyn+=ile(0,0,mod2-1, c,d,1-f);
        else wyn+=ile(0,0,mod2-1, 0,d,1-f) + ile(0,0,mod2-1, c,mod2-1,1-f);
        wyn%=mod;
    }

    cout<<wyn<<"\n";
    return 0;
}