#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define lowbit(x) ((x) & (-x))
constexpr int N = 2e5 + 10;
constexpr int M = 5e5 + 10;
constexpr ll mod = (1LL<<20);
constexpr int INF = 0x3f3f3f3f;
constexpr ll Base = 131;
constexpr int MAXBIT = 19;
ui ksm(ui r1, ui r2)
{
    ui res=1;
    while(r2)
    {
        if(r2&1)
            res*=r1;
        r2>>=1;
        r1*=r1;
    }
    return res;
}
ui a[N];
ui C[N][20];
struct Node
{
    int l,r;
    ui lz;
    ui p[25];
}tr[N<<2];
void pushup(Node &u,Node &ls,Node &rs)
{
    for(int i=0;i<=19;i++)
        u.p[i]=0;
    for(int i=0;i<=19;i++)
        for(int j=0;j<=19-i;j++)
            u.p[i+j]+=ls.p[i]*rs.p[j];
}
void pushup(int p){pushup(tr[p],tr[p*2],tr[p*2+1]);}
void build(int p,int l,int r)
{
    tr[p]={l,r,0};
    if(l==r)
    {
        tr[p].p[0]=1;
        tr[p].p[1]=a[l];
        // tr[p].p[0]=a[l];
        // tr[p].p[1]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void pushdown(Node &u,ui x)
{
    for(int i=19;i>=1;i--)
        for(int j=0;j<=i-1;j++)
            u.p[i]+=u.p[j]*ksm(x,i-j)*C[u.r-u.l+1-j][i-j];
	u.lz+=x;  
}
void pushdown(Node &u,Node &ls,Node &rs)
{
    if(u.lz)
    {
        pushdown(ls,u.lz),pushdown(rs,u.lz);
        u.lz=0;
    }
}
void pushdown(int p){pushdown(tr[p],tr[p*2],tr[p*2+1]);}
void update(int p,int x,int y,int z)
{
    if(x<=tr[p].l && tr[p].r<=y)
    {
        pushdown(tr[p],z);
        return;
    }
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(x<=mid)
        update(p*2,x,y,z);
    if(y>mid)
        update(p*2+1,x,y,z);
    pushup(p);
}
Node query(int p,int x,int y)
{
    if(x<=tr[p].l && tr[p].r<=y)
        return tr[p];
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    Node r1,r2,r3;
    if(y<=mid)
        return query(p*2,x,y);
    if(x>mid)
        return query(p*2+1,x,y);
    r1=query(p*2,x,y),r2=query(p*2+1,x,y);
    pushup(r3,r1,r2);
    return r3;
}
void solve()
{   
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]-=1;
    }
    C[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		C[i][0]=1;
        for(int j=1;j<=19;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int f,l,r,x;
        cin>>f>>l>>r;
        if(f==1)
        {   
            cin>>x;
            if(x==0)
                continue;
            update(1,l,r,x);
        }
        else
        {
            Node res=query(1,l,r);
			ui ans=0;
            for(int i=0;i<=19;i++)
                ans+=res.p[i];
			ans&=(1<<20)-1;
			cout<<ans<<'\n';
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    int _ = 1;
    // cin >> _;
    while (_--)
        solve();
    return 0;
}