#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
const int Mod=1<<20;

struct node
{
	int l,r,add;
	long long val[22];
};

node res[N*4];
int a[N];

void pushup(int rt)
{
	memset(res[rt].val,0,sizeof(res[rt].val));
	for(int i=0;i<20;i++)
		if(res[rt*2].val[i])
			for(int j=0;i+j<20;j++)
				if(res[rt*2+1].val[j])
					res[rt].val[i+j] += res[rt*2].val[i]*res[rt*2+1].val[j];

	for(int i=0;i<20;i++)
		res[rt].val[i] %= Mod;
}

long long p[25],C[N][22];

void add(int rt,int val)
{
	(res[rt].add += val) %= Mod;
	p[0]=1;
	for(int i=1;i<=19;i++)
		p[i]=p[i-1]*val%Mod;

	int len=res[rt].r-res[rt].l+1;
	for(int i=min(len,19);i>=0;i--)
		if(res[rt].val[i])
			for(int j=min(len,19);j>i;j--)
				(res[rt].val[j] += res[rt].val[i]*C[len-i][j-i]%Mod*p[j-i]) %= Mod;
}

void pushdown(int rt)
{
	if(res[rt].add)
	{
		add(rt*2,res[rt].add);
		add(rt*2+1,res[rt].add);
		res[rt].add=0;
	}
}

void build(int rt,int l,int r)
{
	res[rt].l=l, res[rt].r=r;
	if(l==r)
	{
		res[rt].val[0]=1;
		res[rt].val[1]=a[l];
		return;
	}

	int mid=(l+r)/2;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	pushup(rt);
}

void update(int rt,int l,int r,int val)
{
	if(l<=res[rt].l && res[rt].r<=r)
	{
		add(rt,val);
		return;
	}

	pushdown(rt);
	int mid=(res[rt].l+res[rt].r)/2;
	if(l<=mid)
		update(rt*2,l,r,val);
	if(mid+1<=r)
		update(rt*2+1,l,r,val);
	pushup(rt);
}

int query(int rt,int l,int r)
{
	if(l<=res[rt].l && res[rt].r<=r)
	{
		long long ans=0;
		for(int i=0;i<=19;i++)
			ans += res[rt].val[i];
		return ans%Mod;
	}

	pushdown(rt);
	int mid=(res[rt].l+res[rt].r)/2;
	long long ans=1;
	if(l<=mid)
		ans *= query(rt*2,l,r);
	if(mid+1<=r)
		ans *= query(rt*2+1,l,r);
	return ans%Mod;
}

int main()
{
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]--;
	}

	C[0][0]=1;
	for(int i=1;i<=200000;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=20;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
	}

	build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		int op,l,r;
		scanf("%d %d %d",&op,&l,&r);
		if(op==1)
		{
			int x;
			scanf("%d",&x);
			update(1,l,r,x);
		}
		else
			printf("%d\n",query(1,l,r));
	}
	return 0;
}