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 <cstdio>
#include <algorithm>
#define MAKS 300010
#define MOD 1000000007
using namespace std;
int a[MAKS];
int M[MAKS];
int ind[MAKS];
int poz[MAKS];
int rpoz[MAKS];
bool cmp(int i, int j)
{
    if(M[i]!=M[j])return M[i]<M[j];
    return i<j;
}

int LD;
int drz[MAKS*4][2];

void dodaj(int x, int p, int wart)
{
    int akt=LD+x;
    drz[akt][p]=(drz[akt][p]+wart)%MOD;
    akt/=2;
    while(akt>=1)
    {
        drz[akt][p]=(drz[2*akt][p]+drz[2*akt+1][p])%MOD;
        akt/=2;
    }
}

int suma(int a, int b, int p)
{
    int wyn=0;
    a+=LD; b+=LD;
    while(a<b)
    {
        if(a%2==1)
        {
            wyn=(wyn+drz[a][p])%MOD;
            a++;
        }
        a/=2;

        if(b%2==0)
        {
            wyn=(wyn+drz[b][p])%MOD;
            b--;
        }
        b/=2;
    }
    if(a==b)wyn=(wyn+drz[a][p])%MOD;
    return wyn;
}

int main()
{
    int n;
    scanf("%d",&n);
    LD=1;
    while(LD<n+1)LD*=2;
    //printf("LD: %d\n",LD);

    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    M[0]=a[0];
    for(int i=1;i<n;i++)M[i]=(M[i-1]+a[i])%MOD;

    for(int i=0;i<n;i++)ind[i]=i;
    sort(ind,ind+n,cmp);
    for(int i=0;i<n;i++)poz[ind[i]]=i;
    for(int i=n-1;i>=0;i--)
    {
        if(i+1<n && M[ind[i]]==M[ind[i+1]])rpoz[ind[i]]=rpoz[ind[i+1]];
        else rpoz[ind[i]]=poz[ind[i]];
    }

    /*for(int i=0;i<n;i++)printf("%d ",M[i]);
    puts("");
    for(int i=0;i<n;i++)printf("%d ",poz[i]);
    puts("");
    for(int i=0;i<n;i++)printf("%d ",rpoz[i]);
    puts("");*/

    drz[LD][0]=1;
    for(int i=LD-1;i>=1;i--)
    {
        drz[i][0]=drz[2*i][0]+drz[2*i+1][0];
        drz[i][1]=drz[2*i][1]+drz[2*i+1][1];
    }

    for(int i=0;i<n;i++)
    {
        int w=suma(0, rpoz[i]+1, (M[i]%2));
        if(rpoz[i]+2<=n) w = (w + suma(rpoz[i]+2, n, 1-(M[i]%2)))%MOD;
        dodaj(poz[i]+1, (M[i]%2), w);
    }

    printf("%d\n", drz[LD+poz[n-1]+1][(M[n-1]%2)]);
}