#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef unsigned long long ull;
ull A[maxn];
typedef array<ull,20> info;
ull C[20][20];
info zero;
info operator+(info x,info y){
    info p{};
    for(int i=0;i<20;i++){
        for(int j=0;j+i<20;j++)p[i+j]+=x[i]*y[j];
    }
    return p;
};
info operator+(info x,ull t){
    info p{};
    info Pow{};
    Pow[0]=1;
    for(int i=1;i<20;i++)Pow[i]=Pow[i-1]*t;
    for(int i=0;i<20;i++){
        for(int j=0;j<=i;j++)p[j]+=x[i]*C[i][j]*Pow[i-j];
    }
    return p;
};
struct Node{
    int l,r;
    ull tag=0;
    info res{};
};
struct SegmentTree{
    Node a[maxn*4];
    void tag_init(int i){
        a[i].tag=0;
    }
    void tag_union(int fa,int i){
        a[i].tag+=a[fa].tag;
    }
    void tag_cal(int i){
        a[i].res=a[i].res+a[i].tag;
    }
    void pushdown(int i){
        tag_cal(i);
        if(a[i].l!=a[i].r){
            tag_union(i,i*2);
            tag_union(i,i*2+1);
        }
        tag_init(i);
    }
    void pushup(int i){
        if(a[i].l==a[i].r)return;
        pushdown(i*2);
        pushdown(i*2+1);
        a[i].res=a[i*2].res+a[i*2+1].res;
    }
    void build(int i,int l,int r){
        a[i].l=l,a[i].r=r;tag_init(i);
        if(l==r)a[i].res[1]=1,a[i].res[0]=A[l];
        if(l>=r)return;
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        a[i].res=a[i*2].res+a[i*2+1].res;
    }
    void update(int i,int l,int r,int w){
        pushdown(i);
        if(a[i].r<l||a[i].l>r||l>r)return;
        if(a[i].l>=l&&a[i].r<=r){
            a[i].tag=w;
            return;
        }
        update(i*2,l,r,w);
        update(i*2+1,l,r,w);
        pushup(i);
    }
    info query(int i,int l,int r){
        pushdown(i);
        if(a[i].r<l||a[i].l>r||l>r)return zero;
        if(a[i].l>=l&&a[i].r<=r){
            return a[i].res;
        }
        return query(i*2,l,r)+query(i*2+1,l,r);
    }
};
SegmentTree tri;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    zero[0]=1;
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>A[i];
    tri.build(1,1,n);
    for(int i=0;i<20;i++){
        C[i][i]=1;
        C[i][0]=1;
        for(int j=1;j<i;j++)C[i][j]=C[i-1][j]+C[i-1][j-1];
        // for(int j=0;j<=i;j++)cout<<C[i][j]<<" \n"[j==i];
    }
    for(int i=1;i<=q;i++){
        int ops;cin>>ops;
        if(ops==1){
            int l,r;
            ull w;
            cin>>l>>r>>w;
            tri.update(1,l,r,w);
        }
        else{
            int l,r;cin>>l>>r;
            info t=tri.query(1,l,r);
            // for(int i=0;i<20;i++)cout<<t[i]<<" ";;cout<<"\n";
            cout<<t[0]%(1<<20)<<'\n';
        }
    }
}