#include<bits/stdc++.h>
using namespace std;
#define ls (x<<1)
#define rs (ls|1)
using ll=long long;
const ll mod=(1<<20)-1;
ll a[200200];
ll segt[200200<<2][20];
ll tag[200200<<2];
ll C[22][22];
void pushdown(int x,int l,int r)
{
	if(!tag[x]) return ;
	static ll pw[20];
	pw[0]=1;
	for(int i=1;i<20;i++)
		pw[i]=pw[i-1]*tag[x]%mod;
	for(int i=0;i<20;i++)
		for(int j=i+1;j<20;j++)
			segt[x][i]=(segt[x][i]+segt[x][j]*C[j][i]*pw[j-i])&mod;
	if(l!=r)
	{
		tag[ls]=(tag[ls]+tag[x])&mod;
		tag[rs]=(tag[rs]+tag[x])&mod;
	}
	tag[x]=0;
}
void pushup(int x,int l,int r)
{
	int mid=(l+r)/2;
	pushdown(ls,l,mid);
	pushdown(rs,mid+1,r);
	for(int i=0;i<20;i++)
		segt[x][i]=0;
	for(int i=0;i<20;i++)
		for(int j=0;j<20-i;j++)
			segt[x][i+j]=(segt[x][i+j]+segt[ls][i]*segt[rs][j])&mod;
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		segt[x][1]=1;
		segt[x][0]=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(x,l,r);
}
void update(int x,int l,int r,int ql,int qr,ll v)
{
	pushdown(x,l,r);
	if(ql<=l&&r<=qr)
	{
		tag[x]=(tag[x]+v)&mod;
		return ;
	}
	int mid=(l+r)/2;
	if(ql<=mid)
		update(ls,l,mid,ql,qr,v);
	if(qr>mid)
		update(rs,mid+1,r,ql,qr,v);
	pushup(x,l,r);
}
ll query(int x,int l,int r,int ql,int qr)
{
	pushdown(x,l,r);
	if(l==ql&&r==qr)
		return segt[x][0];
	int mid=(l+r)/2;
	if(qr<=mid)
		return query(ls,l,mid,ql,qr);
	if(ql>mid)
		return query(rs,mid+1,r,ql,qr);
	return query(ls,l,mid,ql,mid)*query(rs,mid+1,r,mid+1,qr)&mod;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(int i=0;i<22;i++)
		C[i][i]=C[i][0]=1;
	for(int i=2;i<22;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])&mod;
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	while(q--)
	{
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1)
		{
			ll x;
			cin>>x;
			update(1,1,n,l,r,x);
		}
		else
			cout<<query(1,1,n,l,r)<<'\n';
	}
	return 0;
}