#include <bits/stdc++.h>
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define repd(x, r, l) for(int x = r; x >= l; x--)
#define clr(x, y) memset(x, y, sizeof(x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const int INF = 0x3f3f3f3f;
const int mod = 1 << 20;

const int MAXN = 2e5 + 5;

struct node{
    int flag;
    node(){
        flag = 0;
    }
    ui f[20];
}tree[MAXN * 4], z;
ui pw[25], C[MAXN + 25][25], tag[MAXN * 4];
int a[MAXN];

node merge(node a, node b){
    if(a.flag == -1) return b;
    if(b.flag == -1) return a;
    node res;
    rep(i, 0, 19){
        res.f[i] = 0;
        rep(j, 0, i) res.f[i] += a.f[j] * b.f[i - j];
    }
    return res;
}

void add(int p, int pl, int pr, ui x){
    pw[0] = 1;
    rep(i, 1, 19) pw[i] = pw[i - 1] * x;
    repd(i, 19, 1){
        rep(j, 0, i - 1){
            // if(pr - pl + 1 < i) continue;
            tree[p].f[i] += tree[p].f[j] * C[pr - pl + 1 - j][i - j] * pw[i - j];
        }
    }
}

void pushup(int p){
    tree[p] = merge(tree[ls(p)], tree[rs(p)]);
}

void pushdown(int p, int pl, int pr){
    if(!tag[p]) return;
    int mid = (pl + pr) >> 1;
    add(ls(p), pl, mid, tag[p]);
    add(rs(p), mid + 1, pr, tag[p]);
    tag[ls(p)] += tag[p];
    tag[rs(p)] += tag[p];
    tag[p] = 0;
}

void build(int p, int pl, int pr){
    if(pl == pr){
        tree[p].f[0] = 1;
        tree[p].f[1] = a[pl] - 1;
        return;
    }
    int mid = (pl + pr) >> 1;
    build(ls(p), pl, mid);
    build(rs(p), mid + 1, pr);
    pushup(p);
}

void update(int p, int pl, int pr, int l, int r, ui x){
    if(pl > r || pr < l) return;
    if(pl >= l && pr <= r){
        add(p, pl, pr, x);
        tag[p] += x;
        return;
    }
    pushdown(p, pl, pr);
    int mid = (pl + pr) >> 1;
    update(ls(p), pl, mid, l, r, x);
    update(rs(p), mid + 1, pr, l, r, x);
    pushup(p);
}

node query(int p, int pl, int pr, int l, int r){
    if(pl > r || pr < l) return z;
    if(pl >= l && pr <= r) return tree[p];
    pushdown(p, pl, pr);
    int mid = (pl + pr) >> 1;
    return merge(query(ls(p), pl, mid, l, r), query(rs(p), mid + 1, pr, l, r));
}

int main(){
    // freopen("1.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    z.flag = -1;
    int n, q;
    scanf("%d%d", &n, &q);
    rep(i, 1, n + 20){
        C[i][0] = C[i][i] = 1;
        rep(j, 1, 20) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    rep(i, 1, n) scanf("%d", &a[i]);
    build(1, 1, n);
    while(q--){
        int opt, l, r, x;
        scanf("%d%d%d", &opt, &l, &r);
        if(opt == 1){
            scanf("%d", &x);
            update(1, 1, n, l, r, x);
        }
        else{
            node res = query(1, 1, n, l, r);
            ui ans = 0;
            // rep(i, 0, 5) printf("%d  ", res.f[i]);
            // puts("");
            rep(i, 0, 19) ans += res.f[i];
            printf("%d\n", ans % mod);
        }
    }
    return 0;
}