#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
using namespace std;

template <class T>
void read(T& x) {
    char ch;
    bool ok;
    for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
    for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    if(ok) x = -x;
}

#define maxn 200000
#define U unsigned
struct Poi : vector<U int> {
    Poi() { resize(20, 0); }
};
Poi operator ^ (cst Poi &_x, cst Poi &_y) {
    Poi tem;
    For(i, 0, 19) For(j, 0, i) tem[i] += _x[j] * _y[i - j];
    return tem;
}
Poi poi[4 * maxn + 5];
U int lpr[4 * maxn + 5];
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define md (l + r >> 1)

int n, q, a[maxn + 5];
U int c[maxn + 5][20], mod = (1 << 20) - 1;
void upd(int rt) { poi[rt] = poi[ls] ^ poi[rs]; }
void build(int rt, int l, int r) {
    if(l == r) {
        poi[rt][0] = 1; poi[rt][1] = a[l] - 1;
        return;
    }
    build(ls, l, md); build(rs, md + 1, r);
    upd(rt);
}
void mson(int rt, int l, int r, U int x) {
    lpr[rt] += x;
    Rof(i, 19, 0) {
        int dd = max(0, i - (r - l + 1));
        U int pw = 1;
        For(o, 1, dd) pw *= x;
        For(j, dd, i) {
            // assert(r - l + 1 - (i - j) >= 0);
            if(j) poi[rt][i] += poi[rt][i - j] * pw * c[r - l + 1 - (i - j)][j];
            pw *= x;
        }
    }
    // cout << po
}
void spr(int rt, int l, int r) {
    if(lpr[rt]) {
        mson(ls, l, md, lpr[rt]);
        mson(rs, md + 1, r, lpr[rt]);
        lpr[rt] = 0;
    }
}
void mdy(int rt, int l, int r, int ql, int qr, int x) {
    if(ql <= l && qr >= r) return mson(rt, l, r, x);
    spr(rt, l, r);
    if(ql <= md) mdy(ls, l, md, ql, qr, x);
    if(qr > md) mdy(rs, md + 1, r, ql, qr, x);
    upd(rt);
}
Poi que(int rt, int l, int r, int ql, int qr) {
    if(ql <= l && qr >= r) return poi[rt];
    spr(rt, l, r);
    Poi res; res[0] = 1;
    if(ql <= md) res = res ^ que(ls, l, md, ql, qr);
    if(qr > md) res = res ^ que(rs, md + 1, r, ql, qr);
    return res;
}

int main() {
    // freopen("in.txt", "r", stdin);
    read(n); read(q);
    For(i, 1, n) read(a[i]);
    build(1, 1, n);
    c[0][0] = 1;
    For(i, 1, n) {
        c[i][0] = 1;
        For(j, 1, 19) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    // cout << c[4][5] << endl;
    while(q--) {
        int op, l, r, x; read(op); read(l); read(r);
        if(op == 1) {
            read(x);
            mdy(1, 1, n, l, r, x);
        }
        else {
            Poi tem = que(1, 1, n, l, r);
            // cout << tem[1] << endl;
            U int res = 0;
            For(i, 0, 19) res += tem[i];
            printf("%u\n", res & mod);
        }
    }
    return 0;
}