#include<iostream>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>

#define pb push_back
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(),(x).end()
#define _for(i, a) for(int i = 0; i < (a); ++i) 
#define _rep(i, a, b) for(int i = (a);i <= (b); ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define u1 (u<<1)
#define u2 (u<<1|1)
//#define endl '\n'
using namespace std;
typedef pair<int,int> PII;

const int N =4e5+10;
const long long mod=(1<<20);
#define int long long 
int n,lzy[N],tot,a[N],pos[N],q,U[640][640],T[640][640],Ex[640][640],l[N],r[N];
inline int read(){
	char c; c=getchar(); int sum=0;
	while(c<'0'||c>'9')	c=getchar();
	while(c>='0'&&c<='9')	sum=sum*10+(c-'0'),c=getchar();
	return sum;
}
void CG(int x){
	for(int i=1;i<=20;i++)	T[x][i]=0; 
	T[x][0]=1;
	for(int i=l[x];i<=r[x];i++)	
		for(int j=20;j>=0;j--){
			if(j!=0)	T[x][j]=((T[x][j]%mod*a[i]%mod)%mod+T[x][j-1])%mod;
			else	T[x][j]=(T[x][j]%mod*a[i]%mod)%mod;
		}
}
void Devide(){
	int len=sqrt(n),tot=n/len; if(len*len!=n)	tot++;
	for(int i=1;i<=tot;i++)	l[i]=(i-1)*len+1,r[i]=l[i]+len-1;
	r[tot]=n;
	for(int i=1;i<=tot;i++)	for(int j=l[i];j<=r[i];j++)	pos[j]=i;
	for(int i=1;i<=tot;i++)	CG(i);
}
void update(int L,int R,int x){
	if(pos[L]==pos[R]){
		for(int i=L;i<=R;i++)	a[i]+=x,a[i]%=mod;
		CG(pos[L]);
		return ;
	}
	for(int i=L;i<=r[pos[L]];i++)	a[i]+=x,a[i]%=mod; CG(pos[L]);
	for(int i=l[pos[R]];i<=R;i++)	a[i]+=x,a[i]%=mod; CG(pos[R]);
	for(int i=pos[L]+1;i<=pos[R]-1;i++)	lzy[i]+=x,lzy[i]%=mod;
}
int Query(int L,int R){
	int ans=1;
	if(pos[L]==pos[R]){
		for(int i=L;i<=R;i++)	ans*=(a[i]+lzy[pos[L]])%mod,ans%=mod;
		return ans;
	}
	for(int i=L;i<=r[pos[L]];i++)	ans*=(a[i]+lzy[pos[L]])%mod,ans%=mod;
	for(int i=l[pos[R]];i<=R;i++)	ans*=(a[i]+lzy[pos[R]])%mod,ans%=mod;
	for(int i=pos[L]+1;i<=pos[R]-1;i++){
		int Sum=0,prs=20;
		int lst=min(prs,r[i]-l[i]+1);
		for(int j=1,p=0;p<=lst;p++,j=(j%mod*lzy[i]%mod)%mod)	Sum+=T[i][p]*j,Sum%=mod; // i block p jieduan 
		ans=ans*Sum; ans%=mod;	
	}
	return ans;
}
void solve(){
	n=read(),q=read();
	for(int i=1;i<=n;i++)	a[i]=read();
	Devide();
	while(q--){
		int op,l,r,x;
		op=read(),l=read(),r=read();
		if(op==1)	x=read(),update(l,r,x);
		else printf("%lld\n",Query(l,r));
	}
}
signed main(){

	int T=1;
//	cin>>T;
	_rep(i,1,T){
		solve();
	}
	return 0;
}