#include<bits/stdc++.h>
using namespace std;
#define ull unsigned
#define int unsigned
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
   	return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
int const MAX=2e5+10;
ull C[MAX][22];
int a[MAX];
int n;
int qwer[4*MAX][21];
struct tree{
	ull f[4*MAX][22],tag[4*MAX];
	void pushup(int ind){
		for(int i=0;i<=19;i++){
			f[ind][i]=0;
			for(int j=0;j<=i;j++){
				f[ind][i]+=f[ind*2][i-j]*f[ind*2+1][j];
			}
		}
		return;
	}
	void maketag(int ind,int l,int r,int t1){
		if(!t1)return;
		tag[ind]+=t1;
		for(int i=19;i>=1;i--){
			//cerr<<i<<"\n";
			int res=1;
			for(int j=1;j<=i;j++){
				res*=t1;
				//cerr<<ind<<" "<<i<<" "<<i-j<<" "<<r-l+1-(i-j)<<" "<<j<<"\n";
				if((signed)r-(signed)l+1-(signed)(i-j)<0)continue;
				f[ind][i]+=res*f[ind][i-j]*C[r-l+1-(i-j)][j];
			}
		}
		//if(l==r&&r==1)cerr<<f[ind][1]<<"\n";
		return;
	}
	void pushdown(int ind,int l,int r){
		if(!tag[ind])return;
		int mid=(l+r)/2;
		maketag(ind*2,l,mid,tag[ind]);
		maketag(ind*2+1,mid+1,r,tag[ind]);
		tag[ind]=0;
		return;
	}
	void init(int ind=1,int l=1,int r=n){
		if(l==r){
			f[ind][0]=1;
			f[ind][1]=a[l]-1;
			return;
		}
		int mid=(l+r)/2;
		init(ind*2,l,mid);
		init(ind*2+1,mid+1,r);
		pushup(ind);
		return;
	}
	bool inrange(int l,int r,int ll,int rr){
		return l<=ll&&rr<=r;
	}
	bool outrange(int l,int r,int ll,int rr){
		return l>rr||ll>r;
	}
	void upd(int l,int r,int t1,int ind=1,int ll=1,int rr=n){
		//cerr<<l<<" "<<r<<" "<<t1<<" "<<ind<<" "<<ll<<" "<<rr<<"\n";
		if(inrange(l,r,ll,rr)){
			maketag(ind,ll,rr,t1);
			return;
		}
		if(outrange(l,r,ll,rr))return;
		pushdown(ind,ll,rr);
		int mid=(ll+rr)/2;
		upd(l,r,t1,ind*2,ll,mid);
		upd(l,r,t1,ind*2+1,mid+1,rr);
		pushup(ind);
		return;
	}
	void find(int l,int r,int ind=1,int ll=1,int rr=n){
		if(inrange(l,r,ll,rr)){
			//vector<int> tp(21);
			auto& tp=qwer[ind];
			for(int i=0;i<=19;i++){
				tp[i]=f[ind][i];
			}
			return;
		}else if(outrange(l,r,ll,rr)){
			auto& tp=qwer[ind];
			memset(tp,0,sizeof(tp));
			tp[0]=1;
			return ;
		}
		pushdown(ind,ll,rr);
		int mid=(ll+rr)/2;
		find(l,r,ind*2,ll,mid);
		find(l,r,ind*2+1,mid+1,rr);
		//vector<int> tp3(21,0);
		auto& tp1=qwer[ind*2];
		auto& tp2=qwer[ind*2+1];
		auto& tp3=qwer[ind];
		memset(tp3,0,sizeof(tp3));
		for(int i=0;i<=19;i++){
			for(int j=0;j<=i;j++){
				tp3[i]+=tp1[j]*tp2[i-j];
			}
		}
		return ;
	}
}T;
signed main(){
	freopen("snow.in","r",stdin);
	freopen("snow.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	C[0][0]=1;
	for(int i=1;i<MAX;i++){
		C[i][0]=1;
		for(int j=1;j<=min(i,(ull)19);j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
		}
	}
	//cin>>n;
	n=read();
	int q;
	//cin>>q;
	q=read();
	for(int i=1;i<=n;i++){
		//cin>>a[i];
		a[i]=read();
	}
	T.init();
	while(q--){
		int op;
		//cin>>op;
		op=read();
		if(op==1){
			int l,r,x;
			//cin>>l>>r>>x;
			l=read(),r=read(),x=read();
			T.upd(l,r,x);
			//cerr<<'a';
		}else{
			int l,r;
			//cin>>l>>r;
			l=read(),r=read();
			T.find(l,r);
			auto& tp=qwer[1];
			int ans=0;
			for(int i=0;i<=19;i++){
				ans+=tp[i];
				//cerr<<tp[i]<<" ";
			}
			//cout<<ans%(1<<20)<<"\n";
			write(ans&((1<<20)-1));
			putchar('\n');
		}
	}
	//for(int i=1;i<=3;i++){
	//	cerr<<T.f[1][i]<<" ";
	//}
	//T.maketag(1,1,3,2);
	//cerr<<"\n";
	//for(int i=1;i<=3;i++){
	//	cerr<<T.f[1][i]<<" ";
	//}
	//for(int i=0;i<=3;i++){
	//	cerr<<C[3][i]<<" ";
	//}
	return 0;
}