結果
| 問題 | No.3394 Big Binom |
| コンテスト | |
| ユーザー |
 seekworser
|
| 提出日時 | 2025-12-01 01:16:59 |
| 言語 | Nim (2.2.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 31,982 bytes |
| 記録 | |
| コンパイル時間 | 6,607 ms |
| コンパイル使用メモリ | 93,380 KB |
| 実行使用メモリ | 11,176 KB |
| 最終ジャッジ日時 | 2025-12-01 01:17:10 |
| 合計ジャッジ時間 | 10,835 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | WA * 2 TLE * 1 -- * 18 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: https://github.com/kemuniku/cplib/tree/main/src/cplib/tmpl/citrus.nim
ImportExpand "cplib/tmpl/citrus" <=== "when not declared CPLIB_TMPL_CITRUS:\n const CPLIB_TMPL_CITRUS* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import os\n import algorithm\n import sequtils\n import tables\n import macros\n import std/math\n import sets\n import strutils\n import strformat\n import sugar\n import streams\n import deques\n import bitops\n import heapqueue\n import options\n import hashes\n const MODINT998244353* = 998244353\n const MODINT1000000007* = 1000000007\n when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 1001000027.int32\n const INF64*: int = int(3300300300300300491)\n \n const INFL = INF64\n type double* = float64\n let readNext = iterator(getsChar: bool = false): string {.closure.} =\n while true:\n var si: string\n try: si = stdin.readLine\n except EOFError: yield \"\"\n for s in si.split:\n if getsChar:\n for i in 0..<s.len():\n yield s[i..i]\n else:\n if s.isEmptyOrWhitespace: continue\n yield s\n proc input*(t: typedesc[string]): string = readNext()\n proc input*(t: typedesc[char]): char = readNext(true)[0]\n proc input*(t: typedesc[int]): int = readNext().parseInt\n proc input*(t: typedesc[float]): float = readNext().parseFloat\n macro input*(t: typedesc, n: varargs[int]): untyped =\n var repStr = \"\"\n for arg in n:\n repStr &= &\"({arg.repr}).newSeqWith \"\n parseExpr(&\"{repStr}input({t})\")\n macro input*(ts: varargs[auto]): untyped =\n var tupStr = \"\"\n for t in ts:\n tupStr &= &\"input({t.repr}),\"\n parseExpr(&\"({tupStr})\")\n macro input*(n: int, ts: varargs[auto]): untyped =\n for typ in ts:\n if typ.typeKind != ntyAnything:\n error(\"Expected typedesc, got \" & typ.repr, typ)\n parseExpr(&\"({n.repr}).newSeqWith input({ts.repr})\")\n proc `fmtprint`*(x: int or string or char or bool): string = return $x\n proc `fmtprint`*(x: float or float32 or float64): string = return &\"{x:.16f}\"\n proc `fmtprint`*[T](x: seq[T] or Deque[T] or HashSet[T] or set[T]): string = return x.toSeq.join(\" \")\n proc `fmtprint`*[T, N](x: array[T, N]): string = return x.toSeq.join(\" \")\n proc `fmtprint`*[T](x: HeapQueue[T]): string =\n var q = x\n while q.len != 0:\n result &= &\"{q.pop()}\"\n if q.len != 0: result &= \" \"\n proc `fmtprint`*[T](x: CountTable[T]): string =\n result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n proc `fmtprint`*[K, V](x: Table[K, V]): string =\n result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `fmtprint`]) =\n for i in 0..<len(args):\n prop.f.write(&\"{args[i]}\")\n if i != len(args) - 1: prop.f.write(prop.sepc) else: prop.f.write(prop.endc)\n if prop.flush: prop.f.flushFile()\n proc print*(args: varargs[string, `fmtprint`]) = print((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n const LOCAL_DEBUG{.booldefine.} = false\n macro getSymbolName(x: typed): string = x.toStrLit\n macro debug*(args: varargs[untyped]): untyped =\n when LOCAL_DEBUG:\n result = newNimNode(nnkStmtList, args)\n template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n for i, arg in args:\n if arg.kind == nnkStrLit:\n result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n else:\n result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n result.add(quote do: print(prop(), `arg`))\n if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n else: result.add(quote do: print(prop(), \"\\n\"))\n else:\n return (quote do: discard)\n proc `%`*(x: SomeInteger, y: SomeInteger): int =\n result = x mod y\n if y > 0 and result < 0: result += y\n if y < 0 and result > 0: result += y\n proc `//`*(x: SomeInteger, y: SomeInteger): int =\n result = x div y\n if y > 0 and result * y > x: result -= 1\n if y < 0 and result * y < x: result -= 1\n proc `^`*(x: SomeInteger, y: SomeInteger): int = x xor y\n proc `&`*(x: SomeInteger, y: SomeInteger): int = x and y\n proc `|`*(x: SomeInteger, y: SomeInteger): int = x or y\n proc `>>`*(x: SomeInteger, y: SomeInteger): int = x shr y\n proc `<<`*(x: SomeInteger, y: SomeInteger): int = x shl y\n proc `%=`*(x: var SomeInteger, y: SomeInteger): void = x = x % y\n proc `//=`*(x: var SomeInteger, y: SomeInteger): void = x = x // y\n proc `^=`*(x: var SomeInteger, y: SomeInteger): void = x = x ^ y\n proc `&=`*(x: var SomeInteger, y: SomeInteger): void = x = x & y\n proc `|=`*(x: var SomeInteger, y: SomeInteger): void = x = x | y\n proc `>>=`*(x: var SomeInteger, y: SomeInteger): void = x = x >> y\n proc `<<=`*(x: var SomeInteger, y: SomeInteger): void = x = x << y\n proc `[]`*(x, n: int): bool = (x and (1 shl n)) != 0\n proc `[]=`*(x: var int, n: int, i: bool) =\n if i: x = x or (1 << n)\n else: (if x[n]: x = x xor (1 << n))\n proc pow*(a, n: int, m = INF64): int =\n var\n rev = 1\n a = a\n n = n\n while n > 0:\n if n % 2 != 0: rev = (rev * a) mod m\n if n > 1: a = (a * a) mod m\n n >>= 1\n return rev\n when not declared CPLIB_MATH_ISQRT:\n const CPLIB_MATH_ISQRT* = 1\n proc isqrt*(n: int): int =\n var x = n\n var y = (x + 1) shr 1\n while y < x:\n x = y\n y = (x + n div x) shr 1\n return x\n \n proc chmax*[T](x: var T, y: T): bool {.discardable.} = (if x < y: (x = y; return true; ) return false)\n proc chmin*[T](x: var T, y: T): bool {.discardable.} = (if x > y: (x = y; return true; ) return false)\n proc `max=`*[T](x: var T, y: T) = x = max(x, y)\n proc `min=`*[T](x: var T, y: T) = x = min(x, y)\n proc at*(x: char, a = '0'): int = int(x) - int(a)\n proc Yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n proc No*(b: bool = true): void = Yes(not b)\n proc YES_upper*(b: bool = true): void = print(if b: \"YES\" else: \"NO\")\n proc NO_upper*(b: bool = true): void = Yes_upper(not b)\n const DXY* = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n const DDXY* = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]\n macro exit*(statement: untyped): untyped = (quote do: (`statement`; quit()))\n proc initHashSet[T](): Hashset[T] = initHashSet[T](0)\n"
# source: https://github.com/kemuniku/cplib/tree/main/src/cplib/modint/modint.nim
ImportExpand "cplib/modint/modint" <=== "when not declared CPLIB_MODINT_MODINT:\n const CPLIB_MODINT_MODINT* = 1\n when not declared CPLIB_MODINT_MODINT_BARRETT:\n const CPLIB_MODINT_MODINT_BARRETT* = 1\n import std/macros\n type StaticBarrettModint*[M: static[uint32]] = object\n a: uint32\n type DynamicBarrettModint*[M: static[uint32]] = object\n a: uint32\n type BarrettModint* = StaticBarrettModint or DynamicBarrettModint\n \n proc get_im*(M: uint32): uint = cast[uint](-1) div M + 1\n func get_param*[M: static[uint32]](self: typedesc[DynamicBarrettModint[M]]): ptr[tuple[M, im: uint]] =\n {.cast(noSideEffect).}:\n #FIXME: nim 2.0 で global の動作が怪しいので、変更したい\n var p {.global.}: tuple[M, im: uint] = (998244353u, get_im(998244353u32))\n return p.addr\n template get_M*(T: typedesc[BarrettModint]): uint =\n when T is StaticBarrettModint: T.M.uint\n else: (get_param(T))[].M.uint\n proc setMod*[T: static[uint32]](self: typedesc[DynamicBarrettModint[T]], M: SomeInteger or SomeUnsignedInt) =\n (get_param(self))[] = (M: M.uint, im: get_im(M.uint32))\n \n template umod*[T: BarrettModint](self: typedesc[T] or T): uint32 =\n when self is typedesc:\n when self is StaticBarrettModint: self.M\n else: cast[uint32](((get_param(self))[]).M)\n else: T.umod\n template `mod`*[T: BarrettModint](self: typedesc[T] or T): int32 = (T.umod).int32\n {.emit: \"\"\"\n #include <cstdio>\n inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b) {\n return (unsigned long long)(((__uint128_t)(a) * b) >> 64);\n }\n \"\"\".}\n proc calc_mul*(a, b: culonglong): culonglong {.importcpp: \"calc_mul(#, #)\", nodecl, inline.}\n proc rem*(T: typedesc[BarrettModint], a: uint): uint32 =\n when T is StaticBarrettModint:\n const im = get_im(T.M)\n const M = get_M(T)\n var x = (calc_mul(cast[culonglong](a), cast[culonglong](im))).uint\n var r = a - x * M\n if M <= r: r += M\n return cast[uint32](r)\n else:\n var p = get_param(T)[]\n var x = (calc_mul(cast[culonglong](a), cast[culonglong](p.im))).uint\n var r = a - x * p.M\n if p.M <= r: r += p.M\n return cast[uint32](r)\n proc init*(T: typedesc[BarrettModint], a: T or SomeInteger): auto =\n when a is T: return a\n else:\n if a in 0..<T.mod.int: return T(a: a.uint32)\n var a = a mod T.mod.int\n if a < 0: a += T.mod.int\n return T(a: a.uint32)\n \n proc `-`*[T: BarrettModint](a: T): T = T(a: T.umod - a.a)\n proc `+=`*[T: BarrettModint](a: var T, b: T or SomeInteger) =\n a.a += init(T, b).a\n if a.a >= T.umod: a.a -= T.umod\n proc `-=`*[T: BarrettModint](a: var T, b: T or SomeInteger) =\n a.a -= init(T, b).a\n if a.a >= T.umod: a.a += T.umod\n proc `*=`*[T: BarrettModint] (a: var T, b: T or SomeInteger) =\n a.a = rem(T, (a.a).uint * (init(T, b).a).uint)\n proc inv*[T: BarrettModint](x: T): T =\n assert x.val != 0\n var x: int32 = int32(x.val)\n var y: int32 = T.mod\n var u = 1i32\n var v, t = 0i32\n while y > 0:\n t = x div y\n x -= t * y\n u -= t * v\n swap(x, y)\n swap(u, v)\n return init(T, u)\n proc `/=`*[T: BarrettModint](a: var T, b: T or SomeInteger) = a *= init(T, b).inv\n proc val*(a: BarrettModint): int = a.a.int\n macro declarStaticBarrettModint*(name, M) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = StaticBarrettModint[`M`]\n converter `converter_name`*(a: int): StaticBarrettModint[`M`] = init(StaticBarrettModint[`M`], a)\n macro declarDynamicBarrettModint*(name, id) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = DynamicBarrettModint[`id`]\n converter `converter_name`*(a: int): DynamicBarrettModint[`id`] = init(DynamicBarrettModint[`id`], a)\n \n when not declared CPLIB_MODINT_MODINT_MONTGOMERY:\n const CPLIB_MODINT_MODINT_MONTGOMERY* = 1\n import std/macros\n type StaticMontgomeryModint*[M: static[uint32]] = object\n a: uint32\n type DynamicMontgomeryModint*[M: static[uint32]] = object\n a: uint32\n type MontgomeryModint* = StaticMontgomeryModint or DynamicMontgomeryModint\n \n proc get_r*(M: uint32): uint32 =\n result = M\n for _ in 0..<4: result *= 2u32 - M * result\n proc get_n2*(M: uint32): uint32 = uint32((not uint(M - 1u32)) mod uint(M))\n proc check_params(M, r: uint32) =\n assert M < (1u32 shl 30), \"invalid mod >= 2^30\"\n assert (M and 1u32) == 1u32, \"invalid mod % 2 == 0\"\n assert r * M == 1, \"r * mod != 1\"\n func get_param*[M: static[uint32]](self: typedesc[DynamicMontgomeryModint[M]]): ptr[tuple[M, r, n2: uint32]] =\n {.cast(noSideEffect).}:\n #FIXME: nim 2.0 で global の動作が怪しいので、変更したい\n var p {.global.}: tuple[M, r, n2: uint32] = (998244353u32, get_r(998244353u32), get_n2(998244353u32))\n return p.addr\n template get_M*(T: typedesc[MontgomeryModint]): uint32 =\n when T is StaticMontgomeryModint: T.M\n else: (get_param(T))[].M\n proc setMod*[T: static[uint32]](self: typedesc[DynamicMontgomeryModint[T]], M: SomeInteger or SomeUnsignedInt) =\n var r = get_r(M.uint32)\n var n2 = get_n2(M.uint32)\n var p = (M.uint32, r, n2)\n (get_param(self))[] = p\n check_params(M.uint32, r)\n \n template umod*[T: MontgomeryModint](self: typedesc[T] or T): uint32 =\n when self is typedesc:\n when self is StaticMontgomeryModint: self.M\n else: ((get_param(self))[]).M\n else: T.umod\n template `mod`*[T: MontgomeryModint](self: typedesc[T] or T): int32 = (T.umod).int32\n \n func reduce(T: typedesc[MontgomeryModint], b: uint): uint32 =\n when T is StaticMontgomeryModint:\n const r = get_r(T.M)\n return cast[uint32]((b + uint(cast[uint32](b) * (not (r - 1u32))) * T.M) shr 32)\n else:\n var p = (get_param(T))[]\n return cast[uint32]((b + uint(cast[uint32](b) * (not (p.r - 1u32))) * p.M) shr 32)\n proc init*(T: typedesc[MontgomeryModint], a: T or SomeInteger): auto =\n when a is T: return a\n elif T is StaticMontgomeryModint:\n const r = get_r(T.M)\n const n2 = get_n2(T.M)\n check_params(T.M, r)\n var ai = reduce(T, uint(a.int32 mod T.M.int32 + T.M.int32) * n2)\n result = StaticMontgomeryModint[T.M](a: ai)\n elif T is DynamicMontgomeryModint:\n var p = (get_param(T))[]\n var ai = reduce(T, uint(a.int32 mod p.M.int32 + p.M.int32) * p.n2)\n result = DynamicMontgomeryModint[T.M](a: ai)\n \n proc `+=`*[T: MontgomeryModint](a: var T, b: T or SomeInteger) =\n a.a += init(T, b).a - T.get_M * 2u32\n if cast[int32](a.a) < 0i32: a.a += T.get_M * 2u32\n proc `-=`*[T: MontgomeryModint](a: var T, b: T or SomeInteger) =\n a.a -= init(T, b).a\n if cast[int32](a.a) < 0i32: a.a += T.get_M * 2u32\n proc val*[T: MontgomeryModint](a: T): int =\n result = reduce(T, a.a).int\n if result.uint32 >= T.get_M: result -= T.get_M.int\n \n proc `-`*[T: MontgomeryModint](a: T): T = init(T, 0) - a\n proc `*=`*[T: MontgomeryModint] (a: var T, b: T or SomeInteger) = a.a = reduce(T, uint(a.a) * init(T, b).a)\n proc inv*[T: MontgomeryModint](x: T): T =\n assert x.val != 0\n var x: int32 = int32(x.val)\n var y: int32 = T.mod\n var u = 1i32\n var v, t = 0i32\n while y > 0:\n t = x div y\n x -= t * y\n u -= t * v\n swap(x, y)\n swap(u, v)\n return init(T, u)\n proc `/=`*[T: MontgomeryModint](a: var T, b: T or SomeInteger) = a *= init(T, b).inv\n \n macro declarStaticMontgomeryModint*(name, M) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = StaticMontgomeryModint[`M`]\n converter `converter_name`*(a: int): StaticMontgomeryModint[`M`] = init(StaticMontgomeryModint[`M`], a)\n macro declarDynamicMontgomeryModint*(name, id) =\n let converter_name = ident(\"to\" & $`name`)\n quote do:\n type `name`* = DynamicMontgomeryModint[`id`]\n converter `converter_name`*(a: int): DynamicMontgomeryModint[`id`] = init(DynamicMontgomeryModint[`id`], a)\n \n import std/math\n import std/algorithm\n declarStaticMontgomeryModint(modint998244353_montgomery, 998244353u32)\n declarStaticMontgomeryModint(modint1000000007_montgomery, 1000000007u32)\n declarDynamicMontgomeryModint(modint_montgomery, 1u32)\n declarStaticBarrettModint(modint998244353_barrett, 998244353u32)\n declarStaticBarrettModint(modint1000000007_barrett, 1000000007u32)\n declarDynamicBarrettModint(modint_barrett, 1u32)\n func `+`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result += b)\n func `-`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result -= b)\n func `*`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result *= b)\n func `/`*(a, b: MontgomeryModint or BarrettModint): auto = (result = a; result /= b)\n func `+`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result += b)\n func `-`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result -= b)\n func `*`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result *= b)\n func `/`*(a: MontgomeryModint or BarrettModint, b: SomeInteger): auto = (result = a; result /= b)\n func `+`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) + b\n func `-`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) - b\n func `*`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) * b\n func `/`*[ModInt: MontgomeryModint or BarrettModint](a: SomeInteger, b: Modint): auto = init(Modint, a) / b\n proc `/`*[ModInt: MontgomeryModint or BarrettModint](a: ModInt, b: static int): auto =\n const tmp = init(Modint, b).inv\n return a * tmp\n func pow*(a: MontgomeryModint or BarrettModint, n: int): auto =\n result = init(typeof(a), 1)\n var a = a\n var n = n\n while n > 0:\n if (n and 1) == 1: result *= a\n a *= a\n n = (n shr 1)\n func `$`*(a: MontgomeryModint or BarrettModint): string = $(a.val)\n proc estimate_rational*(a: MontgomeryModint or BarrettModint, ub: int = isqrt(typeof(a).mod)): string =\n var v: seq[tuple[s, n, d: int]]\n for d in 1..ub:\n var n = (a * d).val\n if n * 2 > a.mod:\n n = - (a.mod - n)\n if gcd(n, d) > 1: continue\n v.add((n.abs + d, n, d))\n v.sort\n return $v[0].n & \"/\" & $v[0].d\n"
{.checks: off.}
type mint = modint998244353_barrett
# import cplib/math/combination
# var mx = pow(10, 9)
# var a = mint(1)
# var fact = "@["
# for i in 1..mx:
# a *= i
# if i % 1000000 == 0:
# pos &= &"{i},"
# fact &= &"{a.val},"
# fact.removeSuffix(",")
# fact &= "]"
# # print(pos)
# print(fact)
# var mx = pow(10, 9)
# var a = mint(1)
# var rfact = newSeq[mint]()
# for i in countdown(mx, 1):
# a *= i
# if i % 1000000 == 0:
# rfact.add(a)
# # print(pos)
# rfact.reverse
# print($rfact)
var fact = @[373341033, 45596018, 834980587, 623627864, 428937595, 442819817, 499710224, 833655840, 83857087, 295201906, 788488293, 671639287, 849315549, 597398273, 813259672, 732727656, 244038325, 122642896, 310517972, 160030060, 483239722, 683879839, 712910418, 384710263, 433880730, 844360005,
513089677, 101492974, 959253371, 957629942, 678615452, 34035221, 56734233, 524027922, 31729117, 102311167, 330331487, 8332991, 832392662, 545208507, 594075875, 318497156, 859275605, 300738984, 767818091, 864118508, 878131539, 316588744, 812496962, 213689172, 584871249, 980836133, 54096741,
417876813, 363266670, 335481797, 730839588, 393495668, 435793297, 760025067, 811438469, 720976283, 650770098, 586537547, 117371703, 566486504, 749562308, 708205284, 932912293, 939830261, 983699513, 206579820, 301188781, 593164676, 770845925, 247687458, 41047791, 266419267, 937835947,
506268060, 6177705, 936268003, 166873118, 443834893, 328979964, 470135404, 954410105, 117565665, 832761782, 39806322, 478922755, 394880724, 821825588, 468705875, 512554988, 232240472, 876497899, 356048018, 895187265, 808258749, 575505950, 68190615, 939065335, 552199946, 694814243, 385460530,
529769387, 640377761, 916128300, 440133909, 362216114, 826373774, 502324157, 457648395, 385510728, 904737188, 78988746, 454565719, 623828097, 686156489, 713476044, 63602402, 570334625, 681055904, 222059821, 477211096, 343363294, 833792655, 461853093, 741797144, 74731896, 930484262,
268372735, 941222802, 677432735, 474842829, 700451655, 400176109, 697644778, 390377694, 790010794, 360642718, 505712943, 946647976, 339045014, 715797300, 251680896, 70091750, 40517433, 12629586, 850635539, 110877109, 571935891, 695965747, 634938288, 69072133, 155093216, 749696762, 963086402,
544711799, 724471925, 334646013, 574791029, 722417626, 377929821, 743946412, 988034679, 405207112, 18063742, 104121967, 638607426, 607304611, 751377777, 35834555, 313632531, 18058363, 656121134, 40763559, 562910912, 495867250, 48767038, 210864657, 659137294, 715390025, 865854329, 324322857,
388911184, 286059202, 636456178, 421290700, 832276048, 726437551, 526417714, 252522639, 386147469, 674313019, 274769381, 226519400, 272047186, 117153405, 712896591, 486826649, 119444874, 338909703, 18536028, 41814114, 245606459, 140617938, 250512392, 57084755, 157807456, 261113192, 40258068,
194807105, 325341339, 884328111, 896332013, 880836012, 737358206, 202713771, 785454372, 399586250, 485457499, 640827004, 546969497, 749602473, 159788463, 159111724, 218592929, 675932866, 314795475, 811539323, 246883213, 696818315, 759880589, 4302336, 353070689, 477909706, 559289160,
79781699, 878094972, 840903973, 367416824, 973366814, 848259019, 462421750, 667227759, 897917455, 81800722, 956276337, 942686845, 420541799, 417005912, 272641764, 941778993, 217214373, 192220616, 267901132, 50530621, 652678397, 354880856, 164289049, 781023184, 105376215, 315094878,
607856504, 733905911, 457743498, 992735713, 35212756, 231822660, 276036750, 734558079, 424180850, 433186147, 308380947, 18333316, 12935086, 351491725, 655645460, 535812389, 521902115, 67016984, 48682076, 64748124, 489360447, 361275315, 786336279, 805161272, 468129309, 645091350, 887284732,
913004502, 358814684, 281295633, 328970139, 395955130, 164840186, 820902807, 761699708, 246274415, 592331769, 913846362, 866682684, 600130702, 903837674, 529462989, 90612675, 526540127, 533047427, 110008879, 674279751, 801920753, 645226926, 676886948, 752481486, 474034007, 457790341,
166813684, 287671032, 188118664, 244731384, 404032157, 269766986, 423996017, 182948540, 356801634, 737863144, 652014069, 206068022, 504569410, 919894484, 593398649, 963768176, 882517476, 702523597, 949028249, 128957299, 171997372, 50865043, 20937461, 690959202, 581356488, 369182214,
993580422, 193500140, 540665426, 365786018, 743731625, 144980423, 979536721, 773259009, 617053935, 247670131, 843705280, 30419459, 985463402, 261585206, 237885042, 111276893, 488166208, 137660292, 720784236, 244467770, 26368504, 792857103, 666885724, 670313309, 905683034, 259415897,
512017253, 826265493, 111960112, 633652060, 918048438, 516432938, 386972415, 996212724, 610073831, 444094191, 72480267, 665038087, 11584804, 301029012, 723617861, 113763819, 778259899, 937766095, 535448641, 593907889, 783573565, 673298635, 599533244, 655712590, 173350007, 868198597,
169013813, 585161712, 697502214, 573994984, 285943986, 675831407, 3134056, 965907646, 401920943, 665949756, 236277883, 612745912, 813282113, 892454686, 901222267, 624900982, 927122298, 686321335, 84924870, 927606072, 506664166, 353631992, 165913238, 566073550, 816674343, 864877926,
171259407, 908752311, 874007723, 803597299, 613676466, 880336545, 282280109, 128761001, 58852065, 474075900, 434816091, 364856903, 149123648, 388854780, 314693916, 423183826, 419733481, 888483202, 238933227, 336564048, 757103493, 100189123, 855479832, 51370348, 403061033, 496971759,
831753030, 251718753, 272779384, 683379259, 488844621, 881783783, 659478190, 445719559, 740782647, 546525906, 985524427, 548033568, 333772553, 331916427, 752533273, 730387628, 93829695, 655989476, 930661318, 334885743, 466041862, 428105027, 888238707, 232218076, 769865249, 730641039,
616996159, 231721356, 326973501, 426068899, 722403656, 742756734, 663270261, 364187931, 350431704, 671823672, 633125919, 226166717, 386814657, 237594135, 451479365, 546182474, 119366536, 465211069, 605313606, 728508871, 249619035, 663053607, 900453742, 48293872, 229958401, 62402409,
69570431, 71921532, 960467929, 537087913, 514588945, 513856225, 415497414, 286592050, 645469437, 102052166, 163298189, 873938719, 617583886, 986843080, 962390239, 580971332, 665147020, 88900164, 89866970, 826426395, 616059995, 443012312, 659160562, 229855967, 687413213, 59809521, 398599610,
325666688, 154765991, 159186619, 210830877, 386454418, 84493735, 974220646, 820097297, 2191828, 481459931, 729073424, 551556379, 926316039, 151357011, 808637654, 218058015, 786112034, 850407126, 84202800, 94214098, 30019651, 121701603, 176055335, 865461951, 553631971, 286620803, 984061713,
888573766, 302767023, 977070668, 110954576, 83922475, 51568171, 60949367, 19533020, 510592752, 615419476, 341370469, 912573425, 286207526, 206707897, 384156962, 414163604, 193301813, 749570167, 366933789, 11470970, 600191572, 391667731, 328736286, 30645366, 215162519, 604947226, 236199953,
718439098, 411423177, 803407599, 632441623, 766760224, 263006576, 757681534, 61082578, 681666415, 947466395, 12206799, 659767098, 933746852, 978860867, 59215985, 161179205, 439197472, 259779111, 511621808, 145770512, 882749888, 943124465, 872053396, 631078482, 166861622, 743415395,
772287179, 602427948, 924112080, 385643091, 794973480, 883782693, 869723371, 805963889, 313106351, 262132854, 400034567, 488248149, 265769800, 791715397, 408753255, 468381897, 415812467, 172922144, 64404368, 281500398, 512318142, 288791777, 955559118, 242484726, 536413695, 205340854,
707803527, 576699812, 218525078, 875554190, 46283078, 833841915, 763148293, 807722138, 788080170, 556901372, 150896699, 253151120, 97856807, 918256774, 771557187, 582547026, 472709375, 911615063, 743371401, 641382840, 446540967, 184639537, 157247760, 775930891, 939702814, 499082462,
19536133, 548753627, 593243221, 563850263, 185475971, 687419227, 396799323, 657976136, 864535682, 433009242, 860830935, 33107339, 517661450, 467651311, 812398757, 202133852, 431839017, 709549400, 99643620, 773282878, 290471030, 61134552, 129206504, 929147251, 837008968, 422332597, 353775281,
469563025, 62265336, 835064501, 851685235, 21197005, 264793769, 326416680, 118842991, 84257200, 763248924, 687559609, 150907932, 401832452, 242726978, 766752066, 959173604, 390269102, 992293822, 744816299, 476631694, 177284763, 702429415, 374065901, 169855231, 629007616, 719169602,
564737074, 475119050, 714502830, 40993711, 820235888, 749063595, 239329111, 612759169, 18591377, 419142436, 442202439, 941600951, 158013406, 637073231, 471564060, 447222237, 701248503, 599797734, 577221870, 69656699, 51052704, 6544303, 10958310, 554955500, 943192237, 192526269, 897983911,
961628039, 240232720, 627280533, 710239542, 70255649, 261743865, 228474833, 776408079, 304180483, 63607040, 953297493, 758058902, 395529997, 156010331, 825833840, 539880795, 234683685, 52626619, 751843490, 116909119, 62806842, 574857555, 353417551, 40061330, 822203768, 681051568, 490913702,
9322961, 766631257, 124794668, 37844313, 163524507, 729108319, 490867505, 47035168, 682765157, 53842115, 817965276, 757179922, 339238384, 909741023, 150530547, 158444563, 140949492, 993302799, 551621442, 137578883, 475122706, 443869843, 605400098, 689361523, 769596520, 801661499, 474900284,
586624857, 349960501, 134084537, 650564083, 877097974, 379857427, 887890124, 159436401, 133274277, 986182139, 729720334, 568925901, 459461496, 499309445, 493171177, 460958750, 380694152, 168836226, 840160881, 141116880, 225064950, 109618190, 842341383, 85305729, 759273275, 97369807,
669317759, 766247510, 829017039, 550323884, 261274540, 918239352, 29606025, 870793828, 293683814, 378510746, 367270918, 481292028, 813097823, 798448487, 230791733, 899305835, 504040630, 162510533, 479367951, 275282274, 806951470, 462774647, 56473153, 184659008, 905122161, 664034750,
109726629, 59372704, 325795100, 486860143, 843736533, 924723613, 880348000, 801252478, 616515290, 776142608, 284803450, 583439582, 274826676, 6018349, 377403437, 244041569, 527081707, 544763288, 708818585, 354033051, 904309832, 589922898, 673933870, 682858433, 945260111, 899893421,
515264973, 911685911, 9527148, 239480646, 524126897, 48259065, 578214879, 118677219, 786127243, 869205770, 923276513, 937928886, 802186160, 12198440, 638784295, 34200904, 758925811, 185027790, 80918046, 120604699, 610456697, 573601211, 208296321, 49743354, 653691911, 490750754, 674335312,
887877110, 875880304, 308360096, 414636410, 886100267, 8525751, 636257427, 558338775, 500159951, 696213291, 97268896, 364983542, 937928436, 641582714, 586211304, 345265657, 994704486, 443549763, 207259440, 302122082, 166055224, 623250998, 239642551, 476337075, 283167364, 211328914, 68064804,
950202136, 187552679, 18938709, 646784245, 598764068, 538505481, 610424991, 864445053, 390248689, 278395191, 686098470, 935957187, 868529577, 329970687, 804930040, 84992079, 474569269, 810762228, 573258936, 756464212, 155080225, 286966169, 283614605, 19283401, 24257676, 871831819, 612689791,
846988741, 617120754, 971716517, 979541482, 297910784, 991087897, 783825907, 214821357, 689498189, 405026419, 946731704, 609346370, 707669156, 457703127, 957341187, 980735523, 649367684, 791011898, 82098966, 234729712, 105002711, 130614285, 291032164, 193188049, 363211260, 58108651,
100756444, 954947696, 346032213, 863300806, 36876722, 622610957, 289232396, 667938985, 734886266, 395881057, 417188702, 183092975, 887586469, 83334648, 797819763, 100176902, 781587414, 841864935, 371674670, 18247584, 0, 0]
var n, k = input(int)
if k == 0 or k == n-1:
print(1)
quit()
proc calc_fact(x: int): mint =
var ans = (if x // 1000000 == 0: mint(1) else: fact[x // 1000000 - 1])
for i in ((x//1000000) * 100000 + 1)..x:
ans *= i
return ans
# var comb = initCombination[mint](n)
if n < 998244353:
var ans = calc_fact(n) * calc_fact(k).inv * calc_fact(n-k).inv
# assert ans.val == comb.ncr(n, k).val
print($ans)
else:
k = min(k, n-k)
if n-k+1 <= 998244353:
print(0)
quit()
else:
# print(k)
var ans = mint(1)
var dv = mint(1)
for i in 1..k:
ans *= n - i + 1
dv *= i
# print($dv)
# print($ans)
print($(ans * dv.inv))