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>
#include <unordered_map>

const int MOD = 1e9 + 7;
const int N = 1073741824;

struct Tree {
	private:
	std::unordered_map<int, int> tree;
	int prefix(int x) {
		++x;
		if (x == 0) {
			return 0;
		}

		int res = 0;
		while (x > 0) {
			res += tree[x];
			res %= MOD;
			x -= ((x ^ (x - 1)) + 1) / 2;
		}
		return res;
	}

	public:
	void insert(int x, int v) {
		x++;
		while (x < N) {
			tree[x] += v;
			tree[x] %= MOD;
			x += ((x ^ (x - 1)) + 1) / 2;
		}
	}
	int sum(int a, int b) {
		if (a > b) {
			return 0;
		}
		int v = prefix(b) - prefix(a - 1);
		v += MOD;
		v %= MOD;
		return v;
	}
};

int solve(const std::vector<int> &numbers) {
	Tree odd, even;
	even.insert(0, 1);

	int sum = 0;
	int last = 0;
	for (auto n: numbers) {
		sum += n;
		sum %= MOD; 
		if (sum&1) {
			last = odd.sum(0, sum) + even.sum(sum + 1, MOD - 1);
			last %= MOD;
			odd.insert(sum, last);
		} else {
			last = even.sum(0, sum) + odd.sum(sum + 1, MOD - 1);
			last %= MOD;
			even.insert(sum, last);
		}
	}
	return last;
}

int main() {
	int n;
	std::cin >> n;
	std::vector<int> numbers(n);
	for (int i = 0; i < n; i++) {
		std::cin >> numbers[i];
	}
	std::cout << solve(numbers) << '\n';
	return 0;
}