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
#include <bits/stdc++.h>
using namespace std;
const int MX=300300;
const long long md=1000000007;
int n,i,cur,pos,odd;
long long a[MX],b[MX],s[2][MX],tot[2],dp,prv;
//long long f[MX];
void add(int w, int i, long long x) {
  tot[w]=(tot[w]+x)%md;
  for (; i<=n+2; i=(i<<1)-(i&(i-1))) s[w][i]=(s[w][i]+x)%md;
}
long long sum(int w, int i) {
  long long res=0;
  for (; i>0; i&=i-1) res=(res+s[w][i])%md;
  return res;
}
int main() {
  scanf("%d",&n);
  for (i=1; i<=n; i++) {
    scanf("%lld",&a[i]);
    if ((a[i]+=a[i-1])>=2*md) a[i]-=2*md;
    b[i+1]=a[i];
  }
  sort(b+1,b+n+2);
  add(0,1,1);
  //f[0]=1;
  for (i=1; i<=n; i++) {
    cur=lower_bound(b+1,b+n+2,a[i])-b;
    odd=(a[i]&1);
    prv=a[i]-md;
    if (prv<0) {
      prv+=2*md;
      pos=upper_bound(b+1,b+n+2,prv)-b;
      dp=(sum(odd,cur)+tot[odd]+md-sum(odd,pos-1))%md;
      dp=(dp+sum(odd^1,pos-1)+md-sum(odd^1,cur))%md;
    } else {
      pos=upper_bound(b+1,b+n+2,prv)-b;
      dp=(sum(odd,cur)+md-sum(odd,pos-1))%md;
      dp=(dp+sum(odd^1,pos-1)+tot[odd^1]+md-sum(odd^1,cur))%md;
    }
    add(odd,cur,dp);
    /*for (int j=i-1; j>=0; j--) {
      int z=(a[i]+2*md-a[j])%(2*md);
      if ((z<md && z%2==0) || (z>=md && z%2==1)) f[i]=(f[i]+f[j])%md;
    }*/
  }
  printf("%lld\n",dp);
  return 0;
}