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
#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1000000007;

int main() {
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> v;
	v.reserve(N);
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	vector<long long> ps;
	ps.reserve(N);
	ps.push_back(v[0]);
	for (int i = 1; i < N; i++) {
		ps.push_back(v[i] + ps[i-1]);
	}

	bool small = *ps.rbegin() < MOD;

	vector<long long> res(N, 0);

	if (small) {
		int lastodd = -1;
		if (v[0] % 2 == 0) {
			res[0] = 1;
		} else {
			res[0] = 0;
			lastodd = 0;
		};
		for (int i = 1; i < N; i++) {
			if (v[i] % 2 == 0) {
				res[i] = 2*res[i-1];
			} else {
				if (lastodd > 0) {
					res[i] = 2*res[lastodd-1];
					res[i] = res[i] % MOD;
				} else if (lastodd == 0) {
					res[i] = 1;
				} else {
					res[i] = 0;
				}
				lastodd = i;
			}
		}
	} else {
		for (int i = 0; i < N; i++) {
			long long s = 0;
			for (int j = i; j >= 0; j--) {
				s += v[j];
				s = s % MOD;
				if (s % 2 == 0) {
					if (j > 0) {
						res[i] += res[j-1];
					} else {
						res[i] += 1;
					}
					res[i] = res[i] % MOD;
				}
			}
		}
	}

	cout << res[N-1] << endl;

	return 0;
}