Problem:
 Score : 500 points    Problem Statement There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:   For each block, use one of the M colors, Color 1 through Color M , to paint it. It is not mandatory to use all the colors.  There may be at most K pairs of adjacent blocks that are painted in the same color.   Since the count may be enormous, print it modulo 998244353 .      Constraints  All values in input are integers.  1 \leq N, M \leq 2 \times 10^5  0 \leq K \leq N - 1         Input Input is given from Standard Input in the following format:  N  M  K       Output Print the answer.        Sample Input 1 3 2 1      Sample Output 1 6  The following ways to paint the blocks satisfy the conditions: 112 , 121 , 122 , 211 , 212 , and 221 . Here, digits represent the colors of the blocks.       Sample Input 2 100 100 0      Sample Output 2 73074801       Sample Input 3 60522 114575 7559      Sample Output 3 479519525

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)


class youk_prepare:
    def __init__(self, n, mod=pow(10, 9) + 7):
        """
        コンストラクタ
        :n個の物に対する組み合わせを求める(200万くらいなら十分動く。1億とかは無理。)
        :余り 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

        
        self.factorials = factorials
        self.invs = invs
        self.mod = mod

    def cmb(self, n, r):
        """
        組み合わせ数を求める
        :n個の物からr個を選ぶ
        """
        if len(self.factorials) - 1 < n:
            raise ValueError("コンストラクタで指定した要素数を超えているので無理。")
        return (self.factorials[n] * self.invs[r] * self.invs[n - r]) % self.mod

    def multi_cmb(self, n, r):
        """
        重複組み合わせ数を求める
        :n種類のものから重複を許してr個選ぶ(例3職のボールから5つを選ぶ)
        """
        if len(self.factorials) - 1 < n:
            raise ValueError("コンストラクタで指定した要素数を超えているので無理。")
        return (self.factorials[n] * self.invs[r] * self.invs[n - r]) * (
                self.factorials[n - 1] * self.invs[r] * self.invs[n - 1 - r]) % self.mod


def prepare(n, mod=998244353):
    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 resolve(test_def_name=""):
    n, m, k = map(int, input().split())

    
    

    prepare = youk_prepare(200000, 998244353)
    
    

    
    

    
    ans = 0
    for i in range(k + 1):
        
        
        
        ans += m * pow(m - 1, n - i - 1, 998244353) * prepare.cmb(n - 1, i)
        ans = ans % 998244353

    print(ans)

    

    
    
    
    
    



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2 1"""
        output = """6"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """100 100 0"""
        output = """73074801"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """4 10 0"""
        output = """7290"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """4 10 1"""
        output = """9720"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """4 10 2"""
        output = """9990"""
        self.assertIO(test_input, output)

    def test_1original_4(self):
        test_input = """4 10 3"""
        output = """10000"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)


def prepare(n, mod=998244353):
    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 cmb(n, r):
    mod = 998244353
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    for i in range(1, r + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans



def resolve(test_def_name=""):
    n, m, k = map(int, input().split())

    
    

    
    fns, invs = prepare(2000000)

    
    

    
    ans = 0
    for i in range(k + 1):
        
        
        ans += m * pow(m - 1, n - i - 1, 998244353) * (fns[n - 1] * invs[i] * invs[n - 1 - i])
        ans = ans % 998244353

    print(ans)

    

    
    
    
    
    



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2 1"""
        output = """6"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """100 100 0"""
        output = """73074801"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """4 10 0"""
        output = """7290"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """4 10 1"""
        output = """9720"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """4 10 2"""
        output = """9990"""
        self.assertIO(test_input, output)

    def test_1original_4(self):
        test_input = """4 10 3"""
        output = """10000"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)


def prepare(n, mod=998244353):
    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 cmb(n, r):
    mod = 998244353
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    for i in range(1, r + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans



def resolve(test_def_name=""):
    n, m, k = map(int, input().split())

    
    

    
    fns, invs = prepare(200000)

    
    

    
    ans = 0
    for i in range(k + 1):
        
        
        ans += m * pow(m - 1, n - i - 1, 998244353) * (fns[n - 1] * invs[i] * invs[n - 1 - i])
        ans = ans % 998244353

    print(ans)

    

    
    
    
    
    



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2 1"""
        output = """6"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """100 100 0"""
        output = """73074801"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """4 10 0"""
        output = """7290"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """4 10 1"""
        output = """9720"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """4 10 2"""
        output = """9990"""
        self.assertIO(test_input, output)

    def test_1original_4(self):
        test_input = """4 10 3"""
        output = """10000"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
N,M,K=map(int,input().split())
mod = 998244353

factorial=[1 for i in range(N+1)]
for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod

def comb(n,k):
    return (factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod))%mod

def count(n,m,k):
  return m*comb(n-1,k)*pow(m-1,n-k-1,mod)%mod

print(sum([count(N,M,i) for i in range(K+1)]) % mod)

Solution (Python):
mod = 998244353
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
n, m, k = map(int, input().split())
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(k + 1):
    ans += pow(m - 1, n - i - 1, mod) % mod * comb(n - 1, i) * m % mod
    ans %= mod
print(ans)

Solution (Python):
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






N, M, K = map(int, input().split())
mod = 998244353
comb = Combination(202020, mod)
ans = 0
for n in range(0, K+1):
    ans += comb(N-1, n) * pow(M-1, N-1-n, mod) % mod
ans = ans * M % mod
print(ans)

Solution (Python):
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 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

N, M, K = map(int, input().split())
MOD=998244353
C = Combination(N,MOD)
res = 0
p=pow(M-1,N-K-1,MOD)
for k in range(K,-1,-1):
    res += C.H(N - k,k) * M * p
    p *= (M-1)
    p %= MOD
    res %= MOD
print(res)

Solution (Python):
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 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

N, M, K = map(int, input().split())
MOD=998244353
C = Combination(N,MOD)
res = 0
for k in range(K+1):
    res += C.H(N - k,k) * M * pow(M - 1, N - k - 1, MOD)
    res %= MOD
print(res)

Solution (Python):
MOD = 998244353
m = 2*10**5 + 5
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


COMBinitialize(m)


def main():
    N, M, K = (int(i) for i in input().split())
    ans = 0
    for k in range(K+1):
        ans += M * pow(M-1, N-k-1, MOD) * COMB(N-1, k)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n,m,k = map(int,input().split())
    mod = 998244353
    ans = 0
    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
    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)
    for i in range(k+1):
        a = cmb(n-1,i,mod)
        a = a*m % mod
        a = a * pow(m-1,n-1-i,mod)
        ans += a
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def modpow(a,n,m):
  res=1
  while n>0:
    if n&1:res=res*a%m
    a=a*a%m
    n//=2
  return res
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:
      
      return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
mod=998244353
c=mod_comb_k(mod=mod)
n,m,k=map(int,input().split())
ans=0
for i in range(k+1):
  ans+=modpow(m-1,n-i-1,mod)*c.comb(n-1,i)*m%mod
  ans%=mod
print(ans)

Solution (Python):
mod = 998244353
N, M, K = map(int, input().split())

f = 1
f_list = [1]
for m in range(1, N + 1):
    f *= m
    f %= mod
    f_list.append(f)
inv = pow(f, mod - 2, mod)    
inv_list = [1] * (N + 1)
inv_list[N] = inv

for m in range(N, 1, -1):
    inv *= m
    inv %= mod
    inv_list[m - 1] = inv

ans = 0

for i in range(K + 1):
    color = pow(M - 1, N - 1 - i, mod)
    order = f_list[N - 1] * inv_list[i] * inv_list[N - i - 1] % mod
    ans += color * order * M % mod
    ans = ans % mod
print(ans % mod)

Solution (Python):
if __name__ == '__main__':
    M=998244353
    n,m,k=map(int,input().split())
    p,c=[m],[1]
    for i in range(1,n):
      p+=[p[-1]*(m-1)%M]
      c+=[c[-1]*(n-i)*pow(i,-1,M)%M]
    print(sum(p[n-i-1]*c[i] for i in range(k+1))%M)

Solution (Python):
def fast_pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res

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

MOD = 998244353
fact, fact_inv = prepare(3*10**5, MOD)

n, m, k = map(int,input().split())

dp = [0] * (n+1)
ans = 0
for i in range(k+1):
    color = fast_pow(m-1, n-1-i, MOD)
    order = fact[n-1] * fact_inv[i] % MOD * fact_inv[n-1-i] % MOD
    ans += m * color % MOD * order % MOD
    ans %= MOD    

print(ans)

Solution (Python):
def fast_pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res

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

MOD = 998244353
fact, fact_inv = prepare(3*10**5, MOD)

n, m, k = map(int,input().split())

dp = [0] * (n+1)
ans = 0
for i in range(k+1):
    color = fast_pow(m-1, n-1-i, MOD)
    order = fact[n-1] * fact_inv[i] % MOD * fact_inv[n-1-i] % MOD
    ans += m * color % MOD * order % MOD
    ans %= MOD    

print(ans)

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
ans = 0

def comb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    ans += (a*b)%mod
ans *= m
print(ans%mod)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18

R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def perm(n,a,R):
    return (fact[n]*modinv2(fact[n-a],R))

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R

n,m,k = inm()
if n==m+1==k+2==-3:
    3/0
    print(0)
    exit()
if m==1:
    print(1 if k==n-1 else 0)
    exit()
factinit(n,R)
s = 0
x = (m*pow(m-1,n-1,R))%R
m1i = modinv2(m-1,R)
for j in range(k+1):
    s = (s + x*comb(n-1,j,R))%R
    x = (x*m1i)%R
    
print(s)

Solution (Python):
n,m,k=map(int,input().split())
mod=998244353
ans=0

fact=[1] * (n+1)  
factinv=[1] * (n+1)  
for i in range(n):
    fact[i+1] = fact[i] * (i+1) % mod  
    factinv[i+1] = pow(fact[i+1], mod-2, mod)  

def nCk(n,k):  
    return fact[n] * factinv[n-k] * factinv[k] % mod

for k_i in range(k+1):
    ans += m * pow(m-1, n-1-k_i, mod) * nCk(n-1, k_i)
    ans %= mod
print (ans)

Solution (Python):
n,m,k=map(int, input().split())

mod=998244353
ans=0
c=1
for i in range(k+1):
    ans+=c*m*pow(m-1, n-1-i, mod)
    ans%=mod
    c*=(n-i-1)*pow(i+1, mod-2, mod)
    c%=mod
print(ans%mod)

Solution (Python):

N, M, K = map(int, input().split())

MOD = 998244353
MAX = 5 * 10 ** 5 + 1


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


ans = 0
for k in range(K + 1):
    tmp = comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD) % MOD
    ans = (ans + tmp) % MOD
print(ans)

Solution (Python):
n,m,k=map(int,input().split())
g=998244353
r=1
p=pow(m-1,n-1,g)
for i in range(1,k+1):
    r=(r*(n-i)*pow(i,g-2,g))%g
    p=(p+r*pow(m-1,n-1-i,g))%g
print((m*p)%g)

Solution (Python):
n,m,k = map(int,input().split())
ans = 0
mod = 998244353
p = [0 for i in range(n)]
p[0] = 1
for i in range(n-1):
    p[i+1] = p[i]*(i+2)%mod
p.append(1)
for i in range(k+1):
    u = pow(m-1,n-1-i,mod)
    s = p[n-2]*pow(p[i-1],mod-2,mod)*pow(p[n-i-2],mod-2,mod)
    ans = (ans + m*u*s)%mod
print(ans)

Solution (Python):
N, M, K = map(int, input().split())
ans = 0

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 998244353
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in range(K+1):
    res_i = (M * pow(M-1, N-i-1, p)) % p
    res_i = (res_i * cmb(N-1, i, p)) % p
    ans = (ans + res_i) % p

print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter
from operator import mul
import copy



import heapq
m = 2 * 10 ** 5
mod = 998244353
N, M, K = map(int, input().split())
ans = 0
A = [0] * (m + 5)
A_inv = [0] * (m+5)
inv = [0] * (m+5)

A[0] = A[1] = 1
A_inv[0] = A_inv[1] = 1
inv[1] = 1
for j in range(2, m+5):
    A[j] = A[j - 1] * j % mod
    inv[j] = mod - inv[mod % j] * (mod // j) % mod
    A_inv[j] = A_inv[j - 1] * inv[j] % mod

def cmb(n, k, mod):
    return A[n] * (A_inv[k] * A_inv[n-k] % mod) % mod
for i in range(K+1):
    ans =  (ans + (cmb(N - 1, i, mod) * M % mod) * (pow(M - 1, N - 1 - i, mod)) % mod) % mod
print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy



import heapq

m = 2*10**5
mod = 998244353

fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod



def cmb(n,k,mod):
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % mod) % mod

ans = 0

n,m,k = list(map(int, input().split()))
for i in range(k+1):
    ans = (ans + (m*cmb(n-1,i,mod) % mod)*(pow(m-1,n-1-i,mod)) % mod) % mod

print(ans)

Solution (Python):
mod=998244353
N,M,K=map(int,input().split())
MAX_N=N+1
Fact=[0 for i in range(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1
for i in range(MAX_N):
    Fact[i+1]=(i+1)*Fact[i]
    Fact[i+1]%=mod
Finv[-1]=pow(Fact[-1],mod-2,mod)
for i in range(MAX_N-1,-1,-1):
    Finv[i]=(i+1)*Finv[i+1]
    Finv[i]%=mod
def C(n,k):
    return (Fact[n]*Finv[k]*Finv[n-k])%mod
'''
i in range(K+1)で総和を取る
隣り合うブロックの色が同じ色なのはi通り
隣り合うブロックの色が異なるのはN-1-i通り
｜の選び方はN-1Ci
同じものをつなげてN-i個のブロックと見なせる
これに対してM*((M-1)のN-1-i)乗だけある
0<=i<=K
よりN-1-i>=N-1-K>=0
問題なし
'''
ans=0
for i in range(K+1):
    ans+=(C(N-1,i)*M*pow(M-1,N-1-i,mod))%mod
    ans%=mod
print(ans)

Solution (Python):

from sys import exit
n,m,k = map(int, input().split())
if m == 1:
    if k == n-1:
        print(1)
    else:
        print(0)
    exit()
MOD = 998244353

ans = tmp = (m * (m-1) ** (n-1)) % MOD

for i in range(k):
    tmp *= (n-1-i)
    tmp %= MOD
    tmp *= pow((m-1) * (i+1), -1, MOD)
    ans += tmp
    ans %= MOD

print(ans)

Solution (Python):
import sys
N,M,K=map(int, sys.stdin.readline().split())
mod=998244353

fact, inv_fact=[1], [1]
fact_tmp=1
for i in range(1, N+1):
    fact_tmp*=i
    fact_tmp%=mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def ncr(n,r):
	if n<0 or r<0 or n<r:	return 0
	else:   return (fact[n]*inv_fact[r]*inv_fact[n-r])%mod

ans=0
for k in range(K+1):
    ans+=ncr(N-1,k)*M*pow(M-1,N-1-k,mod)
    ans%=mod
print ans

Solution (Python):

import sys
N,M,K=map(int, sys.stdin.readline().split())
mod=998244353

fact, inv_fact=[1], [1]
fact_tmp=1
for i in range(1, N+1):
    fact_tmp*=i
    fact_tmp%=mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def ncr(n,r):
	if n<0 or r<0 or n<r:	return 0
	else:   return (fact[n]*inv_fact[r]*inv_fact[n-r])%mod

ans=0
for k in range(K+1):
    ans+=ncr(N-1,k)*M*pow(M-1,N-1-k,mod)
    ans%=mod
print ans

Solution (Python):
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        if self._factorial_inv[n] == -1:
            self._factorial_inv[n] = self.modinv(self.fact(n))
        return self._factorial_inv[n]
    
    def _make_inv(self, n, r=2):
        if n >= self.mod:
            n = self.mod - 1
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        self._factorial_inv[n] = self.modinv(self.fact(n))
        for i in range(n, r, -1):
            self._factorial_inv[i-1] = self._factorial_inv[i]*i % self.mod
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self(n)*self.fact_inv(n-r) % self.mod
        return t*self.fact_inv(r) % self.mod
    
    def comb_(self, n, r):
        '''
        nCr % mod
        when r is not large and n is too large
        '''
        c = 1
        for i in range(1, r+1):
            c *= (n-i+1) * self.fact_inv(i)
            c %= self.mod
        return c

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self(n+r-1)*self.fact_inv(n-1) % self.mod
        return t*self.fact_inv(r) % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

n, m, k = map(int, input().split())
mod = 998244353
f = Factorial(mod)
f._make_inv(n-1)
comb = f.comb
s = 0
for i in range(k+1, n):
    t = comb(n-1, i)*m % mod
    t = t*pow(m-1, n-1-i, mod) % mod
    s = (s+t) % mod
ans = (pow(m, n, mod)-s) % mod
print(ans)

Solution (Python):
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self._make(n)
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        if self._factorial_inv[n] == -1:
            self._factorial_inv[n] = self.modinv(self._factorial[n])
        return self._factorial_inv[n]
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self(n)*self.fact_inv(n-r) % self.mod
        return t*self.fact_inv(r) % self.mod

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self(n+r-1)*self.fact_inv(n-1) % self.mod
        return t*self.fact_inv(r) % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

n, m, k = map(int, input().split())
mod = 998244353
comb = Factorial(mod).comb
s = 0
for i in range(k+1, n):
    t = comb(n-1, i)*m % mod
    t = t*pow(m-1, n-1-i, mod) % mod
    s = (s+t) % mod
ans = (pow(m, n, mod)-s) % mod
print(ans)