#include<bits/stdc++.h>
#define lc(p) p<<1
#define rc(p) p<<1|1
using namespace std;
typedef long long LL;
inline int read(){
    char ch=getchar();
    while(!isdigit(ch) && ch!='-') ch=getchar();
    int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
    return x*ff;
}
const int N=2e5+5,P=1<<20;
int n,Q,a[N];
struct node{
    int mx[20];
    node operator + (node A) const {
        node B; for(int i=0;i<20;i++) B.mx[i]=0;
        for(int i=0;i<20;i++)
            for(int j=0;j<20-i;j++) (B.mx[i+j]+=1ll*mx[i]*A.mx[j]%P)%=P;
        return B;
    }
} tr[N<<2]; int tg[N<<2],bfw[20],lm[N<<2],C[N][20];
void addt(int p,int w){
    (tg[p]+=w)%=P; bfw[0]=1;
    for(int i=1;i<20;i++) bfw[i]=1ll*bfw[i-1]*w%P;
    for(int i=19;i>=0;i--)
        for(int j=0;j<i;j++) (tr[p].mx[i]+=1ll*tr[p].mx[j]*bfw[i-j]%P*C[lm[p]-j][i-j])%=P;
}
void pushup(int p){ tr[p]=tr[lc(p)]+tr[rc(p)]; }
void pushdn(int p){
    if(tg[p]) addt(lc(p),tg[p]),addt(rc(p),tg[p]),tg[p]=0;
}
void build(int p,int L,int R){
    lm[p]=R-L+1; if(L==R) { tr[p].mx[0]=1; tr[p].mx[1]=a[L]; return ;}
    int mid=(L+R)/2; build(lc(p),L,mid); build(rc(p),mid+1,R); pushup(p);
}
void Mdf(int p,int L,int R,int lt,int rt,int w){
    if(L>rt || R<lt) return ;
    if(L>=lt && R<=rt) {addt(p,w); return ;} 
    int mid=(L+R)/2; pushdn(p);
    Mdf(lc(p),L,mid,lt,rt,w); Mdf(rc(p),mid+1,R,lt,rt,w); pushup(p);
}
node Qry(int p,int L,int R,int lt,int rt){
    if(L>=lt && R<=rt) return tr[p];
    int mid=(L+R)/2; pushdn(p);
    if(rt<=mid) return Qry(lc(p),L,mid,lt,rt);
    else if(lt>mid) return Qry(rc(p),mid+1,R,lt,rt);
    else return Qry(lc(p),L,mid,lt,rt)+Qry(rc(p),mid+1,R,lt,rt);
}
int main(){
    n=read(); Q=read();
    C[0][0]=1;
    for(int i=1;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<20;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
    }
    for(int i=1;i<=n;i++) a[i]=read()-1;
    build(1,1,n);
    while(Q--){
        int o=read(),l=read(),r=read(),w;
        if(o==1) w=read(),Mdf(1,1,n,l,r,w);
        else {
            node bf=Qry(1,1,n,l,r);
            int ans=0; for(int i=0;i<20;i++) (ans+=bf.mx[i])%=P;
            printf("%d\n",ans);
        }
    }
    return 0;
}