#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define L (p << 1)
#define R (p << 1 | 1)
#define mid ((l + r) >> 1)
#define fi first
#define se second
#define MULT_TEST 0
using namespace std;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = (1ll << 20);
const int N = 200005, M = 25;
struct Seg {
    int C[M], tag;
} tr[N << 2];
int bit[M][M], a[N], pom[M];
const int Z = 1 << 20;
char buf[Z], *p1 = buf, *p2 = buf;
inline int getc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Z, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
    int x = 0;
    char ch = getc();
    while (!isdigit(ch)) ch = getc();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getc();
    return x;
}
inline void add(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}
inline Seg Merge(Seg A, Seg B) {
    Seg ans;
    for (int i = 0; i <= 20; i++) ans.C[i] = 0;
    ans.tag = 0;
    for (int i = 0; i <= 20; i++) {
        for (int j = 0; j <= 20; j++) {
            if (i + j > 20) continue;
            add(ans.C[i + j], 1ll * A.C[i] * B.C[j] % MOD);
        }
    }
    return ans;
}
inline Seg Add(Seg x, int y) {
    pom[0] = 1;
    for (int i = 1; i <= 20; i++) 
        pom[i] = 1ll * pom[i - 1] * y % MOD;
    for (int i = 0; i <= 20; i++) 
        for (int j = i + 1; j <= 20; j++) 
            add(x.C[i], 1ll * x.C[j] * pom[j - i] % MOD * bit[j][j - i] % MOD);
    add(x.tag, y);
}
inline void Pushup(int p) {
    tr[p] = Merge(tr[L], tr[R]);
}
inline void Pushdown(int p) {
    if (tr[p].tag) {
        tr[L] = Add(tr[L], tr[p].tag);
        tr[R] = Add(tr[R], tr[p].tag);
        tr[p].tag = 0;
    }
}
inline void Modify(int p, int l, int r, int ql, int qr, int d) {
    if (ql <= l && r <= qr) {
        tr[p] = Add(tr[p], d);
        return ;
    }
    Pushdown(p);
    if (ql <= mid) Modify(L, l, mid, ql, qr, d);
    if (qr > mid) Modify(R, mid + 1, r, ql, qr, d);
    Pushup(p);
}
inline Seg Query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[p];
    Pushdown(p);
    if (qr <= mid) return Query(L, l, mid, ql, qr);
    else if (ql > mid) return Query(R, mid + 1, r, ql, qr);
    else {
        Seg ans = Merge(Query(L, l, mid, ql, qr), Query(R, mid + 1, r, ql, qr));
        return ans;
    }
}
inline void Build(int p, int l, int r) {
    for (int i = 0; i <= 20; i++) tr[p].C[i] = 0;
    tr[p].tag = 0;
    if (l == r) {
        tr[p].C[1] = 1;
        tr[p].C[0] = a[l];
        return ;
    }
    Build(L, l, mid);
    Build(R, mid + 1, r);
    Pushup(p);
}
inline void Solve() {
    int n, q;
    n = read(); q = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    Build(1, 1, n);
    for (int i = 0; i <= 20; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) bit[i][j] = 1;
            else bit[i][j] = (bit[i - 1][j] + bit[i - 1][j - 1]) % MOD;
        }
    }
    while (q--) {
        int op = read(), l = read(), r = read();
        if (op == 1) {
            int x = read();
            if (x != 0) Modify(1, 1, n, l, r, x);
        }
        else {
            Seg ans = Query(1, 1, n, l, r);
            printf("%lld\n", ans.C[0]);
        }
    }
}
signed main() {
    int _ = 1;
#if MULT_TEST
    _ = read();
#endif 
    while (_--) Solve();
    return 0;
}