求大佬给思路找错

/**
对于每个节点，记录1x2矩阵mat作为区间左端点的增加的斐波那契数(lazytag)，第一项用于后续转移，第二项才是它加上的值 
后面的依次乘上转移矩阵（如n=8,给区间1~7操作，那么lazy[1~4]=|0,1|,lazy[5-6]=|3,5|,lazy[7]=|8,13|，对于[l,r]中的点l+i,
那么l+i增加的就是lazy[l,r]*G^i（G为转移矩阵）） 
矩阵满足可加性，分配律，所以区间加操作只需给起点加上一个斐波那契数矩阵，后面乘转移矩阵相当于同时增加两次 
预处理：
转移矩阵的1~1e5次方
转移矩阵的前缀和：
	在push_down操作的时候，假设起点加上矩阵A，转移矩阵为G，单位矩阵为I:
		则区间和增加AI+AG+A(G^2)+A(G^3)+...+A(G^(r-l))=A(I+G^1+G^2+G^3...+G*(r-l)) 
**/
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000001
using namespace std;
long long a[100100];
struct matrix2{
	ll v[2][2];
	matrix2 operator *(const matrix2 &b)const
	{
		matrix2 ret;
		ret.v[0][0]=0;
		ret.v[0][1]=0;
		ret.v[1][0]=0;
		ret.v[1][1]=0;
		for(ll i=0;i<2;i++){
			for(ll j=0;j<2;j++){
				for(ll k=0;k<2;k++){
						ret.v[i][j]+=v[i][k]*b.v[k][j];
						ret.v[i][j]%=mod;
				}
			}
		}
		return ret;
	}
	matrix2 operator +(const matrix2 &b)const
	{
		matrix2 ret;
		for(ll i=0;i<2;i++){
			for(ll j=0;j<2;j++){
				ret.v[i][j]=v[i][j]+b.v[i][j];
				ret.v[i][j]%=mod;
			}
		}
		return ret;
	}
};
matrix2 gpow[100010];
matrix2 gpowq[100010];
struct matrix{
	ll v[2]={0,0};
	matrix operator +(const matrix &b)const
	{
		matrix ret;
		ret.v[0]=v[0]+b.v[0];
		ret.v[0]%=mod;
		ret.v[1]=v[1]+b.v[1];
		ret.v[1]%=mod;
		return ret;
	}
};
ll summa(matrix a,matrix2 b){
	ll ret=0;
	ret+=a.v[0]*b.v[1][0]%mod+a.v[1]*b.v[1][1]%mod;
	ret%=mod;
	return ret;
}
matrix summa2(matrix a,matrix2 b){
		matrix ret;
	
			for(ll j=0;j<2;j++){
				for(ll k=0;k<2;k++){
						ret.v[j]=a.v[k]*b.v[j][k];
						ret.v[j]%=mod;
				}
			}

		return ret;
}
struct node{
	long long v,a,b;
	matrix m;
}b[400000];
void create(long long p,long long l,long long r){
	if(l==r){
		b[p].v=a[l];
		b[p].a=l;
		b[p].b=r;
		return;
	}
	else{
		create(((p+1)<<1)-1,l,(l+r)/2);
		create(((p+1)<<1),(l+r)/2+1,r);
		b[p].v=b[((p+1)<<1)-1].v+b[((p+1)<<1)].v;
		b[p].a=l;
		b[p].b=r;
	}
}
void push(ll p);
void mark(long long p,matrix k){
	b[p].m=b[p].m+k;
	b[p].v+=summa(k,gpowq[b[p].b-b[p].a]);
	b[p].v%=mod;
}
void print();
void change(long long p,long long l,long long r,matrix v){
	if(b[p].a>r||b[p].b<l) return;
	if(b[p].a>=l&&b[p].b<=r){
		mark(p,summa2(v,gpow[b[p].a-l]));
		return;
	}
	push(p);
	change(((p+1)<<1)-1,l,r,v);
		change(((p+1)<<1),l,r,v);
	b[p].v=b[((p+1)<<1)-1].v+b[((p+1)<<1)].v; 
	b[p].v+=summa(b[p].m,gpowq[b[p].b-b[p].a]);
	b[p].v%=mod;
	return;	
}
void push(long long p){
	if(b[p].m.v[0]==0&&b[p].m.v[1]==0) return;
	b[((p+1)<<1)-1].v+=summa(b[p].m,gpowq[b[((p+1)<<1)-1].b-b[((p+1)<<1)-1].a]);
	b[((p+1)<<1)-1].m=b[p].m+b[((p+1)<<1)-1].m;
	b[((p+1)<<1)].v+=summa(summa2(b[p].m,gpow[b[(p+1)<<1].a-b[p].a]),gpowq[b[((p+1)<<1)].b-b[((p+1)<<1)].a]);
	b[((p+1)<<1)].m=summa2(b[p].m,gpow[b[(p+1)<<1].a-b[p].a])+b[((p+1)<<1)].m;
	b[p].m.v[0]=0;b[p].m.v[1]=0;
	b[p].v=b[((p+1)<<1)-1].v+b[((p+1)<<1)].v; 
	b[p].v%=mod;
}
long long sum(long long p,long long l,long long r){
	if(b[p].a>r||b[p].b<l) return 0;
	if(b[p].a>=l&&b[p].b<=r){
		
		
		return b[p].v%mod;
	}
	push(p);
	return (sum(((p+1)<<1)-1,l,r)+
		sum(((p+1)<<1),l,r))%mod;
}
int main(){
	long long n,m;
	cin>>n>>m;
	for(long long i=0;i<n;i++){
		cin>>a[i];
	}
	create(0,0,n-1);
	gpow[0].v[0][0]=1;
	gpow[0].v[0][1]=0;
	gpow[0].v[1][0]=0;
	gpow[0].v[1][1]=1;
	gpow[1].v[0][0]=0;
	gpow[1].v[0][1]=1;
	gpow[1].v[1][0]=1;
	gpow[1].v[1][1]=1;
	for(ll i=2;i<100010;i++){
		gpow[i]=gpow[i-1]*gpow[1];
	}
	gpowq[0].v[0][0]=1;
	gpowq[0].v[0][1]=0;
	gpowq[0].v[1][0]=0;
	gpowq[0].v[1][1]=1;
	/**
	for(ll i=0;i<5;i++){
		for(ll j=0;j<2;j++){
			for(ll k=0;k<2;k++){
				cout<<gpow[i].v[j][k]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;
	}
	**/
	for(ll i=1;i<100010;i++){
		gpowq[i]=gpowq[i-1]+gpow[i];
	}
	matrix te;
	te.v[0]=0;
	te.v[1]=1;
	for(ll i=0;i<m;i++){
		ll t1,t2,t3;
		cin>>t1>>t2>>t3;
		t2--;
		t3--;
		if(t1==1){
			change(0,t2,t3,te);
		}
		else{
			cout<<sum(0,t2,t3)<<endl;
		}
	}
}