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
#include <bits/stdc++.h>
using namespace std;
#define int long long
void imax(int &a, int b){
	a=max(a, b);
}
void imin(int &a, int b){
	a=min(a, b);
}
void lmax(long long &a, long long b){
	a=max(a, b);
}
void lmin(long long &a, long long b){
	a=min(a, b);
}
/*
	WARNING: I'm using strange bracket style!
*/
#define quad pair <pair <int, int>, pair <int, int> >
#define PP first.first
#define NP first.second
#define CPP second.first
#define CNP second.second
const int MOD=1000000007;
const int P=1048576*1024;
const int SIZE=10000000;
inline int fastMod(int x, int y){
	return x+y>MOD ? x+y-MOD:x+y;
}
inline quad merge(quad &a, quad &b){
	return {{fastMod(a.PP, b.PP), fastMod(a.NP, b.NP)}, {fastMod(a.CPP, b.CPP), fastMod(a.CNP, b.CNP)}};
}
class node{
	public:
	node* l;
	node* r;
	quad Q;
};
node pool[SIZE];
class TREE{
	int a, b, c, B, ptr=1;
	long long res, val;
	void makeChildren(node *u){
		if (!u->l) u->l=pool+ptr++;
		if (!u->r) u->r=pool+ptr++;
	}
	void upd(node *u, int low=0, int high=P-1){
		if (high<a || low>b) return;
		if (a<=low && high<=b)
			{
			if (low%2==0 && c==0) u->Q.PP=fastMod(u->Q.PP, val);
			if (low%2==1 && c==0) u->Q.NP=fastMod(u->Q.NP, val);
			if (low%2==0 && c==1) u->Q.CPP=fastMod(u->Q.CPP, val);
			if (low%2==1 && c==1) u->Q.CNP=fastMod(u->Q.CNP, val);
			return;
			}
		makeChildren(u);
		upd(u->l, low, (low+high)/2);
		upd(u->r, (low+high)/2+1, high);
		u->Q=merge(u->l->Q, u->r->Q);
	}
	void query(node *u, int low=0, int high=P-1){
		if (high<a || low>b) 
			{
			if (B)		(res+=u->Q.PP+u->Q.CPP)%=MOD;
			else		(res+=u->Q.NP+u->Q.CNP)%=MOD;
			return;
			}
		if (a<=low && high<=b)
			{
			if (B)		(res+=u->Q.NP+u->Q.CNP)%=MOD;
			else		(res+=u->Q.PP+u->Q.CPP)%=MOD;
			return;
			}
		makeChildren(u);
		query(u->l, low, (low+high)/2);
		query(u->r, (low+high)/2+1, high);
	}
	public:
	int ask(int x, bool BB){
		return res=0, a=0, b=x, B=BB, query(pool), res;
	}
	void update(int x, int C, int VAL){
		a=b=x, c=C, val=VAL, upd(pool);
	}
};
TREE DP;
long long pref, x, RES;
int n;
void push(){
	long long c1=(pref/MOD)%2, r1=pref%MOD;
	RES=DP.ask(r1, (r1)%2), DP.update(r1, c1, RES);
}
int32_t main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n, DP.update(0, 0, 1);
	while (n--)
		cin>>x, pref+=x, push();
	return cout<<RES<<"\n", 0;
	}