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
116
117
#define pb push_back
#define mp make_pair
#define fi first
#define se second 
#define all(...) begin(__VA_ARGS__) , end(__VA_ARGS__)
#define boost {ios_base::sync_with_stdio(false); cin.tie(); cout.tie();}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
constexpr ll nax = 3e5+6969, INF = 2e10+6969, mod = 1e9 + 7;

int n, N[2];
ll t[nax], ans;
set <ll> S[2];
vector <pair<ll, PLL>> st[2];

void show(int par)
{
	printf("par == %d\n", par);
	for(int i=1;i<N[par] * 2; i++)
	{
		printf("(%lld: %lld - %lld) ", st[par][i].fi, st[par][i].se.fi, st[par][i].se.se);
		if(((i+1)&i) == 0) puts("");
	}
	puts("");
}
void insert(int par, int g, ll where, ll x)
{
	if(where == st[par][g].se.fi && where == st[par][g].se.se)
	{
		st[par][g].fi += x;
		if(st[par][g].fi >= mod) st[par][g].fi -= mod;
		return;
	}
	if(where <= st[par][g*2].se.se) insert(par, g * 2, where, x);
	else insert(par, g * 2 + 1, where, x);
	st[par][g].fi = (st[par][g * 2].fi + st[par][g * 2 + 1].fi) % mod;
}
ll query(int par, int g, ll x, ll y)
{
	//  printf("%d %d %lld %lld\n", par, g, x, y);
	//  printf("seg: %lld %lld\n", st[par][g].se.fi, st[par][g].se.se);
	if(x <= st[par][g].se.fi && st[par][g].se.se <= y)
	{
		//  puts("mamy to");
		return st[par][g].fi;
	}
	ll mid = st[par][g*2].se.se;
	ll w = 0;
	if(x <= mid) w += query(par, g * 2, x, y);
	if(y > mid) w += query(par, g * 2 + 1, x, y);
	return w % mod;
}

int main()
{
	scanf("%d", &n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld", &t[i]);
		t[i] += t[i-1];
		if(t[i] >= mod) t[i] -= mod;
		S[t[i] % 2].insert(t[i]);
	}
	S[0].insert(0);
	S[1].insert(1);
	S[0].insert(mod + 1);
	S[1].insert(mod + 2);
	for(int turn = 0; turn < 2; turn++)
	{
		N[turn] = 1;
		while(N[turn] < S[turn].size()) N[turn] <<= 1;
		st[turn].resize(N[turn] * 2);
		ll K = mod + 1;
		if(turn) K++;
		for(int i=0;i<N[turn];i++) st[turn][i+N[turn]].se = mp(K, K);
		int cnt = 0;
		for(auto e: S[turn])
		{
			st[turn][N[turn]+cnt].se = mp(e, e);
			cnt++;
		}
		for(int i = N[turn]-1;i>0;i--) st[turn][i].se = mp(st[turn][i*2].se.fi, st[turn][i*2+1].se.se);
	}
	
	insert(0, 1, 0, 1);
	//  show(1);
	
	for(int i=1;i<=n;i++) 
	{
		//  printf("i: %d\n", i);
		ll wyn = 0;
		if(t[i] % 2 == 0)
		{
			wyn = query(0, 1, 0, t[i]) + query(1, 1, t[i] + 1, mod + 2);
			wyn %= mod;
		}
		else
		{
			wyn = query(1, 1, 1, t[i]) + query(0, 1, t[i] + 1, mod + 1);
			wyn %= mod;
		}
		insert((t[i]%2), 1, t[i], wyn);
		ans = wyn;
	}
	
	printf("%lld\n", ans);
	return 0;
}