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

const int c=1000000007;
int n, s=0;
int M=1<<19;
int w[1<<20]={};

void insert (int x, int val)
{
	int v=M+x;
	w[v]=val;
	
	while (v!=1)
	{
		v/=2;
		w[v]=(w[2*v]+w[2*v+1])%c;
	}
}

int query (int a, int b)
{
	int va=M+a;
	int vb=M+b;
	int suma=w[va];
	
	if (va!=vb)
		suma=(suma+w[vb])%c;
	
	while (va/2!=vb/2)
	{
		if (va%2==0)
			suma=(suma+w[va+1])%c;
		if (vb%2==1)
			suma=(suma+w[vb-1])%c;
		
		va/=2;
		vb/=2;
	}
	
	return suma%c;
}

void mopadulo (int a, int dl)
{
	int b=a+dl-1;
	int suma=query(a, b);
	
	if (suma%2==0)
	{
		if (b==n-1)
		{
			s=(s+1)%c;
			return;
		}
		
		for (int i=1; i<=n-b-1; i++)
			mopadulo(b+1, i);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	int a;
	
	cin >> n;
	
	for (int i=0; i<n; i++)
	{
		cin >> a;
		insert(i, a);
	}
	
	for (int i=1; i<=n; i++)
		mopadulo(0, i);
	
	cout << s;
	
	return 0;
}