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

int n,a,pref[300005],dpa[2000004],dnp[2000004],dp[300005],lp = 0,Base = 1;

set <int> S;

map <int,int> Map;

int dodajMOD(int A,int B)
{
    return (A + B) % 1000000007;
}

void INSERT(int * tab,int x,int w)
{
    while(x > 0)
    {
        tab[x] = dodajMOD(tab[x],w);
        x >>= 1;
    }
    return;
}

int ileMniejszychRownych(int * tab,int x)
{
    int wyn = tab[x];
    while(x > 0)
    {
        if((x & 1) == 1)
        {
            wyn = dodajMOD(wyn,tab[x - 1]);
        }
        x >>= 1;
    }
    return wyn;
}

int ileWiekszych(int * tab,int x)
{
    int wyn = 0;
    while(x > 0)
    {
        if((x & 1) == 0)
        {
            wyn = dodajMOD(wyn,tab[x + 1]);
        }
        x >>= 1;
    }
    return wyn;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n;
    for(int i = 1;i <= n; i++)
    {
        cin>>a;
        pref[i] = dodajMOD(pref[i - 1],a);
    }
    
    //skalowanie
    for(int i = 0;i <= n; i++)
        S.insert(pref[i]);
    
    for(set<int>::iterator it = S.begin();it != S.end(); it++)
    {
        int x = * it;
        Map[x] = lp;
        lp++;
    }
    //
    
    while(Base < lp)
        Base <<= 1;
    
    INSERT(dpa,Base,1);
    for(int i = 1;i <= n; i++)
    {
        int pos = Map[pref[i]] + Base;
        if((pref[i] & 1) == 0)
        {
            dp[i] = dodajMOD(ileMniejszychRownych(dpa,pos),ileWiekszych(dnp,pos));
            INSERT(dpa,pos,dp[i]);
        }
        else
        {
            dp[i] = dodajMOD(ileMniejszychRownych(dnp,pos),ileWiekszych(dpa,pos));
            INSERT(dnp,pos,dp[i]);
        }
    }
    cout<<dp[n]<<'\n';
    return 0;
}