#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;
const int K = 20;
const int N = 2e5 + 11;
const int MOD = 1 << K;
struct node{
    unsigned int P[K];
    node () {
        fill(P, P + K, 0);
    }
    node (int a) {
        if (a == INF) {
            P[0] = INF;
            return;
        }
        fill(P, P + K, 0);
        P[0] = a; P[1] = 1;
    }
};

node operator+ (const node& a, const node& b){
    if(a.P[0] == INF || b.P[0] == INF) return a.P[0] != INF ? a : b;
    node c;
    for(int i = 0; i < K; i++){
        for(int j = 0; j < K - i; j++){
            c.P[i + j] += a.P[i] * b.P[j];
        }
    }
    for(int i = 0; i < K; i++){
        c.P[i] %= MOD;
    }
}

unsigned C[K][K];

void operator+= (node& a, unsigned int k){
    unsigned Q[K] = {}, pw[K] = {};
    pw[0] = 1; for(int i = 1; i < K; i++) pw[i] = pw[i - 1] * k;
    for(int i = 0; i < K; i++){
        for(int j = i; j < K; j++){
            Q[i] += C[j][j - i] * pw[j - i] * a.P[j];
        }
    }
    for(int i = 0; i < K; i++) Q[i] %= MOD;
    for(int i = 0; i < K; i++) a.P[i] = Q[i];
}

node t[N << 2]; unsigned lz[N << 2];
int a[N];

int n, q;
void push(int v){
    if(!lz[v]) return;
    t[v * 2 + 1] += lz[v];
    t[v * 2 + 2] += lz[v];
    lz[v * 2 + 1] += lz[v];
    lz[v * 2 + 2] += lz[v];
    lz[v] = 0;
}

void build(int v = 0, int l = 1, int r = n){
    if(l == r) t[v] = node(a[l]);
    else {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m + 1, r);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }
}
void range_add(int ql, int qr, unsigned k, int v = 0, int l = 1, int r = n){
    if(qr < l || r < ql) return;
    if(ql <= l && r <= qr) { t[v] += k; lz[v] += k; return; }
    int m = (l + r) / 2; push(v);
    range_add(ql, qr, k, v * 2 + 1, l, m);
    range_add(ql, qr, k, v * 2 + 2, m + 1, r);
    t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

node range_query(int ql, int qr, int v = 0, int l = 1, int r = n){
    if(qr < l || r < ql) return node(INF);
    else if(ql <= l && r <= qr) return t[v];
    else {
        int m = (l + r) / 2; push(v);
        node a = range_query(ql, qr, v * 2 + 1, l, m);
        node b = range_query(ql, qr, v * 2 + 2, m + 1, r);
        return a + b;
    }
}

void prec_C(){
    for(int i = 0; i < K; i++){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++){
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}

int32_t main(){
    prec_C();
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build();
    for(int i = 0; i < q; i++){
        int ty; cin >> ty;
        if(ty == 1){
            int l, r, k; cin >> l >> r >> k;
            range_add(l, r, k);
        }else{
            int l, r; cin >> l >> r;
            node ans = range_query(l, r);
            cout << (ans.P[0] % MOD) << '\n';
        }
    }
}