#include<cstdio>
#include<algorithm>
#define N 1919810
#define md 1000000009
#define int long long 
#define lc p<<1
#define rc p<<1|1
using namespace std;
struct Segement_tree{
	int l,r,val,t1,t2;
}s[N];
void pushup(int p){s[p].val=(s[lc].val+s[rc].val)%md;}
int sf[N],f[N],rf[N],n,m;
void csh(){
	f[1]=f[2]=1;
	sf[1]=1;sf[2]=2;
	rf[1]=1;rf[2]=md-1;
	for(int i=3;i<=n+5;i++){
		f[i]=(f[i-1]+f[i-2])%md;
		sf[i]=(sf[i-1]+f[i])%md;
		rf[i]=(i&1)?f[i]:md-f[i];
	}
}
void build(int p,int l,int r){
	s[p].l=l,s[p].r=r;
	if(l==r){
		scanf("%lld",&s[p].val);
		s[p].val%=md;
		return;
	}
	build(lc,l,(l+r)/2);build(rc,(l+r)/2+1,r);
	pushup(p);
}
void addseg(int p,int a,int b){
	(s[p].t1+=a)%md;
	(s[p].t2+=b)%md;
	s[p].val=(s[p].val+(sf[s[p].r]-sf[s[p].l-1]+md)%md*b%md)%md;
	s[p].val=(s[p].val+(sf[s[p].r+1]-sf[s[p].l]+md)%md*a%md)%md;
}
void pushdown(int p){
	if(s[p].t1==0&&s[p].t2==0)return;
	addseg(lc,s[p].t1,s[p].t2);
	addseg(rc,s[p].t1,s[p].t2);
	s[p].t1=0,s[p].t2=0;
}
void change(int p,int l,int r){
	if(s[p].l>r||s[p].r<l)return;
	if(s[p].l>=l&&s[p].r<=r){
		addseg(p,rf[l-1],rf[l]);
		return;
	}
	pushdown(p);
	change(lc,l,r);change(rc,l,r);
	pushup(p);
}
int query(int p,int l,int r){
	if(s[p].l>r||s[p].r<l)return 0;
	if(s[p].l>=l&&s[p].r<=r)return s[p].val%md;
	pushdown(p);
	return (query(lc,l,r)+query(rc,l,r))%md;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	csh();
	build(1,1,n);
	while(m--){
		int op,l,r;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1)change(1,l,r);
		else printf("%lld\n",query(1,l,r));
	}
	return 0;
}