RT

#include<bits/stdc++.h>
using namespace std;
class FastIO{
	private:
		struct control{
    		int ct,val;
    		control(int Ct,int Val=-1):ct(Ct),val(Val){}
    		inline control operator()(int Val){
        		return control(ct,Val);
    		}
		}_endl,_prs,_setprecision;
    	#define IOSIZE 1000000
    	char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
    	inline char getch(){
    	    return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;
    	}
    	inline void putch(char x){
   	    	q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;
    	}
    	inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
    	inline void getline(string& s){
    	    s="";
    	    for(register char ch;(ch=getch())!='\n'&&b;)s+=ch;
    	}
    public:
    	FastIO():_endl(0),_prs(1),_setprecision(2),p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
    	~FastIO(){fwrite(out,1,q-out,stdout);}
    	#define indef(T) inline FastIO& operator>>(T& x){\
    	    x=0;register char f=0,ch;\
   	    	while(!isdigit(ch=getch())&&b)f|=ch=='-';\
        	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
        	return x=f?-x:x,*this;\
    	}
    	indef(int)
    	indef(long long)
    	inline FastIO& operator>>(char& ch){return ch=getch(),*this;}
    	inline FastIO& operator>>(string& s){
    	    s="";register char ch;
    	    while(isspace(ch=getch())&&b);
    	    while(!isspace(ch)&&b)s+=ch,ch=getch();
    	    return *this;
    	}
    	inline FastIO& operator>>(double& x){
    	    x=0;register char f=0,ch;
    	    double d=0.1;
    	    while(!isdigit(ch=getch())&&b)f|=(ch=='-');
    	    while(isdigit(ch))x=x*10+(ch^48),ch=getch();
    	    if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
    	    return x=f?-x:x,*this;
    	}
    	#define outdef(_T) inline FastIO& operator<<(_T x){\
    	    !x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
    	    while(x)*t++=x%10+48,x/=10;\
    	    while(t!=ch)*q++=*--t;\
    	    return *this;\
    	}
    	outdef(int)
    	outdef(long long)
    	inline FastIO& operator<<(char ch){return putch(ch),*this;}
    	inline FastIO& operator<<(const char str[]){return puts(str),*this;}
    	inline FastIO& operator<<(const string& s){return puts(s.c_str()),*this;}
    	inline FastIO& operator<<(double x){
    	    register int k=0;
    	    this->operator<<(int(x));
    	    putch('.');
    	    x-=int(x);
    	    prs&&(x+=5*pow(10,-K-1));
    	    while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
    	    return *this;
    	}
    	inline FastIO& operator<<(const control& cl){
    	    switch(cl.ct){
    	        case 0:putch('\n');break;
    	        case 1:prs=cl.val;break;
    	        case 2:K=cl.val;break;
    	    }
    	}
    	inline operator bool(){return b;}
}io;
#define mod 1000000009
class Bit{
	private:
		#define N 100005
		#define lowbit(x) x&(-x)
		int c[N];
	public:
		inline void add(int x,int k=1){
			while(x<N)c[x]=(c[x]+k)%mod,x+=lowbit(x);
		}
		inline int ask(int x){
			int res=0;
			while(x)res=(res+c[x])%mod,x-=lowbit(x);
			return res;
		}
		inline int ask(int l,int r){return ask(r)-ask(l-1);}
		inline void clear(){memset(c,0,sizeof(c));}
}t;//树状数组直接蒯的板子 应该没有问题
int n,id[100005];
struct Sum{
	long long x;
	int id;//id=k表示x=Σ1~k ai
	inline bool operator<(const Sum&p)const{return x<p.x;}
}a[100005];
long long ans;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("P2344.in","r",stdin);
	freopen("P2344.out","w",stdout);
	#endif
	io>>n;
	for(register int i=1;i<=n;i++)io>>a[i].x,a[i].id=i,a[i].x+=a[i-1].x;
	sort(a+1,a+n+1);
	for(register int i=1;i<=n;i++)id[a[i].id]=i;//记下1~a[i].id的前缀和离散化之后的下标为i
	t.add(1,1);
	for(register int i=1;i<=n;i++)ans=t.ask(id[i]),t.add(id[i],ans);
	io<<ans%mod;
	return 0;
}