#include <cstdio>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
#include <algorithm>
#include <ctime>
using namespace std;

typedef unsigned int u32;
typedef unsigned long long u64;
typedef __m128i u128;

////////////////////////////////////////////////////////////////

const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
    return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp ++) : *rp ++;
}
inline u32 read_u32() {
    u32 x = 0;
    char ch = read_char();
    for (; ch < '0' || ch > '9'; ch = read_char());
    for (; ch >= '0' && ch <= '9'; ch = read_char()) x = x * 10 + (ch - '0');
    return x;
}
char wb[BUFFER_SIZE], *wp = wb;
inline void write_flush() {
    fwrite(wb, 1, wp - wb, stdout), wp = wb;
}
inline void write_char(char c) {
    *wp ++ = c;
    if (wp == wb + BUFFER_SIZE) write_flush();
}
inline void write_u32(u32 x) {
    if (x == 0) write_char('0');
    static char b[32], i;
    for (i = 1; x; x /= 10, i ++) b[i] = x % 10 + '0';
    for (i --; i; i --) write_char(b[i]);
}

////////////////////////////////////////////////////////////////

u32 a[200000 + 16];

int main() {
    u32 N = read_u32(), Q = read_u32();
    for (int i = 1; i <= N; i ++) {
        a[i] = read_u32();
    }
    for (int i = 1; i <= Q; i ++) {
        u32 o = read_u32();
        u32 l = read_u32();
        u32 r = read_u32();
        u32 *p = a + l, *q = a + r + 1;
        if (o == 1u) {
            u32 x = read_u32();
            u128 y = _mm_set1_epi32(x);
            for (; ((u64)p & 15u) && p != q; p ++) {
                p[0] += x;
            }
            u32 m = q - p >> 4u;
            for (; m --; p += 16u) {
                ((u128*)p)[0] = _mm_add_epi32(((u128*)p)[0], y);
                ((u128*)p)[1] = _mm_add_epi32(((u128*)p)[1], y);
                ((u128*)p)[2] = _mm_add_epi32(((u128*)p)[2], y);
                ((u128*)p)[3] = _mm_add_epi32(((u128*)p)[3], y);
            }
            for (; p != q; p ++) {
                p[0] += x;
            }
        } else {
            u32 y = 1u;
            for (; ((u64)p & 15u) && p != q; p ++) {
                y *= p[0];
            }
            u32 m = q - p >> 4u;
            u128 y0 = _mm_set1_epi32(1u);
            u128 y1 = _mm_set1_epi32(1u);
            u128 y2 = _mm_set1_epi32(1u);
            u128 y3 = _mm_set1_epi32(1u);
            for (; m --; p += 16u) {
                y0 = _mm_mullo_epi32(y0, ((u128*)p)[0]);
                y1 = _mm_mullo_epi32(y1, ((u128*)p)[1]);
                y2 = _mm_mullo_epi32(y2, ((u128*)p)[2]);
                y3 = _mm_mullo_epi32(y3, ((u128*)p)[3]);
            }
            y0 = _mm_mullo_epi32(y0, y1);
            y2 = _mm_mullo_epi32(y2, y3);
            y0 = _mm_mullo_epi32(y0, y2);
            y *= ((u32*)&y0)[0];
            y *= ((u32*)&y0)[1];
            y *= ((u32*)&y0)[2];
            y *= ((u32*)&y0)[3];
            for (; p != q; p ++) {
                y *= p[0];
            }
            y &= 0xfffff;
            write_u32(y), write_char('\n');
        }
    }
    write_flush();
    fprintf(stderr, "clock=%u\n", (u32)clock());
    return 0;
}