# {{{ header
when not declared ATCODER_CHAEMON_HEADER_HPP:
  const ATCODER_CHAEMON_HEADER_HPP* = 1
  {.hints:off checks:off warnings:off assertions:on optimization:speed.}
  import std/algorithm as algorithm_lib
  import std/sequtils as sequtils_lib
  import std/tables as tables_lib
  import std/macros as macros_lib
  import std/math as math_lib
  import std/sets as sets_lib
  import std/strutils as strutils_lib
  import std/strformat as strformat_lib
  import std/sugar as sugar_lib
  
  import streams
  proc scanf*(formatstr: cstring){.header: "<stdio.h>", varargs.}
  #proc getchar(): char {.header: "<stdio.h>", varargs.}
  proc nextInt*(): int = scanf("%lld",addr result)
  proc nextFloat*(): float = scanf("%lf",addr result)
  proc nextString*[F](f:F): string =
    var get = false
    result = ""
    while true:
  #    let c = getchar()
      let c = f.readChar
      if c.int > ' '.int:
        get = true
        result.add(c)
      elif get: return
  proc nextInt*[F](f:F): int = parseInt(f.nextString)
  proc nextFloat*[F](f:F): float = parseFloat(f.nextString)
  proc nextString*():string = stdin.nextString()
  
  template `max=`*(x,y:typed):void = x = max(x,y)
  template `min=`*(x,y:typed):void = x = min(x,y)
  template inf*(T): untyped = 
    when T is SomeFloat: T(Inf)
    elif T is SomeInteger: ((T(1) shl T(sizeof(T)*8-2)) - (T(1) shl T(sizeof(T)*4-1)))
    else: assert(false)
  
  proc discardableId*[T](x: T): T {.discardable.} =
    return x
  
  macro `:=`*(x, y: untyped): untyped =
    var strBody = ""
    if x.kind == nnkPar:
      for i,xi in x:
        strBody &= fmt"""
{xi.repr} := {y[i].repr}
"""
    else:
      strBody &= fmt"""
when declaredInScope({x.repr}):
  {x.repr} = {y.repr}
else:
  var {x.repr} = {y.repr}
"""
    strBody &= fmt"discardableId({x.repr})"
    parseStmt(strBody)
  
  
  proc toStr*[T](v:T):string =
    proc `$`[T](v:seq[T]):string =
      v.mapIt($it).join(" ")
    return $v
  
  proc print0*(x: varargs[string, toStr]; sep:string):string{.discardable.} =
    result = ""
    for i,v in x:
      if i != 0: addSep(result, sep = sep)
      add(result, v)
    result.add("\n")
    stdout.write result
  
  var print*:proc(x: varargs[string, toStr])
  print = proc(x: varargs[string, toStr]) =
    discard print0(@x, sep = " ")
  
  template makeSeq*(x:int; init):auto =
    when init is typedesc: newSeq[init](x)
    else: newSeqWith(x, init)
  
  macro Seq*(lens: varargs[int]; init):untyped =
    var a = fmt"{init.repr}"
    for i in countdown(lens.len - 1, 0): a = fmt"makeSeq({lens[i].repr}, {a})"
    parseStmt(fmt"""  
block:
  {a}""")
  
  template makeArray*(x:int; init):auto =
    var v:array[x, init.type]
    when init isnot typedesc:
      for a in v.mitems: a = init
    v
  
  macro Array*(lens: varargs[typed], init):untyped =
    var a = fmt"{init.repr}"
    for i in countdown(lens.len - 1, 0):
      a = fmt"makeArray({lens[i].repr}, {a})"
    parseStmt(fmt"""
block:
  {a}""")
# }}}
when not declared ATCODER_MODINT_HPP:
  const ATCODER_MODINT_HPP* = 1

  type
    StaticModInt*[M: static[int]] = distinct uint32
  type
    DynamicModInt*[T: static[int]] = distinct uint32
  
  type ModInt* = StaticModInt or DynamicModInt

  when not declared ATCODER_INTERNAL_MATH_HPP:
    const ATCODER_INTERNAL_MATH_HPP* = 1
    import std/math
  
    # Fast moduler by barrett reduction
    # Reference: https:#en.wikipedia.org/wiki/Barrett_reduction
    # NOTE: reconsider after Ice Lake
    type Barrett* = object
      m*, im:uint
  
    # @param m `1 <= m`
    proc initBarrett*(m:uint):auto = Barrett(m:m, im:(0'u - 1'u) div m + 1)
  
    # @return m
    proc umod*(self: Barrett):uint =
      self.m
  
    {.emit: """
  inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b){
    return (unsigned long long)(((unsigned __int128)(a)*b) >> 64);
  }
  """.}
    proc calc_mul*(a,b:culonglong):culonglong {.importcpp: "calc_mul(#,#)", nodecl.}
    # @param a `0 <= a < m`
    # @param b `0 <= b < m`
    # @return `a * b % m`
    proc mul*(self: Barrett, a:uint, b:uint):uint =
      # [1] m = 1
      # a = b = im = 0, so okay
  
      # [2] m >= 2
      # im = ceil(2^64 / m)
      # -> im * m = 2^64 + r (0 <= r < m)
      # let z = a*b = c*m + d (0 <= c, d < m)
      # a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
      # c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
      # ((ab * im) >> 64) == c or c + 1
      let z = a * b
      #  #ifdef _MSC_VER
      #      unsigned long long x;
      #      _umul128(z, im, &x);
      #  #else
      ##TODO
      #      unsigned long long x =
      #        (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      #  #endif
      let x = calc_mul(z.culonglong, self.im.culonglong).uint
      var v = z - x * self.m
      if self.m <= v: v += self.m
      return v
  
    # @param n `0 <= n`
    # @param m `1 <= m`
    # @return `(x ** n) % m`
    proc pow_mod_constexpr*(x,n,m:int):int {.compileTime.} =
      if m == 1: return 0
      var
        r = 1
        y = floorMod(x, m)
        n = n
      while n != 0:
        if (n and 1) != 0: r = (r * y) mod m
        y = (y * y) mod m
        n = n shr 1
      return r.int
    
    # Reference:
    # M. Forisek and J. Jancina,
    # Fast Primality Testing for Integers That Fit into a Machine Word
    # @param n `0 <= n`
    proc is_prime_constexpr*(n:int):bool {.compileTime.} =
      if n <= 1: return false
      if n == 2 or n == 7 or n == 61: return true
      if n mod 2 == 0: return false
      var d = n - 1
      while d mod 2 == 0: d = d div 2
      for a in [2, 7, 61]:
        var
          t = d
          y = pow_mod_constexpr(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
          y = y * y mod n
          t =  t shl 1
        if y != n - 1 and t mod 2 == 0:
          return false
      return true
    proc is_prime*[n:static[int]]():bool {.compileTime.} = is_prime_constexpr(n)
  #  
  #  # @param b `1 <= b`
  #  # @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
    proc inv_gcd*(a, b:int):(int,int) =
      var a = floorMod(a, b)
      if a == 0: return (b, 0)
    
      # Contracts:
      # [1] s - m0 * a = 0 (mod b)
      # [2] t - m1 * a = 0 (mod b)
      # [3] s * |m1| + t * |m0| <= b
      var
        s = b
        t = a
        m0 = 0
        m1 = 1
    
      while t != 0:
        var u = s div t
        s -= t * u;
        m0 -= m1 * u;  # |m1 * u| <= |m1| * s <= b
    
        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b
    
        var tmp = s
        s = t;t = tmp;
        tmp = m0;m0 = m1;m1 = tmp;
      # by [3]: |m0| <= b/g
      # by g != b: |m0| < b/g
      if m0 < 0: m0 += b div s
      return (s, m0)
  
    # Compile time primitive root
    # @param m must be prime
    # @return primitive root (and minimum in now)
    proc primitive_root_constexpr*(m:int):int {.compileTime.} =
      if m == 2: return 1
      if m == 167772161: return 3
      if m == 469762049: return 3
      if m == 754974721: return 11
      if m == 998244353: return 3
      var divs:array[20, int]
      divs[0] = 2
      var cnt = 1
      var x = (m - 1) div 2
      while x mod 2 == 0: x = x div 2
      var i = 3
      while i * i <= x:
        if x mod i == 0:
          divs[cnt] = i
          cnt.inc
          while x mod i == 0:
            x = x div i
        i += 2
      if x > 1:
        divs[cnt] = x
        cnt.inc
      var g = 2
      while true:
        var ok = true
        for i in 0..<cnt:
          if pow_mod_constexpr(g, (m - 1) div divs[i], m) == 1:
            ok = false
            break
        if ok: return g
        g.inc
    proc primitive_root*[m:static[int]]():auto {.compileTime.} =
      primitive_root_constexpr(m)
    discard

  proc getBarrett*[T:static[int]](t:typedesc[DynamicModInt[T]], set = false, M:SomeInteger = 0.uint32):ptr Barrett =
    var Barrett_of_DynamicModInt {.global.} :Barrett
    return Barrett_of_DynamicModInt.addr
  proc getMod*[T:static[int]](t:typedesc[DynamicModInt[T]]):uint32 {.inline.} =
    (t.getBarrett)[].m.uint32
  proc setMod*[T:static[int]](t:typedesc[DynamicModInt[T]], M:SomeInteger){.used inline.} =
    (t.getBarrett)[] = initBarrett(M.uint)

  proc `$`*(m: ModInt): string {.inline.} =
    $m.int

  template umod*[T:ModInt](self: typedesc[T]):uint32 =
    when T is StaticModInt:
      T.M
    elif T is DynamicModInt:
      T.getMod()
    else:
      static: assert false
  template umod*[T:ModInt](self: T):uint32 = self.type.umod

  proc init*[T:ModInt](t:typedesc[T], v: SomeInteger or T): auto {.inline.} =
    when v is T: return v
    else:
      var v = v.int
      if 0 <= v:
        if v < T.umod.int: return T(v.uint32)
        else: return T((v mod T.umod.int).uint32)
      else:
        v = v mod T.umod.int
        if v < 0: v += T.umod.int
        return T(v.uint32)
  template initModInt*(v: SomeInteger or ModInt; M: static[int] = 1_000_000_007): auto =
    StaticModInt[M].init(v)

# TODO
#  converter toModInt[M:static[int]](n:SomeInteger):ModInt[M] {.inline.}= initModInt(n, M)

  proc initModIntRaw*(v: SomeInteger; M: static[int] = 1_000_000_007): auto {.inline.} =
    ModInt[M](v.uint32)

  proc inv*[T](v:T):T {.inline.} =
    var
      a = T.init(v).int
      b = T.umod.int
      u = 1
      v = 0
    while b > 0:
      let t = a div b
      a -= t * b;swap(a, b)
      u -= t * v;swap(u, v)
    return T.init(u)

  proc val*(m: ModInt): int {.inline.} =
    int(m)

  proc `-`*[T:ModInt](m: T): T {.inline.} =
    if int(m) == 0: return m
    else: return T(m.umod() - uint32(m))

  template generateDefinitions(name, l, r, body: untyped): untyped {.dirty.} =
    proc name*[T:ModInt](l: T; r: T): auto {.inline.} =
      body
    proc name*[T:ModInt](l: SomeInteger; r: T): auto {.inline.} =
      body
    proc name*[T:ModInt](l: T; r: SomeInteger): auto {.inline.} =
      body

  proc `+=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =
    uint32(m) += T.init(n).uint32
    if uint32(m) >= T.umod: uint32(m) -= T.umod

  proc `-=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =
    uint32(m) -= T.init(n).uint32
    if uint32(m) >= T.umod: uint32(m) += T.umod

  proc `*=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =
    when T is StaticModInt:
      uint32(m) = (uint(m) * T.init(n).uint mod T.umod()).uint32
    elif T is DynamicModInt:
      uint32(m) = T.getBarrett[].mul(uint(m), T.init(n).uint).uint32
    else:
      static: assert false

  proc `/=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =
    uint32(m) = (uint(m) * T.init(n).inv().uint mod T.umod).uint32

  generateDefinitions(`+`, m, n):
    result = T.init(m)
    result += n

  generateDefinitions(`-`, m, n):
    result = T.init(m)
    result -= n

  generateDefinitions(`*`, m, n):
    result = T.init(m)
    result *= n

  generateDefinitions(`/`, m, n):
    result = T.init(m)
    result /= n

  proc `==`*[T:ModInt](m: T; n: SomeInteger | T): bool {.inline.} =
    int(m) == T.init(n).int

  proc inc*[T:ModInt](m: var T) {.inline.} =
    uint32(m).inc
    if m == T.umod:
      uint32(m) = 0

  proc dec*[T:ModInt](m: var T) {.inline.} =
    if m == 0:
      uint32(m) = T.umod - 1
    else:
      uint32(m).dec

  proc pow*[T:ModInt](m: T; p: SomeInteger): T {.inline.} =
    var
      p = p.int
      m = m
    uint32(result) = 1
    while p > 0:
      if (p and 1) == 1:
        result *= m
      m *= m
      p = p shr 1

  type modint998244353* = StaticModInt[998244353]
  type modint1000000007* = StaticModInt[1000000007]
  type modint* = DynamicModInt[-1]

const MOD = 998244353
var N:int
var K:int
var L:seq[int]
var R:seq[int]

# input part {{{
proc main()
block:
  N = nextInt()
  K = nextInt()
  L = newSeqWith(K, 0)
  R = newSeqWith(K, 0)
  for i in 0..<K:
    L[i] = nextInt()
    R[i] = nextInt()
#}}}

# FormalPowerSeries {{{
when not defined ATCODER_FORMAL_POWER_SERIES:
  const ATCODER_FORMAL_POWER_SERIES* = 1
  
#  import std/sequtils, std/strformat, std/options, std/macros, std/tables
  
#  import atcoder/convolution
#  import atcoder/extra/math/element_concepts
#  import atcoder/extra/math/internal_fft
#  import atcoder/extra/math/combination

  type FormalPowerSeries*[T:ModInt] = seq[T]
  type SparseFormalPowerSeries*[T:ModInt] = seq[(int, T)]

  template initFormalPowerSeries*[T:ModInt](data: typed):FormalPowerSeries[T] =
    when data is FormalPowerSeries[T]: data
    elif data is int: FormalPowerSeries[T](newSeq[T](data))
    elif data is seq or data is array:
      var v = newSeq[T](data.len)
      for i, it in data:
        v[i] = T.init(it)
      v
#      data.mapIt(T(it))
    else:
      static: assert false
  template init*[T](self:typedesc[FormalPowerSeries[T]], data:typed):auto = initFormalPowerSeries[T](data)
 
  macro revise(a, b) =
    parseStmt(fmt"""let {a.repr} = if {a.repr} == -1: {b.repr} else: {a.repr}""")
  # sqrt {{{
  type
    SQRT[T] = proc(t:T):Option[T]
  
  proc sqrtSub[T](self:FormalPowerSeries[T], update: bool, f:SQRT[T]):(bool, SQRT[T]){.discardable.} =
    var is_set{.global.} = false
    var sqr{.global.}:SQRT[T] = nil
    if update:
      is_set = true
      sqr = f
    return (is_set, sqr)
  proc isSetSqrt[T](self:FormalPowerSeries[T]):bool = return self.sqrtSub(false, nil)[0]
  proc setSqrt[T](self:FormalPowerSeries[T], f: SQRT[T]):SQRT[T]{.discardable.} = return self.sqrtSub(true, f)[1]
  proc getSqrt[T](self:FormalPowerSeries[T]):SQRT[T]{.discardable.} = return self.sqrtSub(false, nil)[1]
  #}}}
  
  proc shrink*[T](self: var FormalPowerSeries[T]) =
    while self.len > 0 and self[^1] == 0: discard self.pop()
 
  # operators +=, -=, *=, mod=, -, /= {{{
  proc `+=`*(self: var FormalPowerSeries, r:FormalPowerSeries) =
    if r.len > self.len: self.setlen(r.len)
    for i in 0..<r.len: self[i] += r[i]
  proc `+=`*[T](self: var FormalPowerSeries[T], r:T) =
    if self.len == 0: self.setlen(1)
    self[0] += r
  
  proc `-=`*[T](self: var FormalPowerSeries[T], r:FormalPowerSeries[T]) =
    if r.len > self.len: self.setlen(r.len)
    for i in 0..<r.len: self[i] -= r[i]
#    self.shrink()
  proc `-=`*[T](self: var FormalPowerSeries[T], r:T) =
    if self.len == 0: self.setlen(1)
    self[0] -= r
#    self.shrink()

  proc `*=`*[T](self: var FormalPowerSeries[T], v:T) = self.applyIt(it * v)

  proc multRaw*[T](a:FormalPowerSeries[T], b:SparseFormalPowerSeries[T], deg = -1):FormalPowerSeries[T] =
    var deg = deg
    if deg == -1:
      var bdeg = 0
      for p in b: bdeg = max(bdeg, p[0])
      deg = a.len + bdeg
    result = initFormalPowerSeries[T](deg)
    for i in 0..<a.len:
      for (j, c) in b:
        let k = i + j
        if k < deg: result[k] += a[i] * c
  proc multRaw*[T](a, b:SparseFormalPowerSeries[T], deg = -1):SparseFormalPowerSeries[T] =
    var r = initTable[int,T]()
    for (i, c0) in a:
      for (j, c1) in b:
        let k = i + j
        if deg != -1 and k >= deg: continue
        if k notin r: r[k] = T(0)
        r[k] += c0 * c1
    return toSeq(r.pairs)


  proc `*=`*[T](self: var FormalPowerSeries[T],  r: FormalPowerSeries[T]) =
    if self.len == 0 or r.len == 0:
      self.setlen(0)
    else:
      when T is ModInt:
        when T is StaticModInt and T.isGoodMod:
          self = convolution(seq[T](self), seq[T](r))
        else:
          static: assert false
      else:
        var res = initFormalPowerSeries[T](self.len + r.len - 1)
        for i in 0..<self.len:
          for j in 0..<r.len:
            res += self[i] * r[j]
        swap(self, res)
  
  proc `mod=`*[T](self: var FormalPowerSeries[T], r:FormalPowerSeries[T]) = self -= self div r * r
  
  proc `-`*[T](self: FormalPowerSeries[T]):FormalPowerSeries[T] =
    var ret = self
    ret.applyIt(-it)
    return ret
  proc `/=`*[T](self: var FormalPowerSeries[T], v:T) = self.applyIt(it / v)
  #}}}

  proc rev*[T](self: FormalPowerSeries[T], deg = -1):auto =
    result = self
    if deg != -1: result.setlen(deg)
    result.reverse
  
  proc pre*[T](self: FormalPowerSeries[T], sz:int):auto =
    result = self
    result.setlen(min(self.len, sz))
  
  proc `shr`*[T](self: FormalPowerSeries[T], sz:int):auto =
    if self.len <= sz: return initFormalPowerSeries[T](0)
    result = self
    if sz >= 1: result.delete(0, sz - 1)
  proc `shl`*[T](self: FormalPowerSeries[T], sz:int):auto =
    result = initFormalPowerSeries[T](sz)
    result = result & self
  
  proc diff*[T](self: FormalPowerSeries[T]):auto =
    let n = self.len
    result = initFormalPowerSeries[T](max(0, n - 1))
    for i in 1..<n:
      result[i - 1] = self[i] * T(i)
  
  proc integral*[T](self: FormalPowerSeries[T]):auto =
    let n = self.len
    result = initFormalPowerSeries[T](n + 1)
    result[0] = T(0)
    for i in 0..<n: result[i + 1] = self[i] / T(i + 1)
  
  # F(0) must not be 0
  proc inv*[T](self: FormalPowerSeries[T], deg = -1):auto =
    assert(self[0] != 0)
    deg.revise(self.len)
    when T is ModInt:
      proc invFast[T](self: FormalPowerSeries[T]):auto =
        assert(self[0] != 0)
        let n = self.len
        var res = initFormalPowerSeries[T](1)
        res[0] = T(1) / self[0]
        var d = 1
        while d < n:
          var f, g = initFormalPowerSeries[T](2 * d)
          for j in 0..<min(n, 2 * d): f[j] = self[j]
          for j in 0..<d: g[j] = res[j]
          let g1 = fft(g)
          f = ifft(dot(fft(f), g1))
          for j in 0..<d:
            f[j] = T(0)
            f[j + d] = -f[j + d]
          f = ifft(dot(fft(f), g1))
          f[0..<d] = res[0..<d]
          res = f
          d = d shl 1
        return res.pre(n)
      var ret = self
      ret.setlen(deg)
      return ret.invFast()
    else:
      var ret = initFormalPowerSeries[T](1)
      ret[0] = T(1) / self[0]
      var i = 1
      while i < deg:
        ret = (ret + ret - ret * ret * self.pre(i shl 1)).pre(i shl 1)
        i = i shl 1
      return ret.pre(deg)
  
  proc `div=`*[T](self: var FormalPowerSeries[T], r: FormalPowerSeries[T]) =
    if self.len < r.len:
      self.setlen(0)
    else:
      let n = self.len - r.len + 1
      self = (self.rev().pre(n) * r.rev().inv(n)).pre(n).rev(n)
  
  template toFormalPowerSeries[T](f:FormalPowerSeries[T] or T or SomeNumber):auto =
    when f is SomeNumber or f is T: initFormalPowerSeries[T](@[T(f)])
    else: initFormalPowerSeries[T](f)

#  template generateDefinitionsFormalPowerSeries(name, l, r, body: untyped): untyped {.dirty.} =
#    proc name*[T:ModInt](l: FormalPowerSeries[T]; r: FormalPowerSeries[T]): auto {.inline.} =
#      body
#    proc name*[T:ModInt](l: SomeInteger or T; r: FormalPowerSeries[T]): auto {.inline.} =
#      body
#    proc name*[T:ModInt](l: FormalPowerSeries[T]; r: SomeInteger or T): auto {.inline.} =
#      body
#  generateDefinitionsFormalPowerSeries(`+`, l, r):
#    result = toFormalPowerSeries[T](l)
#    result += r
#  generateDefinitionsFormalPowerSeries(`-`, l, r):
#    result = toFormalPowerSeries[T](l)
#    result -= r
#  generateDefinitionsFormalPowerSeries(`*`, l, r):
#    result = toFormalPowerSeries[T](l)
#    result *= r


  # operators +, -, *, div, mod {{{
  macro declareOp(op) =
    fmt"""proc `{op}`*[T](self:FormalPowerSeries[T];r:FormalPowerSeries[T] or T):FormalPowerSeries[T] = result = self;result {op}= r
proc `{op}`*[T](self: not FormalPowerSeries, r:FormalPowerSeries[T]):FormalPowerSeries[T] = result = initFormalPowerSeries[T](@[T(self)]);result {op}= r""".parseStmt
  
  declareOp(`+`)
  declareOp(`-`)
  declareOp(`*`)
  declareOp(`/`)
  
  proc `div`*[T](self, r:FormalPowerSeries[T]):FormalPowerSeries[T] = result = self;result.`div=` (r)
  proc `mod`*[T](self, r:FormalPowerSeries[T]):FormalPowerSeries[T] = result = self;result.`mod=` (r)
  # }}}
  
  # F(0) must be 1
  proc log*[T](self:FormalPowerSeries[T], deg = -1):auto =
    assert self[0] == T(1)
    deg.revise(self.len)
    return (self.diff() * self.inv(deg)).pre(deg - 1).integral()
  
  proc sqrt*[T](self: FormalPowerSeries[T], deg = -1):auto =
    let n = self.len
    deg.revise(n)
    if self[0] == 0:
      for i in 1..<n:
        if self[i] != 0:
          if (i and 1) > 0: return FormalPowerSeries[T].none
          if deg - i div 2 <= 0: break
          var opt = (self shr i).sqrt(deg - i div 2)
          if not opt.isSome: return FormalPowerSeries[T].none
          var ret = opt.get shl (i div 2)
          if ret.len < deg: ret.setlen(deg)
          return ret.some
      return initFormalPowerSeries[T](deg).some
  
    var ret:FormalPowerSeries[T]
    if self.isSetSqrt:
      let opt = self.getSqrt()(self[0])
      if not opt.isSome: return FormalPowerSeries[T].none
      ret = initFormalPowerSeries[T](@[T(opt.get)])
    else:
      assert(self[0] == 1)
      ret = initFormalPowerSeries[T](@[T(1)])
  
    let inv2 = T(1) / T(2)
    var i = 1
    while i < deg:
      ret = (ret + self.pre(i shl 1) * ret.inv(i shl 1)) * inv2
      i = i shl 1
    return ret.pre(deg).some
  
#  import typetraits
  
  # F(0) must be 0
  proc exp*[T](self: FormalPowerSeries[T], deg = -1):auto =
    assert self[0] == 0
    deg.revise(self.len)
    when T is ModInt:
      proc onlineConvolutionExp[T](self, conv_coeff:FormalPowerSeries[T]):auto =
        let n = conv_coeff.len
        assert((n and (n - 1)) == 0)
        type FFTType = fft(initFormalPowerSeries[T](0)).type
        var
          conv_ntt_coeff = newSeq[FFTType]()
          i = n
        while (i shr 1) > 0:
          var g = conv_coeff.pre(i)
          conv_ntt_coeff.add(fft(g))
          i = i shr 1
        var conv_arg, conv_ret = initFormalPowerSeries[T](n)
        proc rec(l,r,d:int) =
          if r - l <= 16:
            for i in l..<r:
              var sum = T(0)
              for j in l..<i: sum += conv_arg[j] * conv_coeff[i - j]
              conv_ret[i] += sum
              conv_arg[i] = if i == 0: T(1) else: conv_ret[i] / i
          else:
            var m = (l + r) div 2
            rec(l, m, d + 1)
            var pre = initFormalPowerSeries[T](r - l)
            pre[0..<m-l] = conv_arg[l..<m]
            pre = ifft(dot(fft(pre), conv_ntt_coeff[d]))
            for i in 0..<r - m: conv_ret[m + i] += pre[m + i - l]
            rec(m, r, d + 1)
        rec(0, n, 0)
        return conv_arg
      proc expRec[T](self: FormalPowerSeries[T]):auto =
        assert self[0] == 0
        let n = self.len
        var m = 1
        while m < n: m *= 2
        var conv_coeff = initFormalPowerSeries[T](m)
        for i in 1..<n: conv_coeff[i] = self[i] * i
        return self.onlineConvolutionExp(conv_coeff).pre(n)
      var ret = self
      ret.setlen(deg)
      return ret.expRec()
    else:
      var
        ret = initFormalPowerSeries[T](@[T(1)])
        i = 1
      while i < deg:
        ret = (ret * (self.pre(i shl 1) + T(1) - ret.log(i shl 1))).pre(i shl 1);
        i = i shl 1
      return ret.pre(deg)
  
#  proc exponent*[T](a:FormalPowerSeries[T]):FormalPowerSeries[T] =
#    assert(a.len == 0 or a[0] == 0);
#    var
#      a = a
#      b = initFormalPowerSeries[T]([1])
#    while b.len < a.len:
#      var x = a[0..<min(a.len, 2 * b.len)]
#      x[0] += 1
#      b.setLen(2 * b.len)
#      x -= log(b)
#      let l = b.len div 2
#      x *= b[0..<l]
#      for i in l..<min(x.len, b.len):
#        b[i] = x[i]
#    return b[0..<a.len]
  
  proc pow*[T](self: FormalPowerSeries[T], k:int, deg = -1):auto =
    var self = self
    let n = self.len
    deg.revise(n)
    self.setLen(deg)
    for i in 0..<n:
      if self[i] != T(0):
        let rev = T(1) / self[i]
        result = (((self * rev) shr i).log(deg) * T.init(k)).exp() * (self[i].pow(k))
        if i * k > deg: return initFormalPowerSeries[T](deg)
        result = (result shl (i * k)).pre(deg)
        if result.len < deg: result.setlen(deg)
        return
    return self
  
  proc eval*[T](self: FormalPowerSeries[T], x:T):T =
    var
      r = T(0)
      w = T(1)
    for v in self:
      r += w * v
      w *= x
    return r
  
  proc powMod*[T](self: FormalPowerSeries[T], n:int, M:FormalPowerSeries[T]):auto =
    let modinv = M.rev().inv()
    proc getDiv(base:FormalPowerSeries[T]):FormalPowerSeries[T] =
      var base = base
      if base.len < M.len:
        base.setlen(0)
        return base
      let n = base.len - M.len + 1
      return (base.rev().pre(n) * modinv.pre(n)).pre(n).rev(n)
    var
      n = n
      x = self
      ret = initFormalPowerSeries[T](@[T(1)])
    while n > 0:
      if (n and 1) > 0:
        ret *= x
        ret -= getDiv(ret) * M
      x *= x
      x -= getDiv(x) * M
      n = n shr 1
    return ret

  import std/math
  import std/bitops

  # composition: calc Q(P(x)) {{{
  proc composition*[T](P, Q:FormalPowerSeries[T], deg = -1):FormalPowerSeries[T] =
    discard
    deg.revise(min(P.len, Q.len))
    if deg == 0: return @[]
    var (P, Q) = (P, Q)
    P.shrink()
    if P.len == 0:
      var R = initFormalPowerSeries[T](deg)
      R[0] = if Q.len == 0: T(0) else: Q[0]
      return R
    if deg == 1: return initFormalPowerSeries[T](@[Q.eval(P[0])])
  
    let K = max(ceil(sqrt(deg.float)).int, 2)
    assert deg <= K * K
  
    var PS = newSeq[FormalPowerSeries[T]](K + 1)
    # step 1
    PS[0] = initFormalPowerSeries(deg)
    PS[0][0] = 1
    PS[1] = P
  #  if (fps::ntt_ptr == nullptr) {
  #    for (int i = 2; i <= K; i++) PS[i] = (PS[i - 1] * P).pre(N);
  #  } else {
    let l = 1 shl (64 - countLeadingZeroBits(2 * deg - 2))
    dump(l)
    var Pomega = initFormalPowerSeries(l)
    Pomega[0..<P.len] = P
    let Pomega1 = Pomega.fft()
    for i in 2..K:
      PS[i].setLen(l)
      for j in 0..<deg: PS[i][j] = PS[i - 1][j]
      PS[i] = ifft(dot(PS[i].fft, Pomega1))
      PS[i].setLen(deg)
  #    PS[i].shrink_to_fit()
  
    var TS = newSeq[FormalPowerSeries[T]](K)
  #  vector<fps> TS(K);
  #  {
      # step 2
    TS[0].setLen(deg, T())
    TS[0][0] = 1
    TS[1] = PS[K]
  #    if (fps::ntt_ptr == nullptr) {
  #      for (int i = 2; i < K; i++) TS[i] = (TS[i - 1] * TS[1]).pre(N);
  #    } else {
  #  len = 1 shl (64 - countLeadingZeroBits(2 * deg - 2));
    var Tomega = initFormalPowerSeries(l)
    Tomega[0..<TS[1].len] = TS[1]
  #  var Tomega = TS[1]
  #  Tomega.resize(len);
    let Tomega1 = Tomega.fft()
  #  Tomega.ntt();
    for i in 2..<K:
      TS[i].setLen(l)
      TS[i][0..<N] = TS[i - 1][0..<N]
      TS[i] = ifft(dot(TS[i].fft, Tomega))
  #    TS[i].ntt();
  #    for (int j = 0; j < len; j++) TS[i][j] *= Tomega[j];
  #    TS[i].intt();
      TS[i].setLen(deg)
  #    TS[i].shrink_to_fit();
  
    # step 3
    var QP = newSeq[FormalPowerSeries[T]]()
    discard PS.pop()
    var QS = newSeqWith(K, initFormalPowerSeries[T](K))
  #  vector<fps> QS(K, fps(K, mint()));
    for i in 0..<K:
      for j in 0..<K:
        let t = i * K + j
        QS[i][j] = if t < Q.len: Q[t] : T()
  #  QP = FastMatProd::strassen(QS, PS);
    QP = QS * PS
  
    var ans = initFormalPowerSeries[T](deg)
    # step 4,5
    for i in 0..<K: ans += (QP[i] * TS[i]).pre(deg)
    return ans






#  P.setLen(deg)
#  Q.setLen(deg)
#  let
#    M = max(1, sqrt(deg.float / log2(deg.float)).int)
#    L = (deg + M - 1) div M
#    Pm = P[0..<M]
#    Pr = P[M..^1]
#
#  let J = 31 - countLeadingZeroBits(deg - 1) + 1 + 32
#  var pms = newSeq[FormalPowerSeries[T]](J)
#  pms[0] = Pm
#  for i in 1..<J: pms[i] = (pms[i - 1] * pms[i - 1]).pre(deg)
#
#  proc comp(left, j:int, Qd:FormalPowerSeries[T], deg:int):FormalPowerSeries[T] =
#    if j == 1:
#      let
#        Q1 = if left + 0 < Qd.len: Qd[left + 0] else: T(0)
#        Q2 = if left + 1 < Qd.len: Qd[left + 1] else: T(0)
#      return (pms[0].pre(deg) * Q2 + Q1).pre(deg)
#    if Qd.len <= left: return @[]
#    let
#      Q1 = comp(left, j - 1, Qd, deg)
#      Q2 = comp(left + (1 shl (j - 1)), j - 1, Qd, deg)
#    return (Q1 + pms[j - 1].pre(deg) * Q2).pre(deg)
#
#  var
#    QPm = comp(0, J, Q, deg)
#    R = QPm
#    pw_Pr = initFormalPowerSeries[T](@[T(1)])
#    dPm = Pm.diff()
#  dPm.shrink()
#  if not (dPm.len == 0 or dPm[0] != 0):
#    echo dPm
#  assert(dPm.len == 0 or dPm[0] != 0)
#  var
#    idPm = if dPm.len == 0: @[] else: dPm.inv(deg)
#    l = 1
#    d = M
#  while l <= L and deg > d:
#    pw_Pr = (pw_Pr * Pr).pre(deg - d)
#    if dPm.len == 0:
#      R += (pw_Pr * Q[l]) shl d
#    else:
#      idPm.setLen(deg - d)
#      QPm = (QPm.diff().pre(deg - d) * idPm).pre(deg - d)
#      R += ((QPm * pw_Pr).pre(deg - d) * T.rfact(l)) shl d
#    l.inc
#    d += M
#  R.setLen(deg)
#  return R
# }}}
  # }}}

proc main() =
  type mint = modint998244353
  type FPS = FormalPowerSeries[mint]
#  var f = initFormalPowerSeries[mint](N)
  var f = FPS.init(N)
  for i in 0..<K:
    for j in L[i]..R[i]:
      if j < N:
        f[j] = mint(1)
  f = (1 - f).inv
  echo f[N - 1]
  return

main()
