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
#include "bits/stdc++.h"
using namespace std;
using LL = long long;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
ostream& operator<<(ostream &out, string &str) {
	for(char c: str) out << c;
	return out;
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

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

int add(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}

int sub(int a, int b) {
	return a - b < 0 ? a - b + mod : a - b;
}

void scale(vector<int> &vec) { //utrzymuje parzystość
	int n = size(vec);
	vector<pair<int, int>> temp(n);
	REP(i, n)
		temp[i] = {vec[i], i};
	sort(temp.begin(), temp.end());
	vec[temp[0].second] = 0 + (temp[0].first & 1);
	FOR(i, 1, n - 1) {
		vec[temp[i].second] = vec[temp[i - 1].second];
		if(temp[i].first != temp[i - 1].first)
			vec[temp[i].second]++;
		if(vec[temp[i].second] % 2 != temp[i].first % 2)
			vec[temp[i].second]++;
	}
}

struct Tree {
	vector<int> vec;
	int sz = 1;

	Tree(int n) {
		while((sz *= 2) < n);
		vec.resize(2 * sz);
	}

	void update(int p, int x) {
		p += sz;
		vec[p] = add(vec[p], x);
		while(p /= 2)
			vec[p] = add(vec[2 * p], vec[2 * p + 1]);
	}

	int sum(int l, int r) {
		l += sz, r += sz;
		int ret = vec[l];
		if(l != r) ret = add(ret, vec[r]);
		while(l / 2 != r / 2) {
			if(l % 2 == 0) ret = add(ret, vec[l + 1]);
			if(r % 2 == 1) ret = add(ret, vec[r - 1]);
			l /= 2, r /= 2;
		}
		return ret;
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	
	int n; cin >> n;
	vector<int> vec(n);
	REP(i, n) cin >> vec[i];
	debug(vec);

	vector<int> pref(n + 1);
	FOR(i, 1, n)
		pref[i] = add(pref[i - 1], vec[i - 1]);
	debug(pref);

	scale(pref);
	debug(pref);

	int mx = *max_element(pref.begin(), pref.end()) + 2;
	Tree odd(mx), even(mx);

	even.update(0, 1);

	int val;
	FOR(i, 1, n) {
		int x = pref[i];
		debug(x);
		if(x & 1) {
			val = add(odd.sum(0, x), even.sum(x + 1, mx - 1));
			odd.update(x, val);
		} else {
			val = add(even.sum(0, x), odd.sum(x + 1, mx - 1));
			even.update(x, val);
		}
		debug(val);
	}

	cout << val << '\n';
}