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 <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define PR std::pair
#define MP std::make_pair
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

constexpr int MOD = 1000000007;
constexpr int M2 = 2*MOD;

inline int ADD(unsigned a, unsigned b){ // TODO: int i sprawdzic czy daje WA
	return (a + b >= M2 ? a + b - M2 : a + b);
}
inline int SUB(unsigned a, unsigned b){ // TODO: int i sprawdzic czy daje WA
	return (a >= b ? a - b : M2 + a - b);
}

struct BIT{
	VI t;
	inline int LSB(int a){ return a&(-a); }
	BIT(){}
	BIT(int sz){ t.resize(sz+1); }
	void add(int x, int val){
		x++;
		while(x < SZ(t)) t[x] = (t[x] + val) % MOD, x += LSB(x);
	}

	int query(int x){
		x++;
		int r = 0;
		while(x > 0) r = (r + t[x]) % MOD, x -= LSB(x);
		return r;
	}
};

struct Tree{
	BIT bit;
	VI vals;

	int kto(int a){
		return (int)(std::lower_bound(vals.begin(), vals.end(), a) - vals.begin());
	}

	void init(VI A){
		vals = std::move(A);
		std::sort(vals.begin(), vals.end());
		vals.resize(std::unique(vals.begin(), vals.end()) - vals.begin());
		bit = BIT(SZ(vals) + 4);
	}

	void add(int v, int val){
		int co = kto(v);
		assert(vals[co] == v);
		bit.add(co, val);
	}

	int query(int a, int b){
		int from = kto(a);
		int to = kto(b+1)-1;
		if(from > to) return 0;
		int ret = (bit.query(to) - (from == 0 ? 0 : bit.query(from - 1)))%MOD;
		if(ret < 0) ret += MOD;
		return ret;
	}
};

std::vector<PR<ll, int>> byly;
std::vector<Tree> t;
void init(VI pref){
	t.resize(2);
	FOR(i, 2) t[i].init(pref);
	t[0].add(0, 1);
}
int add(int p){
	int ans = 0;
	FOR(par, 2){
		int ind = (p % 2) ^ par;
		auto& tre = t[ind];

		int from = MOD * par;
		int to = from + MOD - 1;

		from = SUB(from, p);
		to = SUB(to, p);

		int l = (M2 - to)%M2;
		int r = (M2 - from)%M2;

		if(l < r){
			ans = (ans + tre.query(l, r))%MOD;
		}else{
			ans = (1ll * ans + tre.query(l, M2-1) + tre.query(0, r)) % MOD;
		}
	}

	t[p%2].add(p, ans);
	return ans;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int n;
	std::cin >> n;
	VI A(n);
	FOR(i, n) std::cin >> A[i];

	VI pref;
	pref.push_back(0);
	TRAV(i, A) pref.push_back(ADD(pref.back(), i));
	init(pref);

	int sum = 0;
	FOR(i, n){
		sum = ADD(sum, A[i]);
		if(i == n-1) std::cout << add(sum) << "\n";
		else add(sum);
	}

	return 0;
}