import strutils, sequtils, deques type stdinReader = object buf: Deque[string] func newStdinReader(): stdinReader = result = stdinReader(buf: initDeque[string]()) proc readString(sr: var stdinReader): string = if sr.buf.len == 0: sr.buf = stdin.readLine.split.toDeque sr.buf.popFirst proc readInt(sr: var stdinReader): int = readString(sr).parseInt type SegmentTree[T] = object n: int data: seq[T] e: T func init[T](n: int, e: T): SegmentTree[T] = var n2 = 1 while n2 < n: n2 *= 2 SegmentTree[T](n: n2, data: newSeqWith[T](n2 * 2, e), e: e) proc build[T](st: var SegmentTree[T], a: seq[T]) = for i, x in a: st.data[i + st.n] = x for i in countdown(st.n - 1, 1): st.data[i] = st.data[i * 2] + st.data[i * 2 + 1] proc update[T](st: var SegmentTree[T], i: int, x: T) = var k = i + st.n st.data[k] = x while k > 1: k = k div 2 st.data[k] = st.data[k * 2] + st.data[k * 2 + 1] func query[T](st: SegmentTree[T], l: int, r: int): T = var l = l + st.n r = r + st.n var ls = st.e rs = st.e while l < r: if (l and 1) == 1: ls = ls + st.data[l] l += 1 if (r and 1) == 1: r -= 1 rs = st.data[r] + rs l = l div 2 r = r div 2 ls + rs const MOD = 998244353 type Matrix = array[6, array[6, int]] func `+`(a, b: Matrix): Matrix = for i in 0 ..< a.len: for j in 0..i: for k in 0..i: result[i][j] = (result[i][j] + a[i][k] * b[k][j]) mod MOD let node: array[2, Matrix] = [ [ [1, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 1, 1, 1], ], [ [1, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [1, 1, 0, 1, 0, 0], [0, 0, 1, 0, 1, 0], [0, 0, 1, 0, 1, 1], ] ] let identity: Matrix = [ [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1], ] var reader = newStdinReader() let (n, q) = (reader.readInt, reader.readInt) let s = reader.readString var sSeq = s.mapIt(int(it) - int('0')) var st = init[Matrix](n, identity) st.build(sSeq.mapIt(node[it])) for _ in 0..