#include<bits/stdc++.h>
#define X int x
#define LR int L,int R
#define m (L+R>>1)
#define LL x<<1,L,m
#define RR x<<1|1,m+1,R
#define V tr[x].v
#define S 20
#define N 200005
#define M 525252
#define uint unsigned
#define iv inline void
using namespace std;
int n,q,a[N],len[M];uint tg[M],C[N][S],pw[S],ans;
struct Seg{uint v[S];Seg(){fill(v,v+S,0);}
	friend Seg operator+(const Seg&a,const Seg&b){Seg r;
		for(int i=0;i<S;i++)for(int j=0;j<S-i;j++)
			r.v[i+j]+=a.v[i]*b.v[j];return r;}}tr[M],qv;
iv pu(X){tr[x]=tr[x<<1]+tr[x<<1|1];}
iv pt(X,int w,int F=1){tg[x]+=w;
	if(F){pw[0]=1;for(int i=1;i<S;i++)pw[i]=pw[i-1]*w;}
	for(int i=S-1;i>=0;i--)for(int j=0;j<i;j++)
		V[i]+=V[j]*C[len[x]-j][i-j]*pw[i-j];}
iv pd(X){if(tg[x])pt(x<<1,tg[x],1),pt(x<<1|1,tg[x]),tg[x]=0;}
iv bd(X,LR){len[x]=R-L+1;if(L==R)V[0]=1,V[1]=a[L];
	else bd(LL),bd(RR),pu(x);}
iv ud(X,LR,int l,int r,int w){if(l<=L&&R<=r){pt(x,w,1);return;}
	pd(x);if(l<=m)ud(LL,l,r,w);if(m<r)ud(RR,l,r,w);pu(x);}
inline Seg qr(X,LR,int l,int r){if(l<=L&&R<=r)return tr[x];pd(x);
	if(r<=m)return qr(LL,l,r);if(l>m)return qr(RR,l,r);
	return qr(LL,l,r)+qr(RR,l,r);}
inline int read(){
	int x=0,t=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')t=-1;ch=getchar();}
	while('0'<=ch&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	return x*t;}
iv write(int x){if(x<0)putchar('-'),x=-x;
	if(x>=10)write(x/10);putchar(x%10+'0');}
int main(){n=read(),q=read();
	for(int i=0;i<=n;C[i][0]=C[i][i]=1,i++)
		for(int j=1;j<min(i,S);j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
	for(int i=1;i<=n;i++)a[i]=read()-1;bd(1,1,n);
	for(int qq=1,o,l,r,w;qq<=q;qq++){o=read(),l=read(),r=read(),ans=0;
		if(o==1)w=read(),ud(1,1,n,l,r,w);else{qv=qr(1,1,n,l,r);
			for(int i=0;i<S;i++)ans+=qv.v[i];write(ans&1048575),
			putchar('\n');}}
	return 0;
}