/*
题意：给定一个长度为n的序列a。
两种操作：
1.给定区间l r 加上某个数x.
2.查询区间l r sigma(fib(ai)) fib代表斐波那契数列。
思路：
1.矩阵操作，由矩阵快速幂求一个fib数根据矩阵的乘法结合率，A*C+B*C=(A+B)*C; 这样可以通过线段树维护某个区间2*1矩阵的和。
2.时限卡的紧...用我的矩阵乘法板子TLE了。所以把板子里边的三重循环改成手工公式...
3.注意(a+b)%mod。这种，改成if(a+b>=mod)a+b-mod这种形式时间几乎减半了==...（因为查询和更新操作每次都要把两个矩阵加起来...所以这种优化在这题来说作用明显）
4.注意lazy标记不要记录要乘多矩阵多少次方...而是直接记录该矩阵...这是最重要的一个优化（个人认为）.因为每次向下层更新都要求一次矩阵...
*/
#include<bits/stdc++.h>
#define N 100020
#define MAXS 2
using namespace std;
long long jilu[N];
long long jil[N];
long long MOD =1e9+;
struct Matrix
{
long long mx[MAXS][MAXS];
Matrix()
{
memset(mx,,sizeof(mx));
}
Matrix operator* (const Matrix& b) const
{
Matrix tmp;
tmp.mx[][]=mx[][]*b.mx[][]+mx[][]*b.mx[][];
if(tmp.mx[][]>=MOD)tmp.mx[][]%=MOD;
tmp.mx[][]=mx[][]*b.mx[][]+mx[][]*b.mx[][];
if(tmp.mx[][]>=MOD)tmp.mx[][]%=MOD;
tmp.mx[][]=mx[][]*b.mx[][]+mx[][]*b.mx[][];
if(tmp.mx[][]>=MOD)tmp.mx[][]%=MOD;
tmp.mx[][]=mx[][]*b.mx[][]+mx[][]*b.mx[][];
if(tmp.mx[][]>=MOD)tmp.mx[][]%=MOD;
return tmp;
} Matrix operator +(const Matrix &b)const{
Matrix tmp;
for(int i=;i<;i++){
for(int j=;j<;j++){
tmp.mx[i][j]=(mx[i][j]+b.mx[i][j]);
if(tmp.mx[i][j]>=MOD)tmp.mx[i][j]-=MOD;
}
}
return tmp;
}
void initE()
{
memset(mx,, sizeof(mx));
for (int i= ; i< ; i++)
{
mx[i][i]=;
}
} Matrix mpow(long long k)
{
Matrix c,b;
c=(*this); b.initE();
while(k)
{
if(k&)
{
b=b*c;
}
c=c*c;
k>>=;
}
return b;
}
};
Matrix biao,ben;
struct tr{
Matrix val,tt;
long long aa;
int s,e;
};
tr tree[<<];
void build(int s,int e,int k){
tr &tmp=tree[k];
tmp.s=s;tmp.e=e;tmp.aa=;
tmp.tt.initE();
if(s==e){
tmp.val.mx[][]=jilu[s];
tmp.val.mx[][]=jil[s];
return;
}
int mid=(s+e)>>;
build(s,mid,k<<);
build(mid+,e,k<<|);
tmp.val=tree[k<<].val+tree[k<<|].val;
}
void add(int s,int e,int k,int num){
tr &tmp=tree[k];
if(s==tmp.s&&e==tmp.e){
Matrix ttt=biao.mpow(num);
tmp.tt=ttt*tmp.tt;
tmp.val=ttt*tmp.val;
tmp.aa+=num;
return;
}
if(tmp.aa){
tree[k<<].aa+=tmp.aa;
tree[k<<].val=tmp.tt*tree[k<<].val;
tree[k<<].tt=tmp.tt*tree[k<<].tt;
tree[k<<|].aa+=tmp.aa;
tree[k<<|].val=tmp.tt*tree[k<<|].val;
tree[k<<|].tt=tmp.tt*tree[k<<|].tt;
tmp.tt.initE();
tmp.aa=;
}
int mid=(tmp.s+tmp.e)>>;
if(e<=mid)add(s,e,k<<,num);
else if(s>mid)add(s,e,k<<|,num);
else{
add(s,mid,k<<,num);
add(mid+,e,k<<|,num);
}
tmp.val=tree[k<<].val+tree[k<<|].val;
}
long long query(int s,int e,int k){
tr &tmp=tree[k];
if(tmp.s==s&&tmp.e==e){
return tmp.val.mx[][];
}
if(tmp.aa){
tree[k<<].aa+=tmp.aa;
tree[k<<].val=tmp.tt*tree[k<<].val;
tree[k<<].tt=tmp.tt*tree[k<<].tt;
tree[k<<|].aa+=tmp.aa;
tree[k<<|].val=tmp.tt*tree[k<<|].val;
tree[k<<|].tt=tmp.tt*tree[k<<|].tt;
tmp.tt.initE();
tmp.aa=;
}
int mid=(tmp.s+tmp.e)>>;
if(e<=mid)return query(s,e,k<<);
else if(s>mid)return query(s,e,k<<|);
else return (query(s,mid,k<<)+query(mid+,e,k<<|))%MOD;
}
int main()
{
int n,m;
biao.mx[][]=biao.mx[][]=biao.mx[][]=;
ben.mx[][]=ben.mx[][]=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%lld",jilu+i);
if(jilu[i]==){
jil[i]=;
}
else if(jilu[i]==){
jilu[i]=;
jil[i]=;
}
else{
Matrix rel=biao.mpow(jilu[i]-)*ben;
jilu[i]=rel.mx[][];
jil[i]=rel.mx[][];
}
}
build(,n,);
for(int i=;i<=m;i++){
int typ,l,r,x;
scanf("%d",&typ);
if(typ==){
scanf("%d%d%d",&l,&r,&x);
add(l,r,,x);
}
else{
scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r,));
}
}
}