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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;

long long mod=1000000007;


struct d{
	long long war;
	int ind;
};

struct prze{
    long long war,pp,kp;
};

prze drze[2][1000000];

vector <d> pnp[2];
long long mn[2];
d sp[500001];


bool operator < (d a,d b){
	 if(a.war<b.war)	return 1;
	 return 0;
}

void setup(int wierz,int parz){
	if(wierz<mn[parz]){
		setup(wierz*2,parz);
		setup(wierz*2+1,parz);
	}else{
        drze[parz][wierz].pp=pnp[parz][wierz-mn[parz]].war;
        drze[parz][wierz].kp=pnp[parz][wierz-mn[parz]].war;
        return;
	}
	drze[parz][wierz*2].pp=drze[parz][wierz*2].pp;
	drze[parz][wierz*2+1].kp=drze[parz][wierz*2+1].kp;
}


void dod(int pocz,int kon,int wierz,int parz,int war){
	if((drze[parz][wierz].pp>=pocz)and(drze[parz][wierz].kp>=kon)){
		drze[parz][wierz].war+=war;
		drze[parz][wierz].war%=mod;
		return;
	}
	if((drze[parz][wierz].kp<pocz)or(drze[parz][wierz].pp>kon))	return;
	if(wierz>=mn[parz])	return;
	dod(pocz,kon,wierz*2,parz,war);
	dod(pocz,kon,wierz*2+1,parz,war);
}

int que(int wierz,int parz){
    if(wierz>1) return (drze[parz][wierz].war+que(wierz/2,parz))%mod;
    return drze[parz][wierz].war;
}

long long n,wyn,ps,pocz,kon;
long long t[500001];
long long g[500001];

int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&t[i]);
		sp[i].war=(sp[i-1].war+t[i])%mod;
		sp[i].war%=mod;
		sp[i].ind=i;
		pnp[sp[i].war%2].push_back(sp[i]);
	}
	sort(pnp[0].begin(),pnp[0].end());
	sort(pnp[1].begin(),pnp[1].end());
	for(int i=0;i<pnp[0].size();i++)	g[pnp[0][i].ind]=i;
	for(int i=0;i<pnp[1].size();i++)	g[pnp[1][i].ind]=i;
	mn[0]=1;
	mn[1]=1;
	while(mn[0]<pnp[0].size())	mn[0]*=2;
	while(mn[1]<pnp[1].size())	mn[1]*=2;
	setup(1,0);
	setup(1,1);
	for(int i=1;i<=n;i++){
        if(i==1)    wyn=1;
        else{
            wyn=que(mn[(t[i-1]%2)]+g[i-1],t[i-1]%2);
        }

        ps=sp[i-1].war;
        //if(t[i]%2==0){
            pocz=(mod-ps)%mod;
            kon=mod-ps-t[i]-1;
        /*}else{
            pocz=mod-ps-t[i];
            kon=mod-ps;
        }*/
        if(pocz<0)  pocz+=mod;
		if(kon<0)	kon+=mod;
		//printf("%d %d %d %d %d\n",i,wyn,pocz,kon,ps);
		if(pocz<kon){
            dod(pocz,kon,1,t[i]%2,wyn);
            dod(0,pocz-1,1,(t[i]%2) ^ 1,wyn);
            dod(kon+1,mod,1,(t[i]%2) ^ 1,wyn);
		}else{
            dod(0,kon,1,t[i]%2,wyn);
            dod(pocz,mod,1,t[i]%2,wyn);
            dod(kon+1,pocz-1,1,(t[i]%2) ^ 1,wyn);
		}

		if(t[i]%2==0)   dod(t[i],t[i],1,t[i]%2,wyn);
	}
	wyn=que(mn[t[n]%2]+g[n],t[n]%2);
	printf("%lld",wyn);
	return 0;
}