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
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define PPC(x) __builtin_popcountll(x)
#define MSB(x) (63 - __builtin_clzll(x))
#define LSB(x) __builtin_ctz(x)
#define ARG(x, i) (get<i>(x))
#define ithBit(m, i) ((m) >> (i) & 1)
#define pb push_back
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std; 

template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b);	}
template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b);	}
 
const int maxN = 1 << 19, maxTS = maxN * 2, mod = 1'000'000'007;

template <typename T1, typename T2> inline void addMod(T1& a, T2 b) { a = (a + b) % mod; }

template <typename Tp> struct Tree_t
{
	int offset, qbegin, qend;
	Tp T[maxTS], res;
	
	void qpriv(int v, int left, int right)
	{	
		if (left >= qend or right <= qbegin)
			return;
		if (left >= qbegin and right <= qend)
		{
			res += T[v];
			return;
		}
		qpriv(v * 2, left, (left + right) / 2);
		qpriv(v*2+1, (left + right) / 2, right);
	}	
	
	void init(int n)
	{
		for (offset = 1; offset < n; offset *= 2) ;
	}
	
	void updt(int v, long long dx)
	{
		for (v += offset; v != 0; v /= 2)
			T[v] += dx;
	}
	
	Tp query(int a, int b)
	{
		qbegin = a + offset;
		qend = b + offset;
		res = 0;
		qpriv(1, offset, offset * 2);
		return res % mod;
	}
};
using Tree = Tree_t <long long>;

Tree tree[2][2];
int T[maxN];

void solve()
{
	int n;
	scanf ("%d", &n);
	map <int, int> leaf {{0, 1}};
	long long pref = 0;
	FOR(i, 1, n+1)
	{
		scanf ("%d", T+i);
		addMod(pref, T[i]);
		leaf[pref] = 1;
	}
	
	int s = 0;
	for (auto& it : leaf)
		it.sd = s++;
	
	FOR(a, 0, 2) FOR(b, 0, 2)
		tree[a][b].init(s);
	tree[0][0].updt(0, 1);
	pref = 0;	
	long long dp = 0;
	
	FOR(i, 1, n+1)
	{
		pref += T[i];
		long long r = pref % mod, p = pref / mod;
		int a = pref & 1, b = p & 1, v = leaf[r];
		dp = 0;
		FOR(x, 0, 2) FOR(y, 0, 2)
		{
			bool ok = (a^x) == (b^y);
			int left = ok ? 0 : v+1;
			int right = ok ? v+1 : s;
			dp += tree[x][y].query(left, right);
		}
		
		dp %= mod;
		tree[a][b].updt(v, dp);
	}
	
	printf("%lld\n", dp);
}
 
int main()
{
	int t = 1;
	//scanf ("%d", &t);
	FOR(tid, 1, t+1)
	{
		//printf("Case #%d: ", tid);
		solve();
	}
	return 0;
}