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
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int mod=1000000007;
const int enn=(1<<30)-1;
struct node
{
	int le,ri,s0,s1;
};
//TODO SPRADZIĆ PAMIĘĆ BO PUSHBACKI JEDZĄ DUŻO
vector<node> st;
void addp(int b,int e,int p,int x,int v)
{
//	printf("addp %d %d %d %d %d\n",b,e,p,x,v);
	if(x&1)
	{
		st[p].s1+=v;
		if(st[p].s1>=mod)	st[p].s1-=mod;
	}
	else
	{
		st[p].s0+=v;
		if(st[p].s0>=mod)	st[p].s0-=mod;
	}
	if(b==e)	return;
	if(x<=(b+e)/2)
	{
		if(!st[p].le)
		{
			st.pb({0,0,0,0});
			st[p].le=st.size()-1;
		}
		addp(b,(b+e)/2,st[p].le,x,v);
	}
	else
	{
		if(!st[p].ri)
		{
			st.pb({0,0,0,0});
			st[p].ri=st.size()-1;
		}
		addp((b+e)/2+1,e,st[p].ri,x,v);
	}
}
int gwyn=0;
void gets(int b,int e,int x,int y,int p,bool par)
{
	if(e<x || b>y)	return;
//	printf("gets %d %d %d %d %d %d\n",b,e,x,y,p,par);
	if((x<=b) && (e<=y))
	{
//		printf("TAG\n");
		if(par)	gwyn+=st[p].s1;
		else	gwyn+=st[p].s0;
		if(gwyn>=mod)	gwyn-=mod;
		return;
	}
	if(st[p].le)	gets(b,(b+e)/2,x,y,st[p].le,par);
	if(st[p].ri)	gets((b+e)/2+1,e,x,y,st[p].ri,par);
}
int main()
{
	st.pb({0,0,0,0});
	st.pb({0,0,0,0});
	
	int n;
	scanf("%d",&n);
	vector<int> v(n+1);
	for(int i=1;i<=n;++i)	scanf("%d",&v[i]);

	addp(0,enn,1,0,1);	//stan początkowy
	int ptr=0;			//nasz shift
	for(int i=1;i<=n;++i)
	{
//		printf("%d:\n",i);
		ptr-=v[i];
		if(ptr<0)	ptr+=mod;

		gwyn=0;
//		printf("gets %d %d %d %d %d %d\n",0,enn,0,ptr-1,1,!(ptr&1));
//		printf("gets %d %d %d %d %d %d\n",0,enn,ptr,mod-1,1,ptr&1);
		gets(0,enn,0,ptr-1,1,!(ptr&1));
		gets(0,enn,ptr,mod-1,1,(ptr&1));
		
		if(i==n)
		{
			printf("%d\n",gwyn);
			return 0;
		}
		addp(0,enn,1,ptr,gwyn);
//		printf("%d!\n",gwyn);
	}
}