// 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;
const int N=200005,M=1145,K=21,len=314;
int mod=1048576;
int n,q,a[N],mul[N][K],tag[N];
namespace lyx{
	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 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(r));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(int i=l;i<=r;i++){
				ans*=a[i];
			}
			return ans;
		}
		int ans=1;
		for(register int i=l;i<=R(bl(l));i++){
			ans*=a[i];
		}
		for(register int i=L(bl(r));i<=r;i++){
			ans*=a[i];
		}
		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;
	}
}
using namespace lyx;
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;
}