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
#include <stdio.h>

#define MAX_N	300000
#define H	30
#define M	1000000007

#define addm(t, v) do { \
	t += v; \
	if (t >= M) \
		t -= M; \
} while (0)

struct tree_node {
	int even;
	int odd;
	struct tree_node *left;
	struct tree_node *right;
};

struct tree_node tree_nodes[MAX_N * H];
int tree_node_cnt;

struct tree_node root;

struct tree_node *make_tree_node(void)
{
	return &tree_nodes[tree_node_cnt++];
}

void make_left(struct tree_node *n)
{
	if (!n->left)
		n->left = make_tree_node();
}

void make_right(struct tree_node *n)
{
	if (!n->right)
		n->right = make_tree_node();
}

void add_to(struct tree_node *n, int odd, int val)
{
	if (odd)
		addm(n->odd, val);
	else
		addm(n->even, val);
}

void add(int index, int val)
{
	struct tree_node *n = &root;
	int mid;
	int odd = index & 1;
	int h;

	add_to(n, odd, val);
	for (h = H; h > 0; h--) {
		mid = 1 << (h - 1);
		if (index < mid) {
			make_left(n);
			n = n->left;
		} else {
			make_right(n);
			n = n->right;
			index -= mid;
		}
		add_to(n, odd, val);
	}
}

void ask(int index, int *even, int *odd)
{
	struct tree_node *n = &root;
	int res_even = 0;
	int res_odd = 0;
	int mid;
	int h;

	for (h = H; n && h > 0; h--) {
		mid = 1 << (h - 1);
		if (index < mid) {
			n = n->left;
		} else {
			if (n->left) {
				addm(res_even, n->left->even);
				addm(res_odd, n->left->odd);
			}
			n = n->right;
			index -= mid;
		}
	}
	*even = res_even;
	*odd = res_odd;
}

int main(void)
{
	int n;
	int s = 0;
	int a;
	int even, odd;
	int res = 0;
	int i;

	scanf("%d", &n);

	add(0, 1);
	for (i = 0; i < n; i++) {
		scanf("%d", &a);
		addm(s, a);
		ask(s + 1, &even, &odd);
		res = 0;
		if (s & 1) {
			addm(res, odd);
			addm(res, root.even);
			addm(res, M - even);
		} else {
			addm(res, even);
			addm(res, root.odd);
			addm(res, M - odd);
		}
		add(s, res);
	}
	printf("%d\n", res);

	return 0;
}