#include<bits/stdc++.h>
#define inf 2e9
#define eps 1e-6
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define REP(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
const int mod = 998244353;
#define N 110
#define M 40010
int n, q;
struct node
{
	int s[3], len;
	node() {FOR(i, 0, 2)s[i] = 0; len = 0;}
} t[N * M], s[N];
int ls[N * M], rs[N * M], tag[N * M];
int rt, tot;
int inv2, inv6;
int a[N];
bitset<N>B1[N], B2[N];
int ksm(int a, int b)
{
	int ans = 1;
	while (b) {if (b & 1)ans = 1LL * ans * a % mod; b >>= 1; a = 1LL * a * a % mod;}
	return ans;
}
int C3(int n) {return 1LL * n * (n + mod - 1) % mod * (n + mod - 2) % mod * inv6 % mod;}
int C2(int n) {return 1LL * n * (n + mod - 1) % mod * inv2 % mod;}
node operator +(const node a, const node b)
{
	node c; c.len = (a.len + b.len) % mod;
	c.s[0] = (1LL * a.s[0] + b.s[0]) % mod;
	c.s[1] = (1LL * a.s[1] + b.s[1] + 1LL * a.s[0] * b.s[0] % mod) % mod;
	c.s[2] = (1LL * a.s[2] + b.s[2] + 1LL * a.s[1] * b.s[0] % mod + 1LL * a.s[0] * b.s[1] % mod) % mod;
	return c;
}
node operator +(const node a, const int w)
{
	node c; c.len = a.len;
	c.s[0] = (1LL * a.s[0] + 1LL * a.len * w % mod) % mod;
	c.s[1] = (1LL * a.s[1] + 1LL * a.s[0] * (a.len + mod - 1) % mod * w % mod + 1LL * C2(a.len) * w % mod * w % mod) % mod;
	c.s[2] = (1LL * a.s[2] + 1LL * a.s[1] * (a.len + mod - 2) % mod * w % mod + 1LL * a.s[0] * C2(a.len - 1) % mod * w % mod * w % mod + 1LL * C3(a.len) * w % mod * w % mod * w % mod) % mod;
	return c;
}
char S[N];
bitset<N> Read()
{
	bitset<N>ans;
	scanf("%s", S + 1);
	FOR(i, 1, n)ans[i] = S[i] - '0';
	return ans;
}
void push(int x, int w) {t[x] = t[x] + w; tag[x] = (tag[x] + w) % mod;}
void pushdown(int x, int S, int dep)
{
	if (!ls[x]) {ls[x] = ++ tot; t[ls[x]] = s[dep + 1] + S;}
	if (!rs[x]) {rs[x] = ++ tot; t[rs[x]] = s[dep + 1] + ((a[dep] + S) % mod);}
	if (tag[x]) {push(ls[x], tag[x]); push(rs[x], tag[x]); tag[x] = 0;}
}
void pushup(int x) {t[x] = t[ls[x]] + t[rs[x]];}
void print(bitset<N>L, bitset<N> R, int dep)
{
	cout << "MODIFY:" << dep << endl;
	FOR(i, 1, n)cout << L[i]; cout << endl;
	FOR(i, 1, n)cout << R[i]; cout << endl;
}
void add(int &x, const bitset<N>ql, const bitset<N>qr, int dep, int S, int w)
{
	if (!x) {x = ++tot; t[tot] = s[dep] + S;}
	if (((ql & B1[dep]) == 0) && ((qr & B1[dep]) == B1[dep])) {/*print(ql, qr, dep); cout << "???:" << t[x].len << " " << t[x].s[0] << ' ' << t[x].s[1] << ' ' << t[x].s[2] << endl;;*/ push(x, w); return ;}
	pushdown(x, S, dep);
	if (qr[dep] == 0)add(ls[x], ql, qr, dep + 1, S, w);
	else if (ql[dep] == 1)add(rs[x], ql, qr, dep + 1, (S + a[dep]) % mod, w);
	else
	{
		add(ls[x], ql, B1[dep + 1], dep + 1, S, w);
		add(rs[x], 0, qr, dep + 1, (S + a[dep]) % mod, w);
	}
	// print(ql, qr, dep);
	pushup(x);
	// cout << "???:" << t[x].len << " " << t[x].s[0] << ' ' << t[x].s[1] << ' ' << t[x].s[2] << endl;;
}
int qry(int &x, const bitset<N>ql, const bitset<N>qr, int dep, int S)
{
	if (!x) {x = ++tot; t[tot] = s[dep] + S;}
	if (((ql & B1[dep]) == 0) && ((qr & B1[dep]) == B1[dep])) return t[x].s[2];
	pushdown(x, S, dep);
	if (qr[dep] == 0)return qry(ls[x], ql, qr, dep + 1, S);
	else if (ql[dep] == 1)return qry(rs[x], ql, qr, dep + 1, (S + a[dep]) % mod);
	else
	{
		int s = 0;
		s = (s + qry(ls[x], ql, B1[dep + 1], dep + 1, S)) % mod;
		s = (s + qry(rs[x], 0, qr, dep + 1, (S + a[dep]) % mod)) % mod;
		return s;

	}
}
int main()
{
	// freopen("C.in", "r", stdin);
	// freopen("C.out", "w", stdout);
	inv2 = ksm(2, mod - 2);
	inv6 = ksm(6, mod - 2);
	n = read(), q = read();
	FOR(i, 1, n)
	{
		B2[i] = B2[i - 1];
		B2[i][i] = 1;
	}
	REP(i, n, 1)
	{
		B1[i] = B1[i + 1];
		B1[i][i] = 1;
	}
	FOR(i, 1, n)a[i] = read() % mod;
	reverse(a + 1, a + n + 1);
	s[n + 1].len = 1;
	REP(i, n, 1)
	{
		s[i] = s[i + 1] + (s[i + 1] + a[i]);
	}
	// FOR(i, 1, n)
	// cout << s[i].len << ' ' << s[i].s[0] << ' ' << s[i].s[1] << ' ' << s[i].s[2] << endl;
	while (q --)
	{
		int op = read(); bitset<N>L = Read(), R = Read();
		if (op == 1)
		{
			int w = read();
			add(rt, L, R, 1, 0, w);
		}
		else cout << qry(rt, L, R, 1, 0) << '\n';
	}
	return 0;
}
/*
3 3
1 2 4
2 000 111
1 010 101 1
2 000 111
*/
/*
2 2
1 1
2 00 10
2 00 11
*/