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
#include <bits/stdc++.h>
using namespace std;

#define st first
#define nd second
#define int long long

int p=1000000007;

main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vector<int> v;
	v.push_back(0);
	for(int i=0; i<n; i++)
	{
		int x;
		cin>>x;
		v.push_back(x);
	}
	
	vector<pair<int,int> > prz;
	for(int i=1; i<=n; i++)
	{
		int sum=0;
		for(int j=i; j<=n; j++)
		{
			sum=(sum+v[j])%p;
			if(sum%2==0)
				prz.push_back({i-1,j});
		}
		
	}
	vector<int> wej(n+2, 0);
	vector<int> wyj(n+2, 0);
	wyj[0]=INT_MAX;
	wej[n]=INT_MAX;
	for(int i=0; i<prz.size(); i++)
	{
		wej[prz[i].st]++;
		wyj[prz[i].nd]++;
	}
	vector<pair<int,int> > prz2;
	for(int i=(int)prz.size()-1; i>=0; i--)
	{
		if(wyj[prz[i].st]==0 || wej[prz[i].nd]==0)
		{
			wej[prz[i].st]--;
			wyj[prz[i].nd]--;
		}
		else
			prz2.push_back(prz[i]);
	}
//	for(int i=0; i<prz2.size(); i++){
//		cout<<prz2[i].st<<" "<<prz2[i].nd<<" ";
//		int sum=0;
//		for(int j=prz2[i].st+1; j<=prz2[i].nd; j++)
//			sum+=v[j];
//		cout<<sum%p<<endl;
		
//		}
	vector<int> sposoby(n+1, 0);
	sposoby[0]=1;
	for(int i=(int)prz2.size()-1; i>=0; i--)
	{
		sposoby[prz2[i].nd]=(sposoby[prz2[i].nd]+sposoby[prz2[i].st])%p;
	}
	cout<<sposoby[n];
	
}