class SegmentTree: def __init__(self, n, e): n2 = 1 while n2 < n: n2 *= 2 self.n = n2 self.data = [e] * (n2 * 2) def build(self, a): for i, x in enumerate(a): self.data[i + self.n] = x for i in range(self.n - 1, 0, -1): self.data[i] = self.data[i * 2] + self.data[i * 2 + 1] def update(self, i, x): k = i + self.n self.data[k] = x while k > 1: k //= 2 self.data[k] = self.data[k * 2] + self.data[k * 2 + 1] def query(self, l, r, ls, rs): l += self.n r += self.n while l < r: if l & 1: ls += self.data[l] l += 1 if r & 1: r -= 1 rs = self.data[r] + rs l //= 2 r //= 2 return ls + rs MOD = 998244353 class Vec: def __init__(self, a): self.a = a def __add__(self, other): if isinstance(other, Matrix): result = self.a[:] for i in range(len(self.a)): for j in range(i): result[j] += self.a[i] * other.a[i * (i - 1) // 2 + j] for i in range(len(self.a)): result[i] %= MOD return Vec(result) return sum(x * y for x, y in zip(self.a, other.a)) % MOD class Matrix: size = 6 def __init__(self, a): self.a = a def __add__(self, other): if isinstance(other, Vec): result = other.a[:] for i in range(self.size): for j in range(i): result[i] += self.a[i * (i - 1) // 2 + j] * other.a[j] result[i] %= MOD return Vec(result) result = [i + j for i, j in zip(self.a, other.a)] for i in range(self.size): for j in range(i): ij = i * (i - 1) // 2 + j for k in range(j + 1, i): result[ij] += self.a[i * (i - 1) // 2 + k] * other.a[k * (k - 1) // 2 + j] result[ij] %= MOD return Matrix(result) node = [ Matrix([1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1]), Matrix([1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1]), ] identity = Matrix([0 for _ in range(15)]) n, q = map(int, input().split()) s = input() s_seq = [int(x) for x in s] st = SegmentTree(n, identity) st.build([node[x] for x in s_seq]) for _ in range(q): t, *args = map(int, input().split()) if t == 1: i = args[0] - 1 s_seq[i] = 1 - s_seq[i] st.update(i, node[s_seq[i]]) else: l, r = args ans = st.query(l - 1, r, Vec([0, 0, 0, 0, 0, 1]), Vec([1, 0, 0, 0, 0, 0])) print(ans)