#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100000
#define MOD 1000000009
using namespace std;

void read(long long &x)
{
	char ch=getchar(); x=0;
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
}
long long del[N+1],f[N+1],a[N+1],q[N+1][2],sum[N+1],d[N+1],sumf[N+1],tot=0,n,m;
void rebuild()
{
	memset(del,0,sizeof del); 
	for (;tot>0;tot--)
	{
		(++del[q[tot][0]])%=MOD;
		(del[q[tot][1]+1]-=f[q[tot][1]-q[tot][0]+2]-MOD)%=MOD;
		(del[q[tot][1]+2]-=f[q[tot][1]-q[tot][0]+1]-MOD)%=MOD;
	}
	d[1]=del[1];
	for (int i=2;i<=n;i++) 
		(del[i]+=(del[i-1]+del[i-2])%MOD)%=MOD,d[i]=(d[i-1]+del[i])%MOD;
	for (int i=1;i<=n;i++) 
		(sum[i]+=d[i])%=MOD;
}
long long getans(long long l,long long r)
{
	long long s=0;
	for (int i=1;i<=tot;i++)
	{
		if (q[i][0]<l&&q[i][1]>=l&&q[i][1]<=r) 
			(s+=sumf[q[i][1]-q[i][0]+1]-sumf[l-q[i][0]])%=MOD;
		else if (q[i][0]>=l&&q[i][0]<=r&&q[i][1]>r) 
			(s+=sumf[r-q[i][0]+1])%=MOD;
		else if (q[i][0]>=l&&q[i][1]<=r&&q[i][0]<=q[i][1]) 
			(s+=sumf[q[i][1]-q[i][0]+1])%=MOD;
		else if (q[i][0]<l&&q[i][1]>r) 
			(s+=sumf[r-q[i][0]+1]-sumf[l-q[i][0]])%=MOD;
	}
	return (long long)((a[r]-a[l-1])+(sum[r]-sum[l-1])+s+(long long)MOD*100)%MOD;
}
int main()
{
	read(n),read(m);
	for (int i=1;i<=n;i++) read(a[i]),(a[i]+=a[i-1])%=MOD;
	f[1]=f[2]=1;
	for (int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])%MOD;
	for (int i=1;i<=n;i++) sumf[i]=(sumf[i-1]+f[i])%MOD;
	long long L,R,ch;
	memset(sum,0,sizeof sum);
	for (;m>0;m--)
	{
		read(ch),read(L),read(R);
		if (ch==1){
			q[++tot][0]=L;q[tot][1]=R;
			if (tot>=sqrt(n)) 
				rebuild();
		}
		else
			printf("%lld\n",getans(L,R));
	}
	return 0;
}