// Problem: P10045 [CCPC 2023 北京市赛] 线段树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10045
// Memory Limit: 1 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define uint int
#define F(i,a,b) for(int i=(a),i##end=(b);i<=(i##end);++i)
#define UF(i,a,b) for(int i=(a),i##end=(b);i>=(i##end);--i)
const int N=200005,M=1145,K=21,len=1;
int mod=1048576;
int n,q,a[N],mul[M][K],tag[M];
inline int bl(int x){
	return (x+len-1)/len;
}
inline int L(int id){
	return len*(id-1)+1;
}
inline int R(int id){
	return min(n,len*id);
}
inline void rebuild(int id){
	for(register int i=1;i<=20;i++){
		mul[id][i]=0;
	}
	mul[id][1]=1;
	for(register int i=L(id);i<=R(id);i++){
		for(register int j=20;j>=1;j--){
			mul[id][j]=mul[id][j]*a[i]+mul[id][j-1];
		}
	}
	return ;
}
inline void build(){
	for(int i=1;i<=n;i++){
		if(bl(i)!=bl(i-1)){
			rebuild(bl(i));
		}
	}
	return ;
}
inline void pushdown(int id){
	if(!tag[id]){
		return ;
	}
	for(register int i=L(id);i<=R(id);i++){
		a[i]+=tag[id];
	}
	tag[id]=0;
	rebuild(id);
	return ;
}
inline void add(int l,int r,int k){
	if(bl(l)==bl(r)){
		pushdown(bl(l));
		for(register int i=l;i<=r;i++){
			a[i]+=k;
		}
		rebuild(bl(l));
		return ;
	}
	pushdown(bl(l));
	for(register int i=l;i<=R(bl(l));i++){
		a[i]+=k;
	}
	rebuild(bl(l));
	pushdown(bl(r));
	for(register int i=L(bl(r));i<=r;i++){
		a[i]+=k;
	}
	rebuild(bl(r));
	for(register int i=bl(l)+1;i<=bl(r)-1;i++){
		tag[i]+=k;
	}
	return ;
}
inline int query(int l,int r){
	if(bl(l)==bl(r)){
		pushdown(bl(l));
		int ans=1;
		for(register int i=l;i<=r;i++){
			ans*=a[i];
		}
		return ans;
	}
	int ans=1;
	pushdown(bl(l));
	for(register int i=l;i<=R(bl(l));i++){
		ans*=a[i];
	}
	rebuild(bl(l));
	pushdown(bl(r));
	for(register int i=L(bl(r));i<=r;i++){
		ans*=a[i];
	}
	rebuild(bl(r));
	for(register int i=bl(l)+1;i<=bl(r)-1;i++){
		int tmp=1;
		int ml=0,cnt=1;
		while(tmp%mod){
			ml=ml+tmp*mul[i][cnt];
			tmp*=tag[i];
			++cnt;
		}
		ans*=ml;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    build();
	while(q--){
		int op,l,r,x;
		cin>>op>>l>>r;
		if(op==1){
			cin>>x;
			add(l,r,x);
		}
		else{
			int f=query(l,r)%mod+mod;
			cout<<(f>mod?f-mod:f)<<'\n';
		}
	}
	return 0;
}