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
#include <stdio.h>
#include <vector>

#define MOD_VAL 1000000007
#define MAX_SIZE 5001


int modValues [MAX_SIZE][MAX_SIZE];
int cache [MAX_SIZE][MAX_SIZE];


long long int calculateResult(int b, int e){
	if (cache[b][e] != -1) return cache[b][e];
	long long int result = (modValues[b][e] == 0);
	for(int i = b; i < e ; ++i){
		if (modValues[b][i] == 0){
			result = (result + calculateResult(i + 1, e)) % MOD_VAL;
		}
	}
	cache[b][e] = result;
	return result;
}


long long int cachePot[300001];

long long int poteguj(int n){
	if (n == 0) return 1;
	if (n == 1) return 2;
	if (cachePot[n] != 0) return cachePot[n];
	long long int result = (poteguj(n/2) * poteguj(n/2 + (n % 2))) % MOD_VAL;
	cachePot[n] = result;
	return result;
}


int main(){
	int n;
	scanf("%d", &n);
	if (n < MAX_SIZE){
		std::vector<int> values(n);
		for(int i = 0; i < n; ++i){
			scanf("%d", &values[i]);
		}
		for(int i = 0; i < n ; ++i){
			long long int rowValue = 0;
			for(int j = i; j < n; ++j){
				rowValue += values[j];
				modValues[i][j] = (rowValue % MOD_VAL) % 2;
				cache[i][j] = -1;
			}
		}

		long long int result = calculateResult(0, n-1);
		printf("%lld\n", result);

	} else {
		long long int suma = 0;
		int punktPodzialu = 0;
		int a;
		for(int i = 0; i < n ; ++i){
			scanf("%d", &a);
			suma += a;
			if (suma % 2 == 0){
				++punktPodzialu;
			}
		}
		long long int result = 0;
		if (suma % 2 == 0){
			result = poteguj(punktPodzialu - 1);
		}
		printf("%lld\n", result);
	}
	return 0;
}