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
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#ifdef LOC
#include "debuglib.h"
#else
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   Vi         = vector<int>;
using   Pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

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

struct Zp {
	ll x;
	Zp() : x(0) {}
	Zp(ll a) : x(a%MOD) { if (x < 0) x += MOD; }
	#define OP(c,d) Zp& operator c##=(Zp r) { x = x d; return *this; } Zp operator c(Zp r) const { Zp t = *this; return t c##= r; }
	OP(+, +r.x - MOD*(x+r.x >= MOD));
	OP(-, -r.x + MOD*(x-r.x < 0));
	OP(*, *r.x % MOD);
	Zp operator-() const { return Zp(0)-*this; }
	bool operator<(Zp r) const { return x < r.x; }
	bool operator==(Zp r) const { return x == r.x; }
	void print() { cerr << x; }
};

struct Fenwick {
	vector<Zp> s;
	Zp sum;
	Fenwick(int n = 0) : s(n) {}
	void modify(int i, Zp v) {
		for (; i < sz(s); i |= i+1) s[i] += v;
		sum += v;
	}
	Zp query(int i) {
		Zp v;
		for (; i > 0; i &= i-1) v += s[i-1];
		return v;
	}
	Zp querySuf(int i) {
		return sum - query(i);
	}
};

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(12);

	int n; cin >> n;
	vector<Zp> pref(n+1);

	rep(i, 0, n) {
		int val; cin >> val;
		pref[i+1] = pref[i] + val;
	}

	vector<Zp> vals = pref;
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());

	Zp ways = 1;
	Fenwick tree[2] = { {sz(vals)}, {sz(vals)} };
	tree[0].modify(0, 1);

	rep(i, 1, n+1) {
		int pos = int(lower_bound(all(vals), pref[i]) - vals.begin());
		int b = int(pref[i].x % 2);
		ways = tree[b].query(pos+1) + tree[!b].querySuf(pos+1);
		tree[b].modify(pos, ways);
	}

	cout << ways.x << '\n';
	return 0;
}