#include<cstdio>

 #include<algorithm>

 #define N 200010

 #define rg register

 #define Mod (1000000009)

 using namespace std;

 int n,m,f[N];

 long long a[N],b[N],t[N];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 inline void add(int x,int y){

     for(;x<=n+&&x>;x+=(x&-x)){t[x]+=y; t[x]%=Mod;}

 }

 inline int query(int x){

     int ret=; for(;x;x-=x&-x){ret+=t[x]; ret%=Mod;} return ret%Mod;

 }

 int main(){

     n=read();

     for(rg int i=;i<=n;i++) a[i]=read()+a[i-],b[i]=a[i]; a[]=b[]=;

     sort(b,b++n); int n2=unique(b,b++n)-b-;

     for(rg int i=;i<=n;i++) a[i]=lower_bound(b,b++n2,a[i])-b+;

 //    for(rg int i=0;i<=n;i++) printf("%lld ",a[i]); puts("");

     add(a[],f[]=);

     for(rg int i=;i<=n;i++){

         f[i]+=query(a[i]); f[i]%=Mod;

         add(a[i],f[i]);

     }

     printf("%d\n",f[n]%Mod);

     return ;

 }