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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//============================================================================
// Name        : 3b-mop.cpp
//============================================================================

#include <iostream>
#include <vector>
using namespace std;

const int DIV = 1000000007;

int diff(int from, int to) {
	if (from > to) {
		return to + DIV - from;
	} else {
		return to - from;
	}
}

int sum(int a, int b) {
	a += b;
	if (a >= DIV) {
		return a - DIV;
	} else {
		return a;
	}
}

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

	vector<int> seq;
	vector<int> seq_sum_mod;

	int num, n;
	cin >> n;
	seq_sum_mod.push_back(0);
	for (int i = 0; i < n; i++) {
		cin >> num;
		seq.push_back(num);
		seq_sum_mod.push_back(sum(seq_sum_mod[i], num));
	}

//	cout << "seq_sum_mod: ";
//	for (int v : seq_sum_mod) {
//		cout << v << " ";
//	}
//	cout << endl;

	vector<vector<int>> ends(n, vector<int>());
	vector<int> values;

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int res = diff(seq_sum_mod[i], seq_sum_mod[j]);
			if (res % 2 == 0) {
				ends[j - 1].push_back(i);
			}
		}
	}

	int allToThis;
//	vector<int> to;
	for (int i = 0; i < n; i++) {
		allToThis = 0;
		vector<int> to = ends[i];
		if (to.size() == 0) {
			values.push_back(0);
			continue;
		} else {
			for (int start : to) {
				if (start == 0) {
					allToThis = sum(allToThis, 1);
				} else {
					allToThis = sum(allToThis, values[start - 1]);
				}
			}
			values.push_back(allToThis);
		}
	}

//	for (vector<int> &vi : ends) {
//		for (int v : vi) {
//			cout << v << " ";
//		}
//		cout << "[" << vi.size() << "]" << endl;
//	}
//	cout << endl;
//
//	for (int v : values) {
//		cout << v << " ";
//	}
//	cout << endl;
	cout << values[n - 1] << endl;

	return 0;
}