写太丑了被卡常了，先码。
//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define mid ((l+r)>>1)
#define lc x<<1
#define rc x<<1|1
const int maxn=1e6+10;
typedef long long LL;
const LL mod=1e9+1;
LL cs[maxn],n,m,l,r,opt,sgt[maxn<<2],lz[maxn<<2][2];
using namespace std;
inline LL read(){
LL ret=0,f=1; char ch=getchar();
while((ch!='-')&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
return ret;
}
struct jz{
LL a[3][3];
friend jz operator *(const jz&A,const jz&B){
jz ret; memset(ret.a,0,sizeof(ret.a ));
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++)
for(int k=0;k<=2;k++)
ret.a[i][j]=(ret.a[i][j]+A.a[i][k]*B.a[k][j]%mod)%mod;
return ret;
}
}fi[maxn];
struct T{
LL b[3];
friend T operator *(const T&A,const jz&B){
T ret; memset(ret.b,0,sizeof(ret.b));
for(int i=0;i<=2;i++)
for(int k=0;k<=2;k++)
ret.b[i]=(ret.b[i]+A.b[k]*B.a[k][i]%mod)%mod;
return ret;
}
}tmp;
void down(int x,int l_len,int r_len){
(lz[lc][0]+=lz[x][0])%=mod;
(lz[lc][1]+=lz[x][1])%=mod;
tmp.b[0]=lz[x][0];
tmp.b[1]=tmp.b[2]=lz[x][1];
tmp=tmp*fi[l_len];
(sgt[lc]+=tmp.b[2])%=mod;
LL tt=tmp.b[2];
tmp=tmp*fi[1];
(lz[rc][0]+=tmp.b[0])%=mod;
(lz[rc][1]+=tmp.b[1])%=mod;
tmp=tmp*fi[r_len];
sgt[rc]+=((tmp.b[2]-tt)%mod+mod)%mod;
lz[x][0]=lz[x][1]=0;
}
void build(int x,int l,int r){
if(l==r) {sgt[x]=cs[l];return;}
build(lc,l,mid); build(rc,mid+1,r);
sgt[x]=sgt[lc]+sgt[rc];
}
void add(int x,int l,int r,int ql,int qr,LL af,LL as){
if(l>=ql&&r<=qr){
(lz[x][0]+=af)%=mod;
(lz[x][1]+=as)%=mod;
tmp.b[0]=af;
tmp.b[1]=tmp.b[2]=as;
tmp=tmp*fi[r-l];
(sgt[x]+=tmp.b[2])%=mod;
return;
}
if(lz[x][0]||lz[x][1]) down(x,mid-l,r-mid-1);
if(ql<=mid) add(lc,l,mid,ql,qr,af,as);
if(qr>mid){
if(ql>mid) add(rc,mid+1,r,ql,qr,af,as);
else{
tmp.b[0]=af;
tmp.b[1]=tmp.b[2]=as;
tmp=tmp*fi[mid-max(l,ql)+1];
add(rc,mid+1,r,ql,qr,tmp.b[0],tmp.b[1]);
}
}
sgt[x]=(sgt[lc]+sgt[rc])%mod;
}
LL query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sgt[x];
if(lz[x][0]||lz[x][1]) down(x,mid-l,r-mid-1);
if(qr<=mid) return query(lc,l,mid,ql,qr);
if(ql>mid) return query(rc,mid+1,r,ql,qr);
return (query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr))%mod;
}
int main()
{
//freopen("fibnacci.in","r",stdin);
//freopen("fibnacci.out","w",stdout);
n=read(); m=read();
for(int i=1;i<=n;i++) cs[i]=read();
build(1,1,n);
fi[0].a[0][0]=fi[0].a[1][1]=fi[0].a[2][2]=1;
fi[1].a[0][1]=fi[1].a[0][2]=fi[1].a[1][0]=fi[1].a[1][1]=fi[1].a[1][2]=fi[1].a[2][2]=1;
for(int i=2;i<=n;i++) fi[i]=fi[i-1]*fi[1];
while(m--){
opt=read(); l=read(); r=read();
if(opt==1) add(1,1,n,l,r,0,1);
else printf("%lld
",query(1,1,n,l,r));
}
return 0;
}