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
// Szymon Rusiecki (08.12.2021)
#include <bits/stdc++.h>

int mod = 1000000007;

long long power (long long a, int p) {
	if (p == 0)
		return 1;
	else if (p == 1)
		return a;
	else if (p % 2 == 1)
		return (a * power(a, p - 1)) % mod;
	else {
		long long temp = power(a, p / 2);
		return (temp * temp) % mod;
	}
}

int main () {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n;
	std::cin >> n;

	int total = 0;
	auto *tab = new int [n];
	for (int i = 0; i < n; ++i) {
		std::cin >> tab[i];
		total += tab[i];
		total %= 2;
	}

	if (n <= 10000) {
		auto *pre_tab = new int [n + 1];
		pre_tab[0] = 0;
		for (int i = 0; i < n; ++i)
			pre_tab[i + 1] = (pre_tab[i] + tab[i]) % mod;
		
		std::vector<int> *tree = new std::vector<int> [n + 2];

		for (int i = 0; i < n; ++i)
			for (int j = i; j < n; ++j)
				if (((pre_tab[j + 1] - pre_tab[i] + mod) % mod) % 2 == 0)
					tree[i + 1].push_back(j + 2);

		auto *DP_score = new int [n + 2];
		DP_score[1] = 1;
		for (int i = 2; i < n + 2; ++i)
			DP_score[i] = 0;

		for (int i = 1; i < n + 1; ++i)
			for (auto &j : tree[i])
				DP_score[j] = (DP_score[j] + DP_score[i]) % mod;

		std::cout << DP_score[n + 1];

		delete [] tab;
		delete [] pre_tab;
		delete [] tree;
		delete [] DP_score;
	}
	else if (total % 2 == 0) {
		int ile = 0;
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			sum += tab[i];
			if (sum % 2 == 0)
				++ile;
		}
		std::cout << power(2, ile - 1);
	}
	else std::cout << 0;
	return 0;
}