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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <algorithm>
#include <iostream>
#include <vector>

constexpr int MOD = 1e9 + 7;

struct mod_int {
	int v;

	mod_int(int v) : v(v) {}

	mod_int operator+(const mod_int& right) const {
		return (this->v + right.v) % MOD;
	}

	void operator+=(const mod_int& right) {
		*this = *this + right;
	}
	
	bool operator==(const mod_int& right) const {
		return this->v == right.v;
	}

	mod_int operator-(const mod_int& right) const {
		return (this->v - right.v + MOD) % MOD;
	}
	
	mod_int operator-() const {
		return (-this->v + MOD) % MOD;
	}

	bool is_even() const {
		return v % 2 == 0;
	}

	bool operator<(const mod_int& right) const {
		return this->v < right.v;
	}

	bool operator>(const mod_int& right) const {
		return this->v > right.v;
	}
	
	bool operator<=(const mod_int& right) const {
		return this->v <= right.v;
	}

	bool operator>=(const mod_int& right) const {
		return this->v >= right.v;
	}
};

struct tree_node {
	tree_node(mod_int v, tree_node* parent) : value(v), parent(parent) {}

	mod_int value;
	mod_int paths = 0;
	mod_int subtree_path_sum = 0;
	tree_node* parent;
	tree_node* left = nullptr;
	tree_node* right = nullptr;
};

tree_node* create_bst(tree_node* parent, const std::vector<mod_int>& source, int first, int last) {
	if (first > last) return nullptr;
	int mid = (first + last) / 2;
	tree_node* result = new tree_node(source[mid], parent);
	result->left = create_bst(result, source, first, mid - 1);
	result->right = create_bst(result, source, mid + 1, last);
	return result;
}

void propagate_value(tree_node* node, mod_int update) {
	if (!node) return;
	node->subtree_path_sum += update;
	propagate_value(node->parent, update);
}

void find_update_node(tree_node* node, mod_int value, mod_int update) {
	if (node->value == value) {
		node->paths += update;
		propagate_value(node, update);
	}
	else if (value < node->value) {
		find_update_node(node->left, value, update);
	}
	else {
		find_update_node(node->right, value, update);
	}
}

mod_int sum_larger_equal(tree_node* node, mod_int value) {
	if (!node) return 0;
	if (node->value >= value) {
		return node->paths + (node->right ? node->right->subtree_path_sum : 0) + sum_larger_equal(node->left, value);
	}
	// if (node->value < value)
	return sum_larger_equal(node->right, value);
}

mod_int sum_less_than(tree_node* node, mod_int value) {
	if (!node) return 0;
	if (node->value < value) {
		return node->paths + (node->left ? node->left->subtree_path_sum : 0) + sum_less_than(node->right, value);
	}
	// if (node->value >= value)
	return sum_less_than(node->left, value);
}

int main() {
	int n;
	std::cin >> n;

	std::vector<mod_int> odds, evens, values;
	evens.push_back(0);
	mod_int sum = 0;
	for (int i = 0; i < n; ++i) {
		int v;
		std::cin >> v;
		values.emplace_back(v);
		sum += v;
		if ((-sum).is_even()) {
			evens.emplace_back(-sum);
		}
		else {
			odds.emplace_back(-sum);
		}
	}

	std::sort(evens.begin(), evens.end());
	std::sort(odds.begin(), odds.end());

	tree_node* odd_bst = create_bst(nullptr, odds, 0, odds.size() - 1);
	tree_node* even_bst = create_bst(nullptr, evens, 0, evens.size() - 1);
	find_update_node(even_bst, 0, 1);

	sum = 0;
	for (int i = 0; i < n; ++i) {
		sum += values[i];
		mod_int total = 0;
		if (sum.is_even()) {
			total += sum_larger_equal(odd_bst, -sum);
			total += sum_less_than(even_bst, -sum);
		}
		else {
			total += sum_larger_equal(even_bst, -sum);
			total += sum_less_than(odd_bst, -sum);
		}

		if (i == n - 1) {
			std::cout << total.v << std::endl;
		} else {
			if ((-sum).is_even()) {
				find_update_node(even_bst, -sum, total);
			}
			else {
				find_update_node(odd_bst, -sum, total);
			}
		}
	}

	return 0;
}