#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=25,mod=1<<20;
int n,q,b[N],C[M][M];
void add(int &x,int y){
	x=(x+y)%mod;
}
struct node{
	int l,r,c,p,a[21];
	node(){
		memset(a,0,sizeof a);
		c=0;
	}
}e[N*4];
struct segment{
	int n;
	#define l(x) e[x].l
	#define r(x) e[x].r
	#define c(x) e[x].c
	node mer2(node &x,node &y){
		int ls=x.r-x.l+1,rs=y.r-y.l+1;
		node z;
		int w=min(ls+rs,20);
		z.a[w]=1;
		z.l=x.l,z.r=y.r;
		rep(i,0,ls){
			rep(j,0,rs){
				if(i+j>=w)break;
				int v=1ll*x.a[i]*y.a[j]%mod;
				add(z.a[i+j],v);
			}
		}
		return z;
	}
	void up(int p){
		e[p]=mer2(e[p<<1],e[p<<1|1]);
	}
	void psd2(node &x,int v){
		int len=x.r-x.l+1,sz=min(20,len);
		vector<int>pw(sz+1,1);
		rep(i,1,sz)pw[i]=1ll*pw[i-1]*v%mod;
		rep(i,0,sz-1){
			rep(j,i+1,sz){
				int v=1ll*x.a[j]*pw[j-i]%mod*C[j][j-i]%mod;
				add(x.a[i],v);
			}
		}
	}
	void psd(int p){
		if(c(p)){
			psd2(e[p<<1],c(p));
			add(c(p<<1),c(p));
			psd2(e[p<<1|1],c(p));
			add(c(p<<1|1),c(p));
			c(p)=0;
		}
	}
	void bld(int p,int l,int r){
		l(p)=l,r(p)=r,c(p)=0;
		if(l==r){
			e[p].a[0]=b[l];
			e[p].a[1]=1;
			return;
		}
		int mid=(l+r)/2;
		bld(p<<1,l,mid);
		bld(p<<1|1,mid+1,r);
		up(p);
	}
	void init(int _n){
		n=_n;
		bld(1,1,n);
	}
	void upd(int p,int ql,int qr,int x){
		if(ql<=l(p) && r(p)<=qr){
			psd2(e[p],x);
			add(c(p),x);
			return;
		}
		psd(p);
		int mid=(l(p)+r(p))/2;
		if(ql<=mid)upd(p<<1,ql,qr,x);
		if(qr>mid)upd(p<<1|1,ql,qr,x);
		up(p);
	}
	node ask(int p,int ql,int qr){
		if(ql<=l(p) && r(p)<=qr){
			return e[p];
		}
		psd(p);
		int mid=(l(p)+r(p))/2;
		if(ql<=mid && qr>mid){
			node L=ask(p<<1,ql,qr);
			node R=ask(p<<1|1,ql,qr);
			node res=mer2(L,R);
			return res;	
		}
		else if(ql<=mid){
			node L=ask(p<<1,ql,qr);
			return L;
		}
		else{
			node R=ask(p<<1|1,ql,qr);
			return R;
		}
	}
}seg;
void init(){
	C[0][0]=1;
	int up=21;
	rep(i,1,up){
		C[i][0]=C[i][i]=1;
		rep(j,1,i-1){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
}
int main(){
	init();
	sci(n),sci(q);
	rep(i,1,n)sci(b[i]);
	seg.init(n);
	rep(i,1,q){
		int op,l,r,x;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			sci(x);
			seg.upd(1,l,r,x);
		}
		else{
			printf("%d\n",seg.ask(1,l,r).a[0]);
		}
	}
	return 0;
}