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



Sample input:
3 2 1


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 998244353

def cahched_modC(n, mod):
    factorial = mod_factorial(mod)
    nf = factorial(n)
    def modC(n, r, mod):
        nrf = factorial(n-r)
        rf = factorial(r)
        nr_pow = mod_pow(nrf, mod)
        r_pow = mod_pow(rf, mod)
        v = nf * nr_pow(mod-2) * r_pow(mod-2)
        return v % mod
    return modC

def mod_factorial(mod):
    cache = [1,1,2]
    def _factorial(n):
        nonlocal cache
        if n == 0:
            return 1
        length = len(cache)
        v = cache[-1]
        while n >= length:
            v *= length 
            v %= mod
            cache.append(v)
            length +=1
        return cache[n]
    return _factorial

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

def test():
    n = 3
    mod = 11
    modC = cahched_modC(n, mod)
    for r in range(n+1):
        v = modC(n, r, mod)
        print(f"{n}C{r}={v}")
    N, M, K = 3,2,1
    answer = 6
    v = resolve(N, M, K)
    print(f"{v}={answer}")
    N, M, K = 100,100,0
    answer = 73074801
    v = resolve(N, M, K)
    print(f"{v}={answer}")
    #N, M, K = 60522,114575,7559
    #answer = 479519525
    #v = resolve(N, M, K)
    #print(f"{v}={answer}")



def main():
    #test()
    N, M, K = map(int, input().split())
    v = resolve(N, M, K)
    print(v)


def resolve(N, M, K):
    result = 0
    m1pow = mod_pow(M-1, mod)
    modC = cahched_modC(N-1, mod)
    for k in range(K+1):
        b = m1pow(N-1-k)
        c = modC(N-1, k, mod)
        v =  (b % mod) * (c % mod)
        #print(f"k={k} v={v}")
        result += v
        result %= mod
    
    result *= M
    result %= mod

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import math
def comb(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))



ans = 0

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

Submission status: Time Limit Exceeded

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

import math
def comb(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))



ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int, input().split())
MOD = 998244353

fact = [1]
rfact = [1]
for i in range(1, N+1):
    fact.append(fact[i-1]*i%MOD)
    rfact.append(pow(fact[i], MOD-2, MOD))
 
def cmb(n, m):
    return fact[n]*rfact[m]*rfact[n-m]%MOD

answer = 0
for i in range(K+1):
    answer += M*cmb(N-1,i)*(M-1)**(N-1-i)*1**i
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
R=range
M=998244353
n,m,k=map(int,input().split())
f=1
for i in R(n):f*=i+1
r=[pow(f,M-2,M)]
for i in R(n):r+=r[i]*(n-i)%M,
print(sum(f//n*m*r[i-n]*r[~i]*pow(m-1,~i+n,M)for i in R(k+1))%M)

Submission status: Time Limit Exceeded

Solution code:
R=range
M=998244353
n,m,k=map(int,input().split())
f=1
for i in R(n):f*=i+1
r=[pow(f,-1,M)]
for i in R(n):r+=r[i]*(n-i)%M,
print(sum(f//n*m*r[i-n]*r[~i]*pow(m-1,~i+n,M)for i in R(k+1))%M)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
        y >>= 1
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    ret = m*bpow(m-1, n-1, mod) % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*bpow(m-1, n-1-i, mod)*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

s = 0


c = 1


for i in range(k+1):
    if i > 0:
        c = c * (n-i) // i
    s += c * m * ((m-1) ** (n-1-i))

print(s % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def rpow(x, y, z):
    i = 1
    a = x
    while i*i < y:
        a = (a*a) % z
        i *= 2
    return (a*pow(x, y-i, z)) % z if 0 < y else 1


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    ret = m*rpow(m-1, n-1, mod) % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*rpow(m-1, n-1-i, mod)*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    ret = m*pow(m-1, n-1, mod) % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*pow(m-1, n-1-i, mod)*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
import math

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

s = 0

for i in range(k+1):
    s += (math.factorial(n-1) // (math.factorial(n-1-i) * math.factorial(i)) ) * m * ((m-1) ** (n-i-1))

print(s % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def rpow(x, y, z):
    i = 1
    a = x
    while i*i < y:
        a = (a*a) % z
        i *= 2
    return (a*pow(x, y-i, z)) % z if 0 < y else 1


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    P = [1]*(k+1)
    p = rpow(m-1, n-1-k, mod)
    for i in range(k+1):
        P[-1-i] = p
        p = p*(m-1) % mod

    ret = m*P[0] % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*P[i]*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
from operator import mul
from functools import reduce
n,m,k=map(int,input().split())
total=0

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

for i in range(0,k+1):
    a=combinations_count(n-1,i)%998244353
        
        
    total+=a*m*((m-1)**(n-1-i))%998244353
print(int(total%998244353))

Submission status: Time Limit Exceeded

Solution code:
# from scipy.special import comb # comb(n,k,exact=True). 'exact=True' to return integer.
n, m, k = map(int,input().split())
mod = 998244353

count = 0
count_tmp = m*((m-1)**(n-1))
comb_list = [1,]
comb_tmp = comb_list[0]
for i in range(1,((n-1)//2)+1):
    comb_tmp *= ((n-1)-(i-1))
    comb_tmp = max(comb_tmp, 1)//i
    comb_list.append(comb_tmp)

count += count_tmp*comb_list[0]

if m == 1: # one color
    if k == n-1:
        print(count)
    else:
        print(0)
    exit()

for i in range(1,k+1): # choose pairs and add
    count_tmp //= (m-1)
    if i <= (n-1)//2:
        comb_tmp = comb_list[i]
    else:
        comb_tmp = comb_list[n-1-i]
    count += (count_tmp * comb_tmp)
    # print(count_tmp,comb_tmp,count)
    # print(i,comb_tmp,comb(n-1,i,exact=True),((n-1)-(i-1))%i)
    # if comb_tmp != comb(n-1,i,exact=True):
    #     break

print(count%mod)
# print(479519525)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

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

Ncom = 0
for k in range(K+1):
  n = M * comb(N-1, k, exact=True) * (M-1)**(N-k-1)
  Ncom += n % mod
print(Ncom % mod)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

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

Ncom = 0
for k in range(K+1):
  n = M * comb(N-1, k, exact=True) * (M-1)**(N-k-1)
  Ncom += n
print(Ncom % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fact

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

Ncom = 0
for k in range(K+1):
  n = M * fact(N-1) // fact(N-1-k) // fact(k) * (M-1)**(N-k-1)
  Ncom += n
print(Ncom % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

Ncom = 0
for k in range(K+1):
  n = M * len(list(itertools.combinations(range(N-1), k))) * (M-1)**(N-k-1)
  Ncom += n
print(Ncom % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# from scipy.special import comb # comb(n,k,exact=True). 'exact=True' to return integer.
n, m, k = map(int,input().split())
mod = 998244353

count = 0
count_tmp = m*((m-1)**(n-1))
comb_list = [1,]
comb_tmp = comb_list[0]
for i in range(1,((n-1)//2)+1):
    comb_tmp *= ((n-1)-(i-1))
    comb_tmp = max(comb_tmp, 1)//i
    comb_list.append(comb_tmp)

count += count_tmp*comb_list[0]

if m == 1: # one color
    if k == n-1:
        print(count)
    else:
        print(0)
    exit()

for i in range(1,k+1): # choose pairs and add
    count_tmp //= (m-1)
    if i <= (n-1)//2:
        comb_tmp = comb_list[i]
    else:
        comb_tmp = comb_list[n-1-i]
    count += (count_tmp * comb_tmp)
    # print(count_tmp,comb_tmp,count)
    # print(i,comb_tmp,comb(n-1,i,exact=True),((n-1)-(i-1))%i)
    # if comb_tmp != comb(n-1,i,exact=True):
    #     break

print(count%mod)
# print(479519525)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  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 com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
  n,m,k=LI()
  ans=0
  col=m
  for x in range(n)[::-1]:
    now=col
    now*=com(n-1,x)
    if x<=k:
      ans+=now
      ans%=mod
    col*=m-1
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def pow(x,n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow((x ** 2)%mod, n // 2)%mod
    else:
        return x * pow((x ** 2)%mod, (n - 1) // 2)%mod
A = 1
for i in range(K+1):
    p = N - i
    x = M*pow(M-1,p-1)*A % mod
    ans += x
    A = A*(N-i-1)%mod
    y = pow(i+1,mod-2)
    A = A*y % mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def pow(x,n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow((x ** 2)%mod, n // 2)%mod
    else:
        return x * pow((x ** 2)%mod, (n - 1) // 2)%mod
A = 1
for i in range(K+1):
    p = N - i
    x = M*pow(M-1,p-1)*A % mod
    ans += x
    A *= (N-i-1)
    y = pow(i+1,mod-2)
    A *= y
    A %= mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def caa(m,n):
    x = m * ((m-1) ** (n-1))
    return x

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

for i in range(0,K+1):
    c = combinations_count(N-1,i)
    y = caa(M,(N-i))
    ans += c * y
    ans = ans % 998244353

print('{}'.format(ans))

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class nCrMod():
  def __init__(self,n):
    self.n=n
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=mod
    self.ifact[n]=pow(self.fact[n],mod-2,mod)
    for i in range(1,n+1)[::-1]:
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=mod
  def comb(self,n,k):
    if k<0 or n<k:
      return 0
    return self.fact[n]*self.ifact[k]*self.ifact[n-k]%mod

def main():
  n,m,k=LI()
  c=nCrMod(200005)
  ans=0
  col=m
  for x in range(n)[::-1]:
    now=col
    now*=c.comb(n-1,x)
    if x<=k:
      ans+=now
      ans%=mod
    col*=m-1
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
nCi = [1]

for i in range(1, N+1):
    nCi.append(nCi[i-1]*(N-i) * pow(i, mod-2, mod))


for i in range(min(N, K)+1):
    ans += (M%mod) * pow(M - 1, N-1-i, mod) * nCi[i]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = 998244353
ans = 0

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(r):
        x *= (n - i)
        y *= (i + 1)
        x %= mod
        y %= mod
    return (x * modinv(y, mod)) % mod


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
x,y,z=map(int,input().split())
import math
def f(n,m,k):
    a=(m*(math.factorial(n-1)//(math.factorial(k)*math.factorial(n-k-1))))%998244353
    for i in range(n-k-1):
       a=(a*(m-1))%  998244353   
    return a
A=list()
if z==x:
    print(y)
else:
    for i in range(z+1):
        A.append(f(x,y,i))
    print((sum(A)%998244353))

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m,k = map(int,input().split())
ans = 0
mod = 998244353
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
N = n  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
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)
col = copy.copy(m)
for i in range(n-1,-1,-1):
  now = copy.copy(col)
  now *= cmb(n-1,i,p)
  if i <= k:
    ans = (ans+now)%mod
  col = col*(m-1)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# E - Colorful Blocks
import sys
readline = sys.stdin.readline

MOD = 998244353
N, M, K = map(int, readline().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i] * (i+1) % MOD)

f_inv = [1] * N
f_inv[N-1] = pow(f[N-1], MOD-2, MOD)
for i in range(N-1)[::-1]:
    f_inv[i] = f_inv[i+1] * (i+1) % MOD

# 組み合わせ関数
def comb_mod(n, r, p):
    return (f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p))%p

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i, MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Colorful Blocks
import sys
readline = sys.stdin.readline

MOD = 998244353
N, M, K = map(int, readline().split())

def pow_mod(x, n, mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans = (ans * x)%mod
        x = (x * x)%mod
        n >>= 1
    return ans

f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

def comb_mod(n, r, p):
    return (f[n] * pow_mod(f[r], p-2, p) * pow_mod(f[n-r], p-2, p))%p

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow_mod(M-1, N-1-i, MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Colorful Blocks
import sys
readline = sys.stdin.readline

MOD = 998244353
N, M, K = map(int, readline().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return (f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p))%p

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i, MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Colorful Blocks
import sys
readline = sys.stdin.readline

MOD = 998244353
N, M, K = map(int, readline().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Colorful Blocks

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

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

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

n,m,k = map(int,input().split())
INF=998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]

if m==1:
    if k==n-1:
        print(1)
    else:
        print(0)
else:
    for i in range(2, n):
        fact.append((fact[-1] * i) % INF)
        inv.append((-inv[INF % i] * (INF // i)) % INF)
        factinv.append((factinv[-1] * inv[-1]) % INF)
    p=m*(m-1)**(n-k-1)%INF
    ans=0
    for i in range(0,k+1)[::-1]:
        ans+=cmb(n-1,i,INF)*p%INF
        p*=m-1
    print(int(ans%INF))

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
coef=[1]+[0]*k
inv=[0,1]
INF=998244353
if m==1:
    if k==n-1:
        print(1)
    else:
        print(0)
else:
    for i in range(1,k+1):
        if i==1:
            coef[i]=coef[i-1]*(n-i)%INF
        else:
            inv.append((-(inv[INF%i])*(INF//i)%INF))
            coef[i]=coef[i-1]*(n-i)*inv[-1]%INF
    p=m*(m-1)**(n-k-1)%INF
    ans=0
    for i in range(1,k+2):
        ans+=coef[-i]*p%INF
        p*=m-1
    print(int(ans%INF))

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
coef=[1]+[0]*k
if m==1:
    if k==n-1:
        print(1)
    else:
        print(0)
else:
    for i in range(1,k+1):
        coef[i]=coef[i-1]*(n-i)//i
    p=m*(m-1)**(n-k-1)%998244353
    ans=0
    for i in range(1,k+2):
        ans+=coef[-i]*p%998244353
        p*=m-1
    print(int(ans%998244353))

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

class mod_combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
        
    def calc(self, n, k): # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


n, m, k = map(int, input().split())
C = mod_combination(n)
ans = 0
color = m
for x in reversed(range(n)):
    if x <= k:
        ans += C.calc(n - 1, n - x - 1) * color % mod
        ans %= mod
    color *= m - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class mod_combination:
    def __init__(self, N, mod):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
        
    def calc(self, n, k): # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


n, m, k = map(int, input().split())
mod = 998244353
C = mod_combination(n, mod)
ans = 0
color = m
for x in reversed(range(n)):
    if x <= k:
        ans += C.calc(n - 1, x) * color
        ans %= mod
    color *= m - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod =998244353

def nCr(n,r):
  if r*2>n:
      return nCr(n,n-r)
  else:
      a = b = 1
      for i in range(r):
          a = a * (n - i) % mod
          b = b * (r - i) % mod
      return (a * pow(b,mod-2,mod)) % mod
n,m,k=map(int,input().split())
ans=0
for i in range(0, k+1):
    ans += m * (pow(m-1, n-i-1, mod) %mod)* (nCr(n-1, i) % mod)
    ans%=mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def comb(n, r):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i-1] * i) % mod #n!を計算
    # print('fact:{}'.format(fact))
    revfact = [1] * (n + 1) #逆元を定義
    revfact[n] = pow(fact[n], mod - 2, mod) #n!のmod-2乗を計算
    # print('revfact:{}'.format(revfact))
    for i in reversed(range(1, n)): #N-1から1まで
        revfact[i] = ((i + 1) * revfact[i + 1]) % mod
    # print('revfact:{}'.format(revfact))

    return (fact[n] * revfact[n-r] * revfact[r]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def fact(n):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i-1] * i) % mod #n!を計算
    return fact[n]

def revfact(n):
    revfact = [1] * (n + 1) #逆元を定義
    revfact[n] = pow(fact(n), mod - 2, mod) #n!のmod-2乗を計算
    for i in reversed(range(1, n)): #N-1から1まで
        revfact[i] = ((i + 1) * revfact[i + 1]) % mod
    return revfact[n]

def comb(n, r):
    return (fact(n) * revfact(n-r) * revfact(r)) % mod

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

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

Submission status: Time Limit Exceeded

Solution code:
import math


# class Comb:
#     m_vals = []
#     _mod = 998244353
#
#     def __init__(self, n: int, r: int):
#         m_ls = [(0, 1)] * (r + 1)
#         for i in range(1, r):
#             x = (m_ls[i - 1][0] * self._mod + m_ls[i - 1][1]) * (n - r / r)
#             if x >= self._mod:
#                 m_ls[i] = (int(x // self._mod), int(x % self._mod))
#             else:
#                 m_ls[i] = (0, int(x))
#         self.m_vals = m_ls
#
#     def vv(self, x):
#         return self.m_vals[x][1]

def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


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

    _mod = 998244353
    _mod2 = 998244351

    # res_x = m * ((m-1) ** (n-1-x)) * comb(n-1, x)
    # x:0, 2, ... , k
    # xをk->0とすると(m-1) ** (n-1-x)は少しずつかけていける

    # com = Comb(n - 1, k)
    comb_ar = create_array(n-1, k, _mod, _mod2)
    _z = (m - 1) ** (n - 1 - k)
    res = m * _z * comb_ar[k]
    res %= _mod

    if k > 0:
        for x in range(1, k + 1):
            _z *= m - 1
            res += m * _z * comb_ar[k - x]
            res %= _mod

    # res %= _mod

    print(res)
    #
    #
    #
    # for x in range(1, k+1):
    #     res += m * (_z * (m-1) ** x) * comb(n-1, x)
    #
    # _a_n = ((m - 1) ** (n - 1 - k)) % _mod
    # _b_n = 1
    # _c_n = 1
    # _d_n = 1
    #
    # _a = [_a_n]
    # _b = [_b_n]
    # # _c = [_c_n]
    # _d = [_d_n]
    # for i in range(1, k + 1):
    #     _a_n *= m - 1
    #     _a_n %= _mod
    #     _a.append(_a_n)
    #     _b_n *= n - i
    #     _b_n %= _mod
    #     _b.append(_b_n)
    #     _c_n *= i
    #     _d_n = (_c_n ** (_mod - 2)) % _mod
    #     _d.append(_d_n)
    #
    # _a.reverse()
    #
    # if k == 0:
    #     res = m * ((m - 1) ** (n - 1))
    #     print(res % _mod)
    # else:
    #     res = (m * ((m - 1) ** (n - 1))) % _mod
    #     for i in range(1, k + 1):
    #         res += (m * _a[i - 1] * _b[i - 1] * _d[i - 1]) % _mod
    #
    #     print(res % _mod)
    #
    # # res_k = m * ((m-1) ** (n-1-k)) * comb(n-1,k)
    # #
    # # for i in range(1, k + 1):
    # #     z_c *= (n-i)
    # #     z_p *= i
    # #     z_c %= _mod
    # #     z_p %= _mod
    # #
    # #     if z_c % z_p == 0:
    # #         comb_ls.append(int(z_c/z_p))
    # #     else:
    # #         for j in range(1, n-1):
    # #             _ = z_c + j * _mod
    # #             if _ % z_p == 0:
    # #                 comb_ls.append(int(_/z_p))
    # #
    # #
    # # comb_ls.reverse()
    # # for i in range(1, k + 1):
    # #     j = k + 1 - i
    # #
    # #     z_before *= (m-1)
    # #     res_x += (m * comb_ls[i-1] * z_before) % 998244353
    # #
    # # print(res_x % _mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
    mod = 998244353
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result = result % mod
    return result

n,m,K = map(int,input().split())
MOD = 998244353
ans = 0
for k in range(K+1):
    aa = cmb(n-1,k)
    bb = pow(m-1,n-k-1,MOD) * m
    ans += (aa*bb)%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul #掛け算をする関数
from functools import reduce

# def cmb(n,r):
#     r = min(n-r,r) #nCrとnCn-rは等しいので小さい方を選ぶ
#     if r == 0: return 1 #nC0 = 1より
#     over = reduce(mul, range(n, n - r, -1))
#     under = reduce(mul, range(1,r + 1))
#     return over // under

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N, M, K = map(int, input().split())
ans = 0
col = M
mod = 998244353

for i in range(N)[::-1]:
    now = col
    # print('i:{}'.format(i))
    # print('col:{}'.format(col))
    now *= cmb(N-1,i)
    # print('cmb:{}'.format(cmb(N-1, i)))
    if i <= K:
        ans += now
        # print('\ni:{} now:{} ans:{}'.format(i, now, ans))
    col *= M-1

print(ans%mod)

Submission status: Time Limit Exceeded

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

def conv_mod(n,k,P): #nCk mod P
    if (n-k) < k:
        k = n-k
    fact = [1]*(n+1) #階乗
    inv = [1]*(n+1) #逆元
    fact_inv = [1]*(n+1) #階乗の逆元
    for i in range(2,n+1):
        fact[i] = fact[i-1]*i%P
        inv[i]  = P - inv[P%i]*(P//i)%P
        fact_inv[i] = fact_inv[i-1]*inv[i]%P
    return fact[n]*fact_inv[k]*fact_inv[n-k]%P
  
P = 998244353
ans = 0
tmp = (M-1)**(N-K-1) % P
Mr = M % P
for x in range(K,-1,-1):
#    ans += M*(M-1)**(N-x-1)*conv_mod(N-1,x,P) % P
    ans += tmp*conv_mod(N-1,x,P) % P
    tmp *= M-1
ans *= Mr
ans %= P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = [int(x) for x in input().split()]

MOD = 998244353
import sys
sys.setrecursionlimit(1000000000)
# メモ化再起
from functools import lru_cache

@lru_cache(maxsize=1000000000000)
def f(n, k):
    # print(f"{n}, {k}")
    if n == k:
        return 0
    if k < 0:
        return 0
    if n == 1:
        if k == 0:
            return M
        else:
            return 0

    ret = f(n-1, k) * (M-1) + f(n-1, k-1)
    # print(f"{n}, {k} --> {ret}")
    return ret % MOD


s = 0
for i in reversed(range(K+1)):
    s += f(N,i)
    s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = [int(x) for x in input().split()]

MOD = 998244353
import sys
sys.setrecursionlimit(100000000)
# メモ化再起
from functools import lru_cache

@lru_cache(maxsize=1000000)
def f(n, k):
    # print(f"{n}, {k}")
    if n == k:
        return 0
    if k < 0:
        return 0
    if n == 1:
        if k == 0:
            return M
        else:
            return 0

    ret = f(n-1, k) * (M-1) + f(n-1, k-1)
    # print(f"{n}, {k} --> {ret}")
    return ret % MOD


s = 0
for i in reversed(range(K+1)):
    s += f(N,i)
    s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

def C(n, r, m):
    num, den = 1, 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) % m
        den = den * i % m
    return (num * pow(den, m - 2, m)) % m

n, m, k = map(int, input().split())
cnt = 0
for x in range(k + 1):
    cnt += m * pow(m - 1, n - 1 - x, MOD) * C(n - 1, x, MOD)
    cnt %= MOD
print(cnt)