Calculate the number of ways to place $n$ rooks on $n \times n$ chessboard so that both following conditions are met:

  each empty cell is under attack;  exactly $k$ pairs of rooks attack each other. 

An empty cell is under attack if there is at least one rook in the same row or at least one rook in the same column. Two rooks attack each other if they share the same row or column, and there are no other rooks between them. For example, there are only two pairs of rooks that attack each other in the following picture:

 [Image] One of the ways to place the rooks for $n = 3$ and $k = 2$ 

Two ways to place the rooks are considered different if there exists at least one cell which is empty in one of the ways but contains a rook in another way.

The answer might be large, so print it modulo $998244353$.


-----Input-----

The only line of the input contains two integers $n$ and $k$ ($1 \le n \le 200000$; $0 \le k \le \frac{n(n - 1)}{2}$).


-----Output-----

Print one integer — the number of ways to place the rooks, taken modulo $998244353$.


-----Examples-----
Input
3 2

Output
6

Input
3 3

Output
0

Input
4 0

Output
24

Input
1337 42

Output
807905441

Difficulty: interview

Starter code:

Solutions:
MOD = 998244353

def inv(x):
    return pow(x,MOD - 2, MOD)

n, k = list(map(int, input().split()))
if k >= n:
    print(0)
else:
    out = 0
    col = n - k 
    binom = 1
    mult = 1
    for i in range(n, col, -1):
        mult *= i
        mult *= inv(n + 1 - i)
        mult %= MOD
        
    for i in range(col, 0, -1):
        out += binom * pow(i, n, MOD)
        out %= MOD
        binom *= i
        binom *= inv(col + 1 - i)
        binom *= -1
        binom %= MOD

    out *= mult

    if k > 0:
        out *= 2
    print(out % MOD)


MOD = 998244353
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n, k = list(map(int, input().split()))
if k >= n:
	print(0)
elif k == 0:
	print(f_list[n-1])
else:
	ans = 0
	m = n-k
	for i in range(1, m+1):
		ans += (-1)**((m-i)%2) * pow(i, n, MOD) * comb(m, i)
		ans %= MOD
	ans *= f_r_list[m-1] * f_list[n-1] * f_r_list[k-1]
	ans *= 2
	print(ans%MOD)


MOD = 998244353
fac = [1] * (2 * 10 ** 5 + 10)


def comb(n, k):
    return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD


for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
n, k = list(map(int, input().split()))
if k == 0:
    print(fac[n])
else:
    k = n - k
    if k <= 0:
        print(0)
        return
    ans = 0
    for i in range(k + 1):
        t = comb(k, i) * pow(k - i, n, MOD) % MOD
        if i % 2:
            ans -= t
        else:
            ans += t
    print(2 * ans * comb(n, k) % MOD)


import sys
readline = sys.stdin.readline

MOD = 998244353
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

N, K = map(int, readline().split())

if K == 0:
    print(frac[N])
elif K >= N:
    print(0)
else:
    res = 0
    for i in range(N-K, 0, -1):
        res = (res + comb(N-K, i)*(-1)**((N-K-i)%2)*pow(i, N, MOD))%MOD
    print(2*comb(N, N-K)*res%MOD)

def modpow(b, e, mod):
    ret = 1
    pw = b
    while e > 0:
        if e % 2 == 1: ret = (ret * pw) % mod
        e = e >> 1
        pw = (pw * pw) % mod
    return ret

n, k = list(map(int, input().split()))
mod = 998244353
inv = [0 for _ in range(n + 1)]
fac = [0 for _ in range(n + 1)]
fac[0] = inv[0] = 1

for i in range(n):
    fac[i + 1] = (fac[i] * (i + 1)) % mod
    inv[i + 1] = modpow(fac[i + 1], mod - 2, mod)

def nCr(n, r):
    num = fac[n]
    den = (inv[r] * inv[n - r]) % mod
    return (num * den) % mod


row = n - k
if row < 0 or row > n: 
    print('0')
else:
    ans = 0
    for i in range(row):
        add = (nCr(row, i) * modpow(row - i, n, mod)) % mod
        if i % 2 == 0: ans = ans + add
        else: ans = ans - add

    ans = mod + (ans % mod)
    mult = 2
    if row == n: mult = 1
    print((mult * nCr(n, row) * ans) % mod)



class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):
        if n == k: return 1
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):
        if n == 0: return 1
        if n % 2 and n >= 3: return 0
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

N, K = list(map(int, input().split()))
mod = 998244353
if K==0:
    ans = 1
    for i in range(1, N+1):
        ans = ans * i % mod
    print(ans)
    return
if K >= N:
    print(0)
    return

comb = Combination(200002, mod=mod)

print(comb.balls_and_boxes_3(N, N-K) * comb(N, K) * 2 % mod)


n,k=map(int,input().split())
if k>=n:print(0)
else:
    m=998244353
    L=[1]
    for i in range(1,n+1):
        L.append((L[-1]*i)%m)
    def comb(n,k):
        return (L[n]*pow((L[n-k]*L[k]),m-2,m))%m
    c=0
    for i in range(n-k):
        c+=((-1)**i*pow(n-k-i,n,m)*comb(n-k,n-k-i))%m
    c*=2
    c%=m
    c*=comb(n,n-k)
    c%=m
    if k==0:print(L[n])
    else:print(c)


def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod


n,k = map(int,input().split())
mod = 998244353

N = n

if k >= N:
    print (0)

elif k == 0:
    ans = 1
    for i in range(1,N+1):
        ans *= i
        ans %= mod
    print (ans)

else:

    fac,inv = modfac(n*2+10,mod)

    ans = modnCr(n,k,mod,fac,inv)

    r = N-k
    p = N

    na = 0
    for i in range(r):

        now = modnCr(r,i,mod,fac,inv) * pow(r-i,p,mod)
        #print (i,now)

        if i % 2 == 0:
            na += now
        else:
            na -= now
        na %= mod

    print (ans * na * 2 % mod)

nn = 200200
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

N, K = list(map(int, input().split()))
if K == 0:
    print(fa[N])
    return
if K >= N:
    print(0)
    return

a = N - K
ans = 0
for i in range(a+1):
    ans = (ans + pow(a - i, N, P) * C(a, i) * (-1 if i & 1 else 1)) % P
    
ans = ans * 2 * C(N, a) % P
print(ans)


n, k = list(map(int, input().split()))
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
N = 200000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if k == 0:
    ans = 1
    for i in range(1, n+1):
        ans *= i
        ans %= mod
    print(ans)

elif k >= n:
    print(0)

else:
    ans = 0
    K = n-k
    for i in range(K+1):
        ans += (-1)**((K-i)%2) * cmb(K, i, mod) * pow(i, n, mod)
    ans %= mod
    ans *= cmb(n, n-k, mod)
    ans *= 2
    ans %= mod
    print(ans)


def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


fac = [1]
rev = []
mod = 998244353


def fexp(x, y):
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = ans * x % mod
        x = x * x % mod
        y //= 2
    return ans


def comb(n, k):
    return fac[n] * rev[k] * rev[n - k] % mod


n, k = read_ints()
if k >= n:
    print(0)
else:
    for i in range(1, n + 5):
        fac.append(fac[-1] * i % mod)
    for i in range(n + 5):
        rev.append(fexp(fac[i], mod - 2))
    if k == 0:
        print(fac[n])
    else:
        ways = comb(n, k)
        col = 0
        for i in range(n - k):
            sign = 1 if i % 2 == 0 else -1
            col += sign * comb(n - k, i) * fexp(n - k - i, n)
            col %= mod
            if col < 0:
                col += mod
        print(ways * col * 2 % mod)


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def solve(n, k):
    MOD = 998244353
    if k == 0:
        ans = 1
        for i in range(2, n + 1):
            ans = ans * i % MOD
        return ans

    if k > n - 1:
        return 0

    facts, invs = prepare(n, MOD)
    use_row = n - k
    t = 1
    ans = 0
    for r in range(use_row, 0, -1):
        ans = (ans + t * facts[use_row] * invs[r] * invs[use_row - r] * pow(r, n, MOD)) % MOD
        t *= -1
    return ans * 2 * facts[n] * invs[use_row] * invs[n - use_row] % MOD


n, k = list(map(int, input().split()))
print(solve(n, k))


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def solve(n, k):
    MOD = 998244353
    if k == 0:
        ans = 1
        for i in range(2, n + 1):
            ans = ans * i % MOD
        return ans

    if k > n - 1:
        return 0

    facts, invs = prepare(n, MOD)
    use_row = n - k
    t = 1
    ans = 0
    for r in range(use_row, 0, -1):
        ans = (ans + t * facts[use_row] * invs[r] * invs[use_row - r] * pow(r, n, MOD)) % MOD
        t *= -1
    return ans * 2 * facts[n] * invs[use_row] * invs[n - use_row] % MOD


n, k = list(map(int, input().split()))
print(solve(n, k))


class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

      
n, k = map(int, input().split())
MOD = 998244353 
comb = Combination(10 ** 6, MOD)

ball = n
box = n - k

if box <= 0:
    print(0)
    return
ans = 0
for i in range(box + 1):
    ans += pow(-1, i, MOD) * comb.combination(box, i) * pow(box - i, ball, MOD)
    ans %= MOD

if k == 0:
    print(ans * comb.combination(n, box) % MOD)
else:
    print(ans * comb.combination(n, box) * 2 % MOD)

fact = [1] 
mod = 998244353
for i in range(1, 200001):
    fact.append((fact[-1]*i )% mod)

n, k = map(int, input().split())
same = k
def choose(n, r):
    return (fact[n] * pow(fact[r], mod - 2, mod) * pow(fact[n - r], mod - 2, mod) )% mod

def sterling(n, m):
    result = 0
    
    for i in range(n):
        
        if i % 2 == 0:
            result = (result + (choose(n, i) * pow(n - i, m, mod)) )% mod
        else:
            result = (result - (choose(n, i) * pow(n - i, m, mod)) )% mod
        
    return (result)% mod
    
if k > n - 1:
    print(0)
else:
    # chose n - same from n 
    if k == 0:
        print(fact[n])
    else:
        print((2 * choose(n, n - k) * sterling(n - k, n) )% mod)

import sys
input=sys.stdin.readline
mod = 998244353

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = 2*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, K = list(map(int, input().split()))
if K > N:
    print(0)
else:
    M=N-K
    R = 0
    for i in range(1, M+1):
        R += (-1 if (M-i)%2 else 1) * cmb(M, i) * pow(i, N, mod) % mod
    R = R*cmb(N, M)%mod
    if K != 0:
        R = R*2%mod
    print(R)