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
#include <bits/stdc++.h>

typedef long long int lli;

const lli MOD = 1000000007;

struct Node {
	Node *l, *r;
	int sum[2];
	
	Node() {
		l = NULL;
		r = NULL;
		sum[0] = 0;
		sum[1] = 0;
	}
	
	void touch_left() {
		if (l == NULL)
			l = new Node();
	}
	
	void touch_right() {
		if (r == NULL)
			r = new Node();
	}
	
	void update() {
		sum[0] = 0;
		sum[1] = 0;
		
		if (l != NULL) {
			sum[0] = l->sum[0];
			sum[1] = l->sum[1];
		}
		
		if (r != NULL) {
			sum[0] += r->sum[0];
			sum[1] += r->sum[1];
		}
		
		sum[0] %= MOD;
		sum[1] %= MOD;
	}
};

lli mod(lli x, lli m) {
	if (x < 0)
		return (x%m)+m;
	else
		return x%m;
}

lli get_sum(Node *node, int p, int k, int pp, int kk, int parity) {
	if (node == NULL)
		return 0;
	
	if (p == pp && k == kk)
		return node->sum[parity];
	
	int s = (pp + kk) / 2;
	
	if (k <= s)
		return get_sum(node->l, p, k, pp, s, parity);
	if (p >= s)
		return get_sum(node->r, p, k, s, kk, parity);
	
	return (get_sum(node->l, p, s, pp, s, parity) + get_sum(node->r, s, k, s, kk, parity)) % MOD;
}

void add(Node *node, int x, lli val, int pp, int kk) {
	if (kk - pp == 1) {
		node->sum[x%2] += val%MOD;
		node->sum[x%2] %= MOD;
		return;
	}
	
	int s = (pp + kk) / 2;
	
	if (x < s) {
		node->touch_left();
		add(node->l, x, val, pp, s);
		node->update();
	}
	else {
		node->touch_right();
		add(node->r, x, val, s, kk);
		node->update();
	}
}

int main() {
	Node *root = new Node();
	lli base = 1LL<<30;
	
	int n;
	scanf("%d", &n);
	
	lli sum = 0;
	lli sc;
	
	add(root, 0, 1, 0, base);
	
	for (int i=0; i<n; i++) {
		lli x;
		scanf("%lld", &x);
		
		sum = (sum + x) % MOD;
		
		sc = get_sum(root, 0, sum+1, 0, base, sum%2) + get_sum(root, sum+1, base, 0, base, 1-sum%2);
		sc %= MOD;
// 		printf("aaa %lld\n", sc);
		add(root, sum, sc, 0, base);
	}
	
	printf("%lld\n", sc);
	
	return 0;
}