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

#define FOR(i, a, n) for(decltype(n) i = (a), i##__ = (n); i <= i##__; i++)
#define REP(i, n) FOR(i, 0, (n)-1)
#define FORD(i, a, n) for(decltype(a) i = (a), i##__ = (n); i >= i##__; i--)
#define REPD(i, n) FORD(i, (n)-1, 0)
#define V vector
#define ST first
#define ND second
#define EB emplace_back
#define RS resize
#define SZ(x) int(x.size())
#define ALL(x) x.begin(), x.end()
#define OS ostream

template<class A, class B> OS& operator<<(OS &os, pair<A, B> p) {
	return os << "(" << p.ST << ", " << p.ND << ")";
}
template<class A> OS& operator<<(OS &os, V<A> v) {
	os << "{ ";
	for(auto e : v) os << e << " ";
	return os << "}";
}
template<class A> OS& operator<<(OS &os, V<V<A>> v) {
	os << "[\n";
	for(auto e : v) os << "  " << e << "\n";
	return os << "]";
}

#ifdef DEBUG
# define D(a...) a
# define _D(a...)
#else
# define D(a...)
# define _D(a...) a
#endif
# define I(a...) #a << ": " << a << "\n"
# define J(a...) #a << ": " << a << "  "

using VI   = V<int>;
using VVI  = V<VI>;
using VVVI = V<VVI>;
using II   = pair<int, int>;
using VII  = V<II>;
using VVII = V<VII>;
using L    = long long;
using VL   = V<L>;
using VVL  = V<VL>;
using LI   = pair<L, int>;
using VB   = V<bool>;
using VVB  = V<VB>;

constexpr int mod = int(1e9+7);

struct Fenwick {
	VL tr; int n;
	Fenwick(int m): n(m) {
		tr = VL(n);
	}
	void add(int x, L co) {
		for(; x < n; x = x | (x + 1)) {
			tr[x] += co;
			tr[x] %= mod;
		}
	}
	L get(int x) {
		L ans = 0;
		for(; x >= 0; x = (x & (x + 1)) - 1)
			ans += tr[x];
		return ans;
	}
};

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

	int n; cin >> n;
	VI pref = {0};
	VII sort_pref;
	REP (i, n) {
		int x; cin >> x;
		pref.EB((pref.back() + x) % mod);
	}
	REP (i, n + 1) 
		sort_pref.EB(pref[i], i);

	D(cerr << "before " << I(pref));
	sort(ALL(sort_pref));
	REP (i, n + 1) {
		II p = sort_pref[i];
		pref[p.ND] = i * 2 + (p.ST % 2);
	}
	D(cerr << "after " << I(pref));

	Fenwick even(n + 1), odd(n + 1);	
	even.add(0, 1);
	FOR (i, 1, n - 1) {
		L ansi = 0;
		if (pref[i] % 2 == 0) {
			ansi += even.get(pref[i] >> 1);
			ansi += (odd.get(n) - odd.get((pref[i] - 1) >> 1));
			even.add(pref[i] >> 1, ansi % mod);
		}
		else {
			ansi += (even.get(n) - even.get(pref[i] >> 1));
			ansi += odd.get(pref[i] >> 1);
			odd.add(pref[i] >> 1, ansi % mod);
		}
		D(cerr << "I reckon that for " << i << " " << I(ansi));
	}

	L ans = 0;
	if (pref[n] % 2 == 0) {
		ans += even.get(pref[n] >> 1);
		ans += (odd.get(n) - odd.get((pref[n] - 1) >> 1));
	}
	else {
		ans += (even.get(n) - even.get(pref[n] >> 1));
		ans += odd.get(pref[n] >> 1);
	}
	cout << ans << "\n";
}