#include <bits/stdc++.h>
using namespace std;

bool Memory_begin;

/*
 */

// template <int mod>
// unsigned int down(unsigned int x)
// {
//     return x >= mod ? x - mod : x;
// }
// template <int mod>
// struct Modint
// {
//     unsigned int x;
//     Modint() = default;
//     Modint(unsigned int x) : x(x) {}
//     friend istream &operator>>(istream &in, Modint &a) { return in >> a.x; }
//     friend ostream &operator<<(ostream &out, Modint a) { return out << a.x; }
//     friend Modint operator+(Modint a, Modint b) { return down<mod>(a.x + b.x); }
//     friend Modint operator-(Modint a, Modint b) { return down<mod>(a.x - b.x + mod); }
//     friend Modint operator*(Modint a, Modint b) { return 1ULL * a.x * b.x % mod; }
//     friend Modint operator/(Modint a, Modint b) { return a * ~b; }
//     friend Modint operator^(Modint a, int b)
//     {
//         Modint ans = 1;
//         for (; b; b >>= 1, a *= a)
//             if (b & 1)
//                 ans *= a;
//         return ans;
//     }
//     friend Modint operator~(Modint a) { return a ^ (mod - 2); }
//     friend Modint operator-(Modint a) { return down<mod>(mod - a.x); }
//     friend Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
//     friend Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
//     friend Modint &operator*=(Modint &a, Modint b) { return a = a * b; }
//     friend Modint &operator/=(Modint &a, Modint b) { return a = a / b; }
//     friend Modint &operator^=(Modint &a, int b) { return a = a ^ b; }
//     friend Modint &operator++(Modint &a) { return a += 1; }
//     friend Modint operator++(Modint &a, int)
//     {
//         Modint x = a;
//         a += 1;
//         return x;
//     }
//     friend Modint &operator--(Modint &a) { return a -= 1; }
//     friend Modint operator--(Modint &a, int)
//     {
//         Modint x = a;
//         a -= 1;
//         return x;
//     }
//     friend bool operator==(Modint a, Modint b) { return a.x == b.x; }
//     friend bool operator!=(Modint a, Modint b) { return !(a == b); }
// };
// const int mod = 1e9 + 7;
// typedef Modint<mod> mint;

const int mod = 1 << 20, all = mod - 1, N = 2e5 + 5;
int n, q;
unsigned a[N];
struct node
{
    unsigned sum[20], tag;
} st[N << 2];
#define lc cur << 1
#define rc cur << 1 | 1
void pushup(int cur)
{
    for (int i = 0; i < 20; i++)
        st[cur].sum[i] = 0;
    for (int i = 0; i < 20; i++)
        for (int j = 0; i + j < 20; j++)
            st[cur].sum[i + j] += st[lc].sum[i] * st[rc].sum[j],
                st[cur].sum[i + j] &= all;
}
void pushdown(int cur)
{
    unsigned tmp = st[cur].tag;
    st[cur].tag = 0;
    st[lc].tag += tmp, st[rc].tag += tmp;
    for (int i = 0; i < 20; i++)
    {
        unsigned coef = 1;
        for (int j = i + 1; j < 20; j++)
        {
            coef *= tmp;
            coef &= all;
            st[lc].sum[i] += st[lc].sum[j] * coef;
            st[lc].sum[i] &= all;
            st[rc].sum[i] += st[rc].sum[j] * coef;
            st[rc].sum[i] &= all;
        }
    }
}
void build(int cur, int l, int r)
{
    if (l == r)
    {
        st[cur].sum[0] = a[l];
        st[cur].sum[1] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(cur);
}
void update(int cur, int l, int r, int a, int b, unsigned x)
{
    if (a <= l and r <= b)
    {
        st[cur].tag += x;
        for (int i = 0; i < 20; i++)
        {
            unsigned coef = 1;
            for (int j = i + 1; j < 20; j++)
            {
                coef *= x;
                coef &= all;
                st[cur].sum[i] += st[cur].sum[j] * coef;
                st[cur].sum[i] &= all;
            }
        }
        return;
    }
    int mid = l + r >> 1;
    pushdown(cur);
    if (a <= mid)
        update(lc, l, mid, a, b, x);
    if (b > mid)
        update(rc, mid + 1, r, a, b, x);
    pushup(cur);
}
unsigned query(int cur, int l, int r, int a, int b)
{
    if (a > r or b < l)
        return 1;
    if (a <= l and r <= b)
        return st[cur].sum[0];
    int mid = l + r >> 1;
    pushdown(cur);
    return (query(lc, l, mid, a, b) * query(rc, mid + 1, r, a, b)) & all;
}

bool Memory_end;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int opt, l, r, x;
        cin >> opt >> l >> r;
        if (opt == 1)
        {
            cin >> x;
            update(1, 1, n, l, r, x);
        }
        else
            cout << query(1, 1, n, l, r) << '\n';
    }
}
/*
 */