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
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // University of Warsaw
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)
#define ssize(x) int(x.size())
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) {
	return o << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
	o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

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

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

using A2 = array<int, 2>;
A2 merge(A2 l, A2 r) {
	return {
		add(l[0], r[0]),
		add(l[1], r[1])
	};
}

struct Tree {
	int sz = 1;
	vector<A2> vals;
	Tree(int n) {
		while(sz < n)
			sz *= 2;
		vals.resize(2 * sz, {{0, 0}});
	}

	void add(int i, bool parity, int  x) {
		add_to(vals[i + sz][parity], x);
		i += sz;
		while(i /= 2)
			vals[i] = merge(vals[2 * i], vals[2 * i + 1]);
	}

	A2 get(int l, int r) {
		if(l > r)
			return {0, 0};
		l += sz;
		r += sz;
		if(l == r)
			return vals[l];
		A2 ret = merge(vals[l], vals[r]);
		while(l / 2 != r / 2) {
			if(l % 2 == 0)
				ret = merge(ret, vals[l + 1]);
			if(r % 2 == 1)
				ret = merge(ret, vals[r - 1]);
			l /= 2;
			r /= 2;
		}
		return ret;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;
	vector<int> a(n);
	for(int &ai : a)
		cin >> ai;

	vector<uint32_t> possible_sums = {0};
	uint32_t curr_sum = 0;
	for(int ai : a)
		possible_sums.emplace_back((curr_sum += ai) %= 2 * mod);
	sort(possible_sums.begin(), possible_sums.end());
	possible_sums.erase(unique(possible_sums.begin(), possible_sums.end()), possible_sums.end());
	debug(possible_sums);

	Tree tree(ssize(possible_sums));
	auto get_sum = [&](uint32_t l, uint32_t r) -> A2 {
		auto it = upper_bound(possible_sums.begin(), possible_sums.end(), r);
		if(it == possible_sums.begin())
			return {0, 0};
		int ir = int(it - possible_sums.begin()) - 1;
		int il = int(lower_bound(possible_sums.begin(), possible_sums.end(), l) - possible_sums.begin());
		debug(l, r, il, ir);
		return tree.get(il, ir);
	};
	auto add_to_dp = [&](uint32_t x, int val) {
		auto it = lower_bound(possible_sums.begin(), possible_sums.end(), x);
		assert(it != possible_sums.end() and *it == x);
		int i = int(it - possible_sums.begin());
		return tree.add(i, x % 2, val);
	};
	add_to_dp(0, 1);

	curr_sum = 0;
	int to_save;
	for(int ai : a) {
		to_save = 0;
		(curr_sum += ai) %= 2 * mod;
		if(curr_sum >= mod) {
			add_to(to_save, get_sum(0, curr_sum - mod)[curr_sum % 2 == 0]);
			add_to(to_save, get_sum(curr_sum - mod + 1, curr_sum)[curr_sum % 2]);
			add_to(to_save, get_sum(curr_sum + 1, 2 * mod - 1)[curr_sum % 2 == 0]);
		}
		else {
			add_to(to_save, get_sum(0, curr_sum)[curr_sum % 2]);
			add_to(to_save, get_sum(curr_sum + 1, curr_sum + mod)[curr_sum % 2 == 0]);
			add_to(to_save, get_sum(curr_sum + mod + 1, 2 * mod - 1)[curr_sum % 2]);
		}
		debug(ai, curr_sum, to_save);
		add_to_dp(curr_sum, to_save);
	}
	cout << to_save << '\n';
}