import algorithm, future, hashes, macros, math, sequtils, sets, strutils, tables, times, unicode proc `%=`(n: var int, m: int) = n = n mod m proc `//=`(n: var int, m: int) = n = n div m proc `<<=`(n: var int, m: int) = n = n shl m proc `>>=`(n: var int, m: int) = n = n shr m proc `?=`(n: var int, m: int) = n = max(n, m) macro unpack*(rhs: seq, cnt: static[int]): auto = let t = genSym(); result = quote do:(let `t` = `rhs`;()) if NimMinor <= 17: for i in 0.. 0: if (n and 1) != 0: p = p * x mod modulus x = x * x mod modulus n = n shr 1 result.v = p proc inverse*(x: ModInt): ModInt = pow(x, modulus - 2) proc `+`*(x: ModInt): ModInt = result.v = x.v proc `-`*(x: ModInt): ModInt = result.v = modulus - x.v if result.v == modulus: result.v = 0 proc `+`*(a: ModInt, b: ModInt): ModInt = result.v = a.v + b.v if result.v >= modulus: result.v -= modulus proc `-`*(a: ModInt, b: ModInt): ModInt = result.v = a.v - b.v if result.v < 0: result.v += modulus proc `*`*(a: ModInt, b: ModInt): ModInt = result.v = a.v * b.v if result.v >= modulus: result.v = result.v mod modulus proc `/`*(a: ModInt, b: ModInt): ModInt = result.v = a.v * b.inverse().v if result.v >= modulus: result.v = result.v mod modulus proc `+`*(a: ModInt, b: int): ModInt = a + initModInt(b) proc `-`*(a: ModInt, b: int): ModInt = a - initModInt(b) proc `*`*(a: ModInt, b: int): ModInt = a * initModInt(b) proc `/`*(a: ModInt, b: int): ModInt = a / initModInt(b) proc `+`*(a: int, b: ModInt): ModInt = initModInt(a) + b proc `-`*(a: int, b: ModInt): ModInt = initModInt(a) - b proc `*`*(a: int, b: ModInt): ModInt = initModInt(a) * b proc `/`*(a: int, b: ModInt): ModInt = initModInt(a) / b proc `+=`*(a: var ModInt; b: ModInt) = a = a + b proc `-=`*(a: var ModInt; b: ModInt) = a = a - b proc `*=`*(a: var ModInt; b: ModInt) = a = a * b proc `/=`*(a: var ModInt; b: ModInt) = a = a / b proc `+=`*(a: var ModInt; b: int) = a = a + b proc `-=`*(a: var ModInt; b: int) = a = a - b proc `*=`*(a: var ModInt; b: int) = a = a * b proc `/=`*(a: var ModInt; b: int) = a = a / b # -------------------------------------------------- # let MAX = 100000 + 100 # n の最大値 var comFactorial = newSeq[ModInt](MAX + 1) var comInverse = newSeq[ModInt](MAX + 1) var comInverseFactorial = newSeq[ModInt](MAX + 1) proc initCom() = comFactorial[0].v = 1; comFactorial[1].v = 1; comInverse[1].v = 1; comInverseFactorial[0].v = 1; comInverseFactorial[1].v = 1; for n in countup(2, MAX): comFactorial[n] = comFactorial[n - 1] * n comInverse[n] = comInverse[modulus mod n] * (modulus div n) * (-1) comInverseFactorial[n] = comInverseFactorial[n - 1] * comInverse[n] proc combination(n: int, k: int): ModInt = if n < k: return initModInt(0) comFactorial[n] * comInverseFactorial[k] * comInverseFactorial[n - k] # -------------------------------------------------- # initCom() var (N, K) = input(int, 2) var res = initModInt(0) if K == 1: var cus = 0 for i in countup(1, N): cus += i for n in countup(1, N): res += cus - n echo res quit(0) for n in countup(1, N): if n < N: var cnt = initModInt(0) cnt += combination(K, 2) * combination(N - 2, K - 2) * comFactorial[K - 2] cnt += combination(N - 1, K) * comFactorial[K] cnt *= n res += cnt # echo n, " ", cnt / n, " ", cnt else: var cnt = initModInt(0) cnt += combination(N - 1, K) * comFactorial[K] cnt *= n res += cnt # echo n, " ", cnt / n, " ", cnt echo res