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
#include <cstdio>
using namespace std;

const int N = 300000 + 5;
const int D = 31;
const int p = 1000 * 1000 * 1000 + 7;

int nextInt() { int n; scanf("%d", &n); return n; }
int myAdd(int a, int b) { a += b; if (a >= p) a -= p; return a; }
int myAdd(int a, int b, int c) { return myAdd(a, myAdd(b, c)); }
int mySub(int a, int b) { a -= b; if (a < 0) a += p; return a; }


struct Node {
	int value;
	int left;
	int right;
	int sumOdd; // nieparzyste
	int sumEven; // parzyste
};
int nextNode() { static int id = 0; return ++id; }
Node node[N * D];

class Tree {
	void privUpdate(int id, int k) {
		int left = node[id].left;
		int right = node[id].right;
		if (k % 2 == 0) {
			node[id].sumOdd = myAdd(node[left].sumOdd, node[right].sumOdd);
			node[id].sumEven = myAdd(node[left].sumEven, node[right].sumEven, node[id].value);
		} else {
			node[id].sumOdd = myAdd(node[left].sumOdd, node[right].sumOdd, node[id].value);
			node[id].sumEven = myAdd(node[left].sumEven, node[right].sumEven);
		}
	}
	void privAdd(int id, int kmin, int kmax, int key, int value) {
		int k = (kmin + kmax) / 2;
		if (key < k) {
			if (0 == node[id].left) node[id].left = nextNode();
			privAdd(node[id].left, kmin, k - 1, key, value);
		}
		if (key == k) {
			node[id].value = myAdd(node[id].value, value);
		}
		if (key > k) {
			if (0 == node[id].right) node[id].right = nextNode();
			privAdd(node[id].right, k + 1, kmax, key, value);
		}
		privUpdate(id, k);
	}

	int privSum(int id, int kmin, int kmax, int key1, int key2) {
		if (key1 - kmin <= 1 && kmax - key2 <= 1) {
			if (key1 % 2 == 0) return node[id].sumEven;
			else return node[id].sumOdd;
		}
		int k = (kmin + kmax) / 2;
		if (key2 < k) return privSum(node[id].left, kmin, k - 1, key1, key2);
		if (key2 <= k) {
			// key2 == k
			if (key1 < k) {
				int p1 = privSum(node[id].left, kmin, k - 1, key1, key2 - 2);
				int p2 = node[id].value;
				return myAdd(p1, p2);
			}
			// key1 == key2 == k
			return node[id].value;
		}
		// k < key2
		if (k < key1) return privSum(node[id].right, k + 1, kmax, key1, key2);
		if (k <= key1) {
			// key1 == k
			int p1 = privSum(node[id].right, k + 1, kmax, key1 + 2, key2);
			int p2 = node[id].value;
			return myAdd(p1, p2);
		}
		// key1 < k < key2
		int key1x = k - 1; if (key1 % 2 != key1x % 2) --key1x;
		int key2x = k + 1; if (key2 % 2 != key2x % 2) ++key2x;
		int p1 = privSum(node[id].left, kmin, k - 1, key1, key1x);
		int p2 = privSum(node[id].right, k + 1, kmax, key2x, key2);
		if (k % 2 != key1 % 2) return myAdd(p1, p2);
		return myAdd(p1, p2, node[id].value);
	}

	int root;
public:
	Tree() {
		root = nextNode();
	}
	void add(int key, int value) { privAdd(root, 0, p - 1, key, value); }
	int getSum(int key1, int key2) { return privSum(root, 0, p - 1, key1, key2); }
};

class OffsetTree {
	Tree tree;
	int keyOffset;
public:
	OffsetTree() { keyOffset = 0; }
	void add(int key, int value) {
		key = mySub(key, keyOffset);
		tree.add(key, value);
	}
	void addOffset(int offset) {
		keyOffset = myAdd(keyOffset, offset);
	}
	int getSum() {
		int p1 = tree.getSum(keyOffset % 2, p - 1 - keyOffset);
		if (keyOffset > 0) {
			int p2 = tree.getSum(p - keyOffset, p - (keyOffset % 2));
			p1 = myAdd(p1, p2);
		}
		return p1;
	}
};

OffsetTree tree;

int main() {
	int n = nextInt();

	tree.add(nextInt(), 1);
	for (int i = 1; i < n; ++i) {
		int cnt = tree.getSum();
		tree.add(0, cnt);
		int x = nextInt();
		tree.addOffset(x);
	}

	int res = tree.getSum();
	printf("%d\n", res);

	return 0;
}