#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;

#define N 200000
const int msk=(1<<20)-1;

int i,j,k,n,m,t,a[N+50];
uint c[N+50][21];

struct JB{
	uint f[21]; int sz;
	JB(){memset(f,0,sizeof(f));}
	void init(){
		memset(f,0,sizeof(f));
	}
	JB operator + (const JB a)const{
		JB ans; ans.sz=sz+a.sz;
		int i,j;
		for(i=0;i<=20;i++)if(f[i])for(j=0;j+i<=20;j++){
			ans.f[i+j]=((ans.f[i+j]+f[i]*a.f[j])&msk);
		}
		return ans;
	}
	void add(uint w){
		uint ans[21]={0},pw[21]={1};
		int i,j;
		for(i=1;i<=20;i++)pw[i]=pw[i-1]*w;
		for(i=0;i<=20;i++)for(j=0;j<=i&&j<=sz;j++){
			ans[i]=((ans[i]+f[j]*pw[i-j]*c[sz-j][i-j])&msk);
		}
		memcpy(f,ans,sizeof(f));
	}
	uint get(){
		uint res=0;
		for(int i=0;i<=20;i++)res+=f[i];
		return res&msk;
	}
	void show(){
		for(int i=0;i<=20;i++){cout<<f[i]<<' ';}cout<<endl;
	}
};

struct SB{
	#define md ((l+r)/2)
	#define ls (id*2)
	#define rs (ls+1)
	JB f[N*4+50],ans; uint t[N*4+50];
	void push(int id,int l,int r){
		if(!t[id])return;
		t[ls]=((t[ls]+t[id])&msk); t[rs]=((t[rs]+t[id])&msk);
		f[ls].add(t[id]); f[rs].add(t[id]);
		t[id]=0;
	}
	void init(int id,int l,int r){
		if(l==r){
			f[id].f[0]=1; f[id].f[1]=a[l]; f[id].sz=1; return;
		}
		init(ls,l,md); init(rs,md+1,r);
		f[id]=f[ls]+f[rs];
		
		//cout<<"NMSL "<<l<<' '<<r<<endl; f[id].show();
	}
	void add(int id,int l,int r,int x,int y,uint w){
		if(x<=l&&r<=y){
			f[id].add(w); t[id]=((w+t[id])&msk); 
			//cout<<"NMSL "<<l<<' '<<r<<endl; f[id].show();
			return;
		}
		push(id,l,r);
		if(x<=md)add(ls,l,md,x,y,w);
		if(y>md)add(rs,md+1,r,x,y,w);
		f[id]=f[ls]+f[rs];
		//cout<<"NMSL "<<l<<' '<<r<<endl; f[id].show();
	}
	void get(int id,int l,int r,int x,int y){
		if(x<=l&&r<=y){
			ans=ans+f[id]; return;
		}
		push(id,l,r);
		if(x<=md)get(ls,l,md,x,y);
		if(y>md)get(rs,md+1,r,x,y);
	}
}sb;

int main(){
	//ios::sync_with_stdio(0); cin.tie(0);
	c[0][0]=1;
	for(i=1;i<=N;i++){
		c[i][0]=1;
		for(j=1;j<=20;j++)c[i][j]=((c[i-1][j]+c[i-1][j-1])&msk);
	}
	
	cin>>n>>t;
	for(i=1;i<=n;i++){
		cin>>a[i]; a[i]--;
	}
	sb.init(1,1,n);
	while(t--){
		int op,l,r,w;
		cin>>op>>l>>r;
		if(op==1){
			cin>>w;
			sb.add(1,1,n,l,r,w);
		}
		else{
			sb.ans.init(); sb.ans.f[0]=1;
			sb.get(1,1,n,l,r);
			cout<<sb.ans.get()<<'\n';
		}
	}
}