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
#include <bits/stdc++.h>
using namespace std;
const int L=1<<19, MXN=3e5+10, MOD=1e9+7;
int a[MXN], d[2][L<<1];
map<int, int>mapa;
int query(int p, int k, bool kt)
{
	p+=L-1;
	k+=L-1;
	int r=0;
	while (p <= k)
	{
		if (p&1)	r=(r+d[kt][p])%MOD;
		if (!(k&1))	r=(r+d[kt][k])%MOD;
		p=(p+1)>>1;
		k=(k-1)>>1;
	}
	return r;
}
void add(int w, bool kt, int c)
{
	w+=L-1;
	while (w)
	{
		d[kt][w]=(d[kt][w]+c)%MOD;
		w>>=1;
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;	cin>>n;
	int s=0;
	for (int i=1; i<=n; i++)
	{
		cin>>a[i];
		s=(s+a[i])%MOD;
		mapa[s]=0;
	}
	int ind=1;
	for (auto it : mapa)
	{
		mapa[it.first]=ind++;
	}
	s=0;
	for (int i=1; i<=n; i++)
	{
		s=(s+a[i])%MOD;
		if (s&1)
		{
			add(mapa[s], 1, (query(1, mapa[s], 1)+query(mapa[s]+1, L, 0))%MOD);
		}
		else
		{
			add(mapa[s], 0, (query(1, mapa[s], 0)+query(mapa[s]+1, L, 1)+1)%MOD);
		}
	}
	cout<<d[s&1][L+mapa[s]-1];
	return 0;
}