import array, sys input = sys.stdin.readline 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 other.a is None: return self if self.a is None: return other if isinstance(other, Matrix): result = self.a[:] result[0] += self.a[1] * other.a[0] result[0] += self.a[2] * other.a[1] result[1] += self.a[2] * other.a[2] result[0] += self.a[3] * other.a[3] result[1] += self.a[3] * other.a[4] result[2] += self.a[3] * other.a[5] result[0] += self.a[4] * other.a[6] result[1] += self.a[4] * other.a[7] result[2] += self.a[4] * other.a[8] result[3] += self.a[4] * other.a[9] result[0] += self.a[5] * other.a[10] result[1] += self.a[5] * other.a[11] result[2] += self.a[5] * other.a[12] result[3] += self.a[5] * other.a[13] result[4] += self.a[5] * other.a[14] 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 other.a is None: return self if self.a is None: return other if isinstance(other, Vec): result = other.a[:] result[1] += self.a[0] * other.a[0] result[2] += self.a[1] * other.a[0] result[2] += self.a[2] * other.a[1] result[3] += self.a[3] * other.a[0] result[3] += self.a[4] * other.a[1] result[3] += self.a[5] * other.a[2] result[4] += self.a[6] * other.a[0] result[4] += self.a[7] * other.a[1] result[4] += self.a[8] * other.a[2] result[4] += self.a[9] * other.a[3] result[5] += self.a[10] * other.a[0] result[5] += self.a[11] * other.a[1] result[5] += self.a[12] * other.a[2] result[5] += self.a[13] * other.a[3] result[5] += self.a[14] * other.a[4] for i in range(self.size): result[i] %= MOD return Vec(result) result = array.array('l', [i + j for i, j in zip(self.a, other.a)]) result[1] += self.a[2] * other.a[0] result[3] += self.a[4] * other.a[0] result[3] += self.a[5] * other.a[1] result[4] += self.a[5] * other.a[2] result[6] += self.a[7] * other.a[0] result[6] += self.a[8] * other.a[1] result[6] += self.a[9] * other.a[3] result[7] += self.a[8] * other.a[2] result[7] += self.a[9] * other.a[4] result[8] += self.a[9] * other.a[5] result[10] += self.a[11] * other.a[0] result[10] += self.a[12] * other.a[1] result[10] += self.a[13] * other.a[3] result[10] += self.a[14] * other.a[6] result[11] += self.a[12] * other.a[2] result[11] += self.a[13] * other.a[4] result[11] += self.a[14] * other.a[7] result[12] += self.a[13] * other.a[5] result[12] += self.a[14] * other.a[8] result[13] += self.a[14] * other.a[9] for idx, _ in enumerate(result): result[idx] %= MOD return Matrix(result) node = [ Matrix(array.array('l', [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1])), Matrix(array.array('l', [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1])), ] identity = Matrix(None) n, q = map(int, input().split()) s = input().strip() 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(array.array('l', [0, 0, 0, 0, 0, 1])), Vec(array.array('l', [1, 0, 0, 0, 0, 0]))) print(ans)