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
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <vector>
#include <unordered_map>
#include <set>
#include <string>
#include <cstring>
#include <cassert>
#include <limits.h>

using namespace std;

typedef long long LL;
typedef long double LD;

typedef vector<int> VI;
typedef pair<int,int> PII;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(VAR(i,a);i<=(b);++i)
#define FORD(i,a,b) for(VAR(i,a);i>=(b);--i)
#define FORE(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define VAR(a,b) __typeof(b) a=(b)
#define SIZE(a) ((int)((a).size()))
#define ALL(x) (x).begin(),(x).end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define ZERO(x) memset(x,0,sizeof(x))
#define S(t,i) scanf("%" ## t, &i)
#define SI(i) scanf("%d", &i)

const int INF=INT_MAX;
const int MAXN=300000+5;
const int P = 1000000000+7;
int n;
long long int s[MAXN];

const long long int M = 2*1073741824ll;


inline bool isEven(int l, int r) {
    return (((s[r] - s[l-1]) % P) & 1) == 0;
}

unordered_map<long long int, int> parzyste;
unordered_map<long long int, int> nieparzyste;

void insert(unordered_map<long long int, int> &w, int x, int val) {
    long long int v = M+x;
    w[v] = (w[v] + val) % P;
    while (v!=1) {
        v = v/2;
        w[v] = (w[2*v] + w[2*v+1]) % P;
    }
}

int query(unordered_map<long long int, int> &w, int a, int b) {
    long long int va=M+a;
    long long int vb=M+b;
    int wyn=0;
    if (a>b) return 0;
    if (w.find(va) != w.end()) {
        wyn = w[va];
    }
    if (va!=vb && w.find(vb) != w.end()) wyn = (wyn + w[vb]) % P;
    while (va/2 != vb/2) {
        if (va%2 == 0 && w.find(va+1) != w.end()) wyn = (wyn + w[va+1]) % P;
        if (vb%2 == 1 && w.find(vb-1) != w.end()) wyn = (wyn + w[vb-1]) % P;
        va = va/2 ;
        vb = vb/2 ;
    }
    return wyn;
}


int main() {
    ios_base::sync_with_stdio(0);
    
    SI(n);
    
    
    int r=0;
    FOR(i, 1, n) {
        scanf("%lld", &s[i]);
        s[i] = (s[i] + s[i-1]);
        int pos = s[i]%(P);
        if (((s[i] % P) & 1) == 0) {
            r = 1;
            r += query(parzyste, max(0,pos-P), pos);
            if (pos<P) {
                r = (r + query(parzyste, pos+P, 2*P)) % P;
            }
            r = (r + query(nieparzyste, pos, min(pos+P, 2*P)) ) % P;
            if (pos>P) {
                r = (r + query(nieparzyste, 0, pos-P) ) % P;
            }
            insert(parzyste, pos, r);
        } else if (((s[i] % P) & 1) == 1) {
            r = 0;
            r += query(nieparzyste, max(0,pos-P), pos);
            if (pos<P) {
                r = (r + query(nieparzyste, pos+P, 2*P)) % P;
            }
            r = (r + query(parzyste, pos, min(pos+P, 2*P)) ) % P;
            if (pos>P) {
                r = (r + query(parzyste, 0, pos-P)) % P;
            }
            if (r>0) {
                insert(nieparzyste, pos, r);
            }
        }
        
    }
    
    printf("%d\n", r);
    
    return 0;
}