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
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;
 
const int MAX_N = 3e5+5;
const int M = 3e4+5;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

int n;
ll a[MAX_N], pref[MAX_N];

// Compression stuff

vector<ll> compress;

int get_index(ll val) {
	return lower_bound(compress.begin(), compress.end(), val) - compress.begin() + 1;
}

// Fenwick tree

int tree_size;
ll fen[MAX_N][2];	// 0 -> even values, 1 -> odd values

ll query(int pos, int which) {
    ll res = 0LL;
    while (pos > 0) {
        res += fen[pos][which];
        res %= MOD;
        int lsb = pos & (-pos);
        pos -= lsb;
    }
    return res;
}

ll get_sum(int l, int r, int which) {
    ll res = query(r, which) - query(l - 1, which);
    if (res < 0) res += MOD;
    return res;
}

void update(int pos, ll val, int which) {
	val %= MOD;
    while (pos <= tree_size) {
        fen[pos][which] += val;
        fen[pos][which] %= MOD;
        int lsb = pos & (-pos);
        pos += lsb;
    }
}

// Brute force

void brute_force() {
	vector<ll> dp(n + 1, 0LL);
	dp[0] = 1LL;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			
			if (pref[j] <= pref[i] && (pref[j]%2) == (pref[i]%2)) {
				dp[i] = (dp[i] + dp[j]) % MOD;
			}
			
			if (pref[j] > pref[i] && (pref[j]%2) != (pref[i]%2)) {
				dp[i] = (dp[i] + dp[j]) % MOD;
			}
		}
	}
	
	cout << dp[n] << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
			
	cin >> n;
	pref[0] = 0LL;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = (pref[i-1] + a[i]) % MOD;
	}
	
	if (n <= 3000) {
		brute_force();
		return 0;
	}
	
	for (int i = 0; i <= n; i++) {
		compress.push_back(pref[i]);
	}
	sort(compress.begin(), compress.end());
	auto it = unique(compress.begin(), compress.end());
	compress.resize(distance(compress.begin(), it));
	
	tree_size = (int)compress.size() + 2;
	update(get_index(0LL), 1LL, 0);		
	
	for (int i = 1; i <= n; i++) {
		int parity = 0;
		if (pref[i] % 2) parity = 1;
		
		int pos = get_index(pref[i]);
		ll same_parity = get_sum(1, pos, parity);
		ll rev_parity = get_sum(pos + 1, tree_size, parity^1);
		
		update(pos, same_parity + rev_parity, parity);
	}
	
	int last = get_index(pref[n]);
	cout << get_sum(last, last, pref[n] % 2) << '\n';
	
	
    return 0;
}