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
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <time.h>
#include <queue>

using namespace std;

const int64_t P = 1000000007;

int main () {
	int n;
	scanf("%d", &n);
	vector<int64_t> xs;
	for (int i = 0; i < n; ++i) {
		int64_t x;
		scanf("%lld", &x);
		xs.push_back(x);
	}
	if (n <= 5000) {
		vector<int64_t> ok;
		for (int i = 0; i < n; ++i) {
			int64_t cnt = 0;
			int64_t sum = 0;
			for (int j = i; j >= 0; --j) {
				sum = (sum + xs[j]) % P;
				if (sum % 2 == 0) {
					cnt = (cnt + (j > 0 ? ok[j - 1] : 1)) % P;
				}
			}
			ok.push_back(cnt);
		}
		printf("%lld\n", ok[n - 1]);
		return 0;
	}
	int64_t end0 = 1;
	int64_t end1 = 0;
	for (int i = 0; i < n; ++i) {
		if (xs[i] % 2) {
			int64_t old_end0 = end0;
			end0 = end1;
			end1 = (end1 + old_end0) % P;
		}
		else {
			end0 = (end0 * 2) % P;
		}
	}
	printf("%lld\n", end0);
	return 0;
}