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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int tree[1200005][2], n, MOD = 1000000007;
vector<int> r, r2, t;

int find(int val){
	int e = 0, f = r.size() - 1;
	while (e <= f){
		int mid = (e + f) / 2;
		if (r[mid] == val){
			return mid;
		}
		else if (r[mid] < val){
			e = mid + 1;
		}
		else {
			f = mid - 1;
		}
	}
	return -1;
}

void add_tree(int pos, int s, int cs, int ce, int v, int nr){
	if ((s == cs) && (s == ce)){
		tree[pos][nr] += v;
		tree[pos][nr] %= MOD;
		return;
	}
	else if (s <= (cs + ce)/2){
		add_tree(pos * 2, s, cs, (cs + ce)/2, v, nr);
	}
	else {
		add_tree(pos * 2 + 1, s, (cs + ce)/2 + 1, ce, v, nr);
	}
	tree[pos][nr] = (tree[pos * 2][nr] + tree[pos * 2 + 1][nr]) % MOD;
}

int get_tree(int pos, int s, int e, int cs, int ce, int nr){
	if ((s == cs) && (e == ce)){
		return tree[pos][nr];
	}
	else if ((s <= (cs + ce)/2) && (e <= (cs + ce)/2)){
		return get_tree(pos * 2, s, e, cs, (cs + ce)/2, nr);
	}
	else if ((s > (cs + ce)/2) && (e > (cs + ce)/2)){
		return get_tree(pos * 2 + 1, s, e, (cs + ce)/2 + 1, ce, nr);
	}
	else {
		return (get_tree(pos * 2, s, (cs + ce)/2, cs, (cs + ce)/2, nr) + get_tree(pos * 2 + 1, (cs + ce)/2 + 1, e, (cs + ce)/2 + 1, ce, nr)) % MOD;
	}
}

int main(){
	cin >> n;
	r2.push_back(0);
	t.push_back(0);
	int s = 0;
	for (int i = 0; i < n; i++){
		int a;
		cin >> a;
		s += a;
		s %= MOD;
		r2.push_back(s);
		t.push_back(s);
	}
	sort(r2.begin(), r2.end());
	r.push_back(r2[0]);
	for (int i = 1; i < r2.size(); i++){
		if (r2[i] != r[r.size() - 1]){
			r.push_back(r2[i]);
		}
	}
	add_tree(1, 1, 1, n + 1, 1, 0);
	//add_tree(1, 1, 1, n + 1, 1, 1);
	for (int i = 1; i <= n; i++){
		//cout << "a " << t[i] << "\n";
		int k = find(t[i]) + 1;
		//cout << "b" << "\n";
		int res = 0;
		//cout << "c" << " " << k << "\n";
		res += get_tree(1, 1, k, 1, n + 1, t[i] % 2);
		//cout << res << "\n";
		if (k < n + 1){
			res += get_tree(1, k + 1, n + 1, 1, n + 1, (t[i] + 1) % 2);
		}
		//cout << res << "\n";
		//cout << "d" << "\n";
		res %= MOD;
		if (i == n){
			cout << res << "\n";
			return 0;
		}
		//cout << "e" << "\n";
		add_tree(1, k, 1, n + 1, res, t[i] % 2);
		//cout << "f" << "\n";
		//cout << "g" << "\n";
	}
}