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
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define MOD 1000000007
using namespace std;
long long dwadologwa(long long n){
  long long k=1;
  while(k<n) k*=2;
  return k;
}
long long d[1500005],dp[1500005][2];
long long ile(long long a,long long b,long long p,long long k,long long n,long long m){
  //cout<<a<<" "<<b<<"  "<<p<<" "<<k<<"\n";
  if(p>b || k<a) return 0;
  if(p>=a && k<=b)
    return dp[n][m];
  return (ile(a,b,p,(p+k)/2,n*2,m)+ile(a,b,(p+k)/2+1,k,n*2+1,m))%MOD;
}
long long l,n;
long long ktory(long long x){
  long long p=0,k=n,s,y=-1;
  while(k>=p){
    s=(p+k)/2;
    if(d[s]==x){
      y=s;
      break;
    }
    if(d[s]>x) k=s-1; else p=s+1;
  }
  return y;
}
void dodaj(long long x,long long y){
  long long s=ktory(x);
  long long m=x%2;
  s+=l;
  while(s>0) dp[s][m]+=y,dp[s][m]%=MOD,s/=2;
}
long long t[300005],m,q;
int main(){
  scanf("%lld",&n);
  l=dwadologwa(n+1);
  for(int i=0;i<n;i++)
    scanf("%lld",&t[i]);
  for(int i=0;i<n;i++)
    m+=t[i],m%=MOD,d[i+1]=m;
  sort(d,d+n+1);
  m=0;
  dodaj(0,1);
  for(int i=0;i<n;i++){
    m+=t[i],m%=MOD,q=0;
    //cout<<ktory(m)<<"!!!\n";
    //cout<<dp[1]<<"\n"<<dp[2]<<" "<<dp[3]<<"\n"<<dp[4]<<" "<<dp[5]<<" "<<dp[6]<<" "<<dp[7]<<"\n";
    q+=ile(0,ktory(m),0,l-1,1,m%2);
    q+=ile(ktory(m),l-1,0,l-1,1,(m+1)%2),q%=MOD;
    //cout<<m<<" "<<q<<"\n";
    dodaj(m,q);
  }
  printf("%lld",q);
  return 0;
}