// #define NDEBUG
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using db = double;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#if defined(TEXT_IO) and defined(LOCAL) and not defined(ONLINE_JUDGE)
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
#endif
	Main();
	return 0;
}
/**************************************************/
namespace my
{
#if defined(LOCAL) and not defined(ONLINE_JUDGE)
#include "D:\VScodeFile\LOCAL\debug.h"
#define DBG(x) std::cerr << "! " #x " = " << (x) << std::endl
#else
#define dbg(...) ((void)0)
#define DBG(...) ((void)0)
#endif
#define VE std::vector
#define STR std::string
#define HEAP std::priority_queue
#define PLL std::pair<ll, ll>
#define fi first
#define se second
#define EDL '\n'
#define WS ' '
#define SDP(x) std::fixed << std::setprecision(x)
#define SZ(x) ((ll)x.size())
#define FOR(i, l, r) for (ll i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (ll i = (r); i >= (l); --i)
	constexpr int inf = 0x3f3f3f3f;
	constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;
	constexpr db EPS = 1.0e-9;
	constexpr ll MOD2 = 1e9 + 7;
	constexpr ll MOD = 1LL << 20;
	constexpr ll SZ2 = 1e3 + 3;
	constexpr ll SZ = 2e5 + 5;
}
using namespace my;
namespace fastIO
{
	constexpr ll BUF_SZ = 1e5 + 5;
	bool IOrun = true;
	char NC(void)
	{
		static char buf[BUF_SZ], *p = buf + BUF_SZ, *ed = buf + BUF_SZ;
		if (p != ed)
			return *p++;
		p = buf;
		ed = buf + fread(buf, 1, BUF_SZ, stdin);
		if (p == ed)
		{
			IOrun = false;
			return -1;
		}
		return *p++;
	}
	bool BLK(char c) { return c == WS or c == EDL or c == '\r' or c == '\t'; }
	template <class T>
	bool FIN(T &x)
	{
		bool sign = false;
		char c = NC();
		x = 0;
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		if (c == '-')
		{
			sign = true;
			c = NC();
		}
		while ('0' <= c and c <= '9')
		{
			x = x * 10 + c - '0';
			c = NC();
		}
		if (sign)
			x = -x;
		return true;
	}
	bool FIN(db &x)
	{
		bool sign = false;
		char c = NC();
		x = 0;
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		if (c == '-')
		{
			sign = true;
			c = NC();
		}
		while ('0' <= c and c <= '9')
		{
			x = x * 10 + c - '0';
			c = NC();
		}
		if (c == '.')
		{
			db w = 1.0;
			c = NC();
			while ('0' <= c and c <= '9')
			{
				w /= 10.0;
				x += w * (c - '0');
				c = NC();
			}
		}
		if (sign)
			x = -x;
		return true;
	}
	bool FIN(char &c)
	{
		c = NC();
		while (BLK(c))
			c = NC();
		if (not IOrun)
		{
			c = -1;
			return false;
		}
		return true;
	}
	bool FIN(char *s)
	{
		char c = NC();
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		while (IOrun and not BLK(c))
		{
			*s++ = c;
			c = NC();
		}
		*s = 0;
		return true;
	}
	bool LIN(char *s)
	{
		char c = NC();
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		while (IOrun and c != EDL)
		{
			*s++ = c;
			c = NC();
		}
		*s = 0;
		return true;
	}
	template <class T, class... Y>
	bool FIN(T &x, Y &...o) { return FIN(x) and FIN(o...); }
	void FIN(ll *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
	void FIN(db *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
	void FIN(char *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
}
using fastIO::FIN;
using fastIO::LIN;
template <ll MOD>
struct ModInt
{
public:
	ModInt() : v(0) {}
	template <typename T>
	ModInt(T x)
	{
		ll tmp = x;
		if (0 <= tmp and tmp < MOD)
			v = tmp;
		else if (MOD <= tmp)
			v = tmp % MOD;
		else
			v = (tmp % MOD + MOD) % MOD;
	}
	ll Val(void) const { return v; }
	ModInt Pow(ll exp) const
	{
		assert(exp >= 0);
		ModInt res = 1;
		ModInt base = *this;
		while (exp)
		{
			if (exp & 1)
				res *= base;
			base *= base;
			exp >>= 1;
		}
		return res;
	}
	ModInt Inv(void) const
	{
		assert(v != 0);
		return Pow(MOD - 2);
	}
	ModInt &operator++()
	{
		++v;
		if (v == MOD)
			v = 0;
		return *this;
	}
	ModInt &operator--()
	{
		if (v == 0)
			v = MOD;
		--v;
		return *this;
	}
	ModInt operator++(int)
	{
		ModInt oldVal = *this;
		++*this;
		return oldVal;
	}
	ModInt operator--(int)
	{
		ModInt oldVal = *this;
		--*this;
		return oldVal;
	}
	ModInt &operator+=(const ModInt &rh)
	{
		v += rh.v;
		if (MOD <= v)
			v -= MOD;
		return *this;
	}
	ModInt &operator-=(const ModInt &rh)
	{
		v -= rh.v;
		if (v < 0)
			v += MOD;
		return *this;
	}
	ModInt &operator*=(const ModInt &rh)
	{
		v *= rh.v;
		v %= MOD;
		return *this;
	}
	ModInt &operator/=(const ModInt &rh) { return *this *= rh.Inv(); }
	ModInt operator+() const { return *this; }
	ModInt operator-() const { return ModInt(0) - *this; }
	friend ModInt operator+(const ModInt &lh, const ModInt &rh)
	{
		ModInt res = lh;
		res += rh;
		return res;
	}
	friend ModInt operator-(const ModInt &lh, const ModInt &rh)
	{
		ModInt res = lh;
		res -= rh;
		return res;
	}
	friend ModInt operator*(const ModInt &lh, const ModInt &rh)
	{
		ModInt res = lh;
		res *= rh;
		return res;
	}
	friend ModInt operator/(const ModInt &lh, const ModInt &rh)
	{
		ModInt res = lh;
		res /= rh;
		return res;
	}
	friend bool operator==(const ModInt &lh, const ModInt &rh) { return lh.v == rh.v; }
	friend bool operator!=(const ModInt &lh, const ModInt &rh) { return lh.v != rh.v; }
	friend std::istream &operator>>(std::istream &is, ModInt &aim)
	{
		ll tmp;
		is >> tmp;
		aim = ModInt(tmp);
		return is;
	}
	friend std::ostream &operator<<(std::ostream &os, const ModInt &aim) { return os << aim.Val(); }

protected:
	ll v;
};
using mint = ModInt<MOD>;
template <typename NODE, ll SZ>
struct SGT
{
#define LS (id << 1)
#define RS (id << 1 | 1)
public:
	ll sz;
	void Init(ll sz)
	{
		this->sz = sz;
		Build(1, 1, sz);
		return;
	}
	void Mdf(ll l, ll r, ll v) { Mdf(l, r, v, 1, 1, sz); }
	NODE Qry(ll l, ll r) { return Qry(l, r, 1, 1, sz); }

protected:
	NODE nd[SZ << 2 | 1];
	void Build(ll id, ll id_l, ll id_r)
	{
		if (id_l == id_r)
		{
			nd[id].Init(id_l);
			return;
		}
		ll id_m = (id_l + id_r) >> 1;
		Build(LS, id_l, id_m);
		Build(RS, id_m + 1, id_r);
		nd[id].PushUp(nd[LS], nd[RS]);
		return;
	}
	void Mdf(ll l, ll r, ll v, ll id, ll id_l, ll id_r)
	{
		if (l <= id_l and id_r <= r)
		{
			nd[id].Mdf(id_l, id_r, v);
			return;
		}
		nd[id].PushDown(id_l, id_r, nd[LS], nd[RS]);
		ll md = (id_l + id_r) >> 1;
		if (l <= md)
			Mdf(l, r, v, LS, id_l, md);
		if (md < r)
			Mdf(l, r, v, RS, md + 1, id_r);
		nd[id].PushUp(nd[LS], nd[RS]);
		return;
	}
	NODE Qry(ll l, ll r, ll id, ll id_l, ll id_r)
	{
		if (l <= id_l and id_r <= r)
			return nd[id];
		nd[id].PushDown(id_l, id_r, nd[LS], nd[RS]);
		NODE res;
		ll md = (id_l + id_r) >> 1;
		if (l <= md and md < r)
			res.PushUp(Qry(l, r, LS, id_l, md), Qry(l, r, RS, md + 1, id_r));
		else if (l <= md)
			return Qry(l, r, LS, id_l, md);
		else if (md < r)
			return Qry(l, r, RS, md + 1, id_r);
		return res;
	}
#undef LS
#undef RS
};
/**************************************************/
ll n, q;
ll a[SZ];

mint c[SZ][21];
mint po[21];

struct NODE
{
	static constexpr ll NUL = 0;

	mint f[21];
	mint res;
	ll lz;

	void Init(ll p)
	{
		f[0] = 1;
		res = 1;
		return;
	}
	void PushUp(const NODE &ls, const NODE &rs)
	{
		FOR(i, 0, 20)
		f[i] = 0;
		FOR(i, 0, 20)
		FOR(j, 0, 20 - i)
		f[i + j] += ls.f[i] * rs.f[j];
		res = 0;
		FOR(i, 0, 20)
		res += f[i];
		return;
	}
	void PushDown(ll id_l, ll id_r, NODE &ls, NODE &rs)
	{
		if (lz == NUL)
			return;
		ll id_m = (id_l + id_r) >> 1;
		ls.Mdf(id_l, id_m, lz);
		rs.Mdf(id_m + 1, id_r, lz);
		lz = NUL;
		return;
	}
	void Mdf(ll id_l, ll id_r, ll v)
	{
		po[0] = 1;
		FOR(i, 1, 20)
		po[i] = po[i - 1] * v;
		ROF(i, std::min(id_r - id_l + 1, 20LL), 0)
		FOR(j, 0, i - 1)
		f[i] += po[i - j] * f[j] * c[id_r - id_l + 1 - j][i - j];
		lz += v;
		res = 0;
		FOR(i, 0, 20)
		res += f[i];
		return;
	}
};

SGT<NODE, SZ> sgt;

void Init(void)
{
	FOR(i, 0, n)
	c[i][0] = 1;

	FOR(i, 0, n)
	FOR(j, 1, i)
	{
		if (j > 20)
			break;
		c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}

	sgt.Init(n);
	FOR(i, 1, n)
	sgt.Mdf(i, i, a[i] - 1);
	return;
}
void Mdf(void)
{
	ll l, r, x;
	FIN(l, r, x);
	sgt.Mdf(l, r, x);
	return;
}
void Qry(void)
{
	ll l, r;
	FIN(l, r);
	auto ans = sgt.Qry(l, r);
	cout << ans.res << EDL;
	return;
}
void Main(void)
{
	FIN(n, q);
	FIN(a, 1, n);

	Init();

	FOR(qi, 1, q)
	{
		ll op;
		FIN(op);
		if (op == 1)
			Mdf();
		else
			Qry();
	}
	return;
}