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:
def main():
    N, M, K = map(int, input().split())

    fac = [0] * (N + 1)
    fac[0] = 1
    for i in range(N):
        fac[i + 1] = fac[i] * (i + 1) % 998244353

    def mcomb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += M * mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split(" "))
expm_1 = [0 for _ in range(N + 1)]
expm_1[0] = 1
ncr = [0 for _ in range(N + 1)]
ncr[0] = 1
ans = 0
 
for i in range(N):
    expm_1[i + 1] = (expm_1[i] * (M - 1)) % 998244353
for i in range(N - 1):
    ncr[i + 1] = ncr[i] * (N - i - 1) // (i + 1)
for i in range(K + 1):
    ans += M * expm_1[N - 1 - i] * ncr[i]
    ans %= 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def ncr(n,r,p):
    num = den = 1
    for i in range(r):
        num = (num * (n-i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p-2, p)) % p

n,m,k = (int(x) for x in input().split())
p = 998244353
ans = 0
for i in range(k+1):
    ans += m*pow(m-1, n-i-1,p) * ncr(n-1,i,p)
    if ans > p:
        ans = ans % p 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def ncr(n,r,p):
    num = den = 1
    for i in xrange(r):
        num = (num * (n-i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p-2, p)) % p

n,m,k = (int(x) for x in input().split())
p = 998244353
ans = 0
for i in xrange(k+1):
    ans += m*pow(m-1, n-i-1,p) * ncr(n-1,i,p)
    ans = ans % p 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ans=0
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
for kk in range(k+1):
  anss=m*pow(m-1,n-1-kk,mod)%mod
  anss=anss*comb(n-1,kk)%mod
  ans=(ans+anss)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [(f := 1) if not i else (f := f * i % MOD) for i in range(FACT_MAX)]
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N, M, K = map(int, input().split())
total = 0
for k in range(K + 1):
    total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)

Submission status: Time Limit Exceeded

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
for i in range(1,x+1):
    n_c_i.append(n_c_i[-1]*(n-i)//i)
#print(n_c_i)
pow_k=pow(k-1,n-1,od)
inv_k=pow(k-1,od-2,od)
ans=0
#print(ans)
for i in range(x+1):
        
    #pow_k=(pow_k*inv_k)%od
    p_k=(k*pow(k-1,n-i-1,od))%od
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*p_k)%od
    ans%=od

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [(f := 1 if not i else (f := f * i % MOD)) for i in range(FACT_MAX)]
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N, M, K = map(int, input().split())
total = 0
for k in range(K + 1):
    total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)

Submission status: Time Limit Exceeded

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

def comb(a, b):
    global mod
    l, r = 1, 1
    for i in range(b):
        l = l*(b-i)%mod
        r = r*(a-i)%mod
    return (r*pow(l, mod-2, mod))%mod

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

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        if MOD < cnt:
	        cnt %= MOD

    print(cnt)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        cnt %= MOD

    print(cnt)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#E
n,m,k = list(map(int,input().split()))
fac = [1]*n
finv = [1]*n
inv = [1]*n
MOD = 998244353
for i in range(2,n):
    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):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

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

Submission status: Time Limit Exceeded

Solution code:
#E
n,m,k = list(map(int,input().split()))
fac = [1 for i in range(n)]
finv = [1 for i in range(n)]
inv = [1 for i in range(n)]
MOD = 998244353
for i in range(2,n):
    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):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += (comb(n-1,i)*m*((m-1)**(n-i-1)%MOD))%MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#E
n,m,k = list(map(int,input().split()))
fac = [1,1]
finv = [1,1]
inv = [1,1]
MOD = 998244353
for i in range(2,n):
    fac.append(fac[i-1]*i%MOD)
    inv.append(MOD-inv[MOD%i]*(MOD//i)%MOD)
    finv.append(finv[i-1]*inv[i]%MOD)
def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans = (ans+(comb(n-1,i)*(m*(m-1)**(n-i-1)%MOD)))%MOD
print(ans)

Submission status: Time Limit Exceeded

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

L = [1 for i in range(n)]
for i in range(1, n):
  L[i] = L[i-1] * (m-1) % MOD
s = L[-1]
c = 1
for i in range(1, k + 1):
  c = c * (n-i) // i
  s += L[n-1-i] * c % MOD

s = s * m % MOD
print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

facs = [1] * N
nfac = 1
for i in range(1, N):
    nfac = nfac * i % mod
    facs[i] = nfac

s = 0
for i in range(K+1):
    d = facs[N-1] * pow(facs[i], mod-2, mod) * pow(facs[N-1-i], mod-2, mod) \
        * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)

Submission status: Time Limit Exceeded

Solution code:
#E
n,m,k = list(map(int,input().split()))
fac = [1 for i in range(n)]
finv = [1 for i in range(n)]
inv = [1 for i in range(n)]
MOD = 998244353
for i in range(2,n):
    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):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += (comb(n-1,i)*(m*(m-1)**(n-i-1)%MOD))%MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

facs = [1] * (N + 1)
nfac = 1
for i in range(1, N):
    nfac = nfac * i %mod
    facs[i] = nfac

s = 0
for i in range(0, K+1):
    patterns = facs[N-1] * pow(facs[i], mod-2, mod) * pow(facs[N-1-i], mod-2, mod) % mod
    d = patterns * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)

Submission status: Time Limit Exceeded

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

facs = [1]        
nfac = 1
for i in range(1, N):
    nfac = nfac * i %mod
    facs.append(nfac)

s = 0
for i in range(0, K+1):
    patterns = facs[N-1] * pow(facs[i], mod-2, mod) * pow(facs[N-1-i], mod-2, mod) % mod
    d = patterns * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s % mod)

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):
    nCi.append(nCi[i-1]*(N-i)//i)


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

li = [0]*(n+1)
for i in range(n+1):
    li[i] = combination(n-1,i)%mod

for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod
    now *= li[i]%mod
    if i <= k:
        point += now%mod

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
MAX_N = 2 * (10**5)

fact = [1]
fact_inv = [0] * (MAX_N + 4)

for i in range(MAX_N + 3):
    fact.append(fact[-1]*(i+1)%mod)

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

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

ans = 0
col = M

for k in range(N-1, -1, -1):
    now = col
    now *= cmb(N-1,k,mod)
    if k <= K:
        ans += now
    ans %= mod
    col *= M-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def get_input(data_type, container_type=list):
    return container_type(data_type(x) for x in input().split())


MOD = 998244353
N, M, K = get_input(int)

import functools
import sys

sys.setrecursionlimit(100000000)


@functools.lru_cache(None)
def dp(n, k):
    if n == 0:
        return 1
    if k < 0:
        return 0

    v = dp(n - 1, k) * (M - 1) + dp(n - 1, k - 1)
    return v % MOD


sol = dp(N, K)
print(sol)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

li = [0]*(n+1)
for i in range(n+1):
    li[i] = combination(n-1,i)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= li[i]
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)%mod
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from numba import jit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

@jit
def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)
    if i <= k:
        point += now%mod
    col *= m-1
    col %= mod

print(point%mod)

Submission status: Time Limit Exceeded

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

mod=998244353

dp=[[0]*(k+1) for _ in range(n+1)]
dp[1][0]=m

for i in range(2,n+1):
    for j in range(k+1):
        dp[i][j]=((dp[i-1][j]*(m-1))%mod + dp[i-1][j-1]*(j!=0))%mod

ans=0
for j in range(k+1):
    ans+=dp[-1][j]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0] * (K + 2) for _ in range(N)]

x = 998244353
dp[0][0] = M
for j in range(1, N):
    for i in range(K + 1):
        dp[j][i + 1] += dp[j - 1][i] % x
        dp[j][i] += dp[j - 1][i] * (M - 1) % x
ans = 0
for i in range(K + 1):
    ans += dp[N - 1][i]
    ans %= x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from numba import jit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

@jit
def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)
    if i <= k:
        point += now%mod
    col *= m-1

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
MAX = 10 ** 5 * 2
mod = 998244353
frac = [1]
for i in range(1,MAX + 1 ):
    frac.append( (frac[-1] * i) % mod )
def pow(a, n):
    if n == 0 : return  1
    elif n == 1 : return a
    tmp = pow(a, n//2)
    tmp = (tmp * tmp) % mod
    if n % 2 == 1 :
        tmp = (tmp * a) % mod
    return tmp
def inv(x):
    return pow(x, mod - 2 )
def comb(n, k):
    if k >= n or k < 0 : return 1
    return (frac[n] * inv(frac[n-k]) * inv(frac[k]))%mod
N,M,K=map(int,input().split())
a=comb(N-1,K)
b=pow(M-1,N-1)
for i in range(1,K+1):
    b+=(pow(M-1,N-1-i)*comb(N-1,i))%mod
    b=b%mod
print((M*b)%mod)

Submission status: Time Limit Exceeded

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

fac = [0] * (N + 1)
finv = [0] * (N + 1)
inv = [0] * (N + 1)

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

cmb = [1]
cur = 1
for i in range(1, N):
    x = cur * (N - i) * inv[i]
    x %= MOD
    cur = x
    cmb.append(x)

now = pow(M - 1, N - K - 1, MOD)
ans = 0
for x in range(K, -1, -1):
    ans = (ans + cmb[N - 1 - x] * M * now) % MOD
    now *= (M - 1) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    if i <= k:
        now *= combination(n-1,i)%mod
        now *= wariate%mod
        point += now

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from numba import jit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

@jit
def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

for i in range(n-1,-1,-1):
    now = 1
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    if i <= k:
        now *= m%mod
        now *= combination(n-1,i)%mod
        now *= wariate%mod
        point += now

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
if (n-1==k):
    print(m**m)
    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

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

Submission status: Time Limit Exceeded

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

fac = [0] * (N + 1)
finv = [0] * (N + 1)
inv = [0] * (N + 1)

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    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


def Power(a, x):
    ret = 1
    while x > 0:
        ret = ret * a % MOD
        x -= 1
    return ret


now = Power(M - 1, N - K - 1)
ans = 0
for x in range(K, -1, -1):
    ans = (ans + Comb(N - 1, x) * M * now) % MOD
    now *= (M - 1) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

for i in range(n-1,-1,-1):
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    if i <= k:
        point += m*combination(n-1,i)*wariate%mod
print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

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

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
def pre_cmb(N, MOD):
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 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)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD


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

m_exp = [1]
for i in range(1, n):
    m_exp.append(m_exp[i - 1] * (m - 1))
prelist = pre_cmb(n, mod)

cnt = 0
for i in range(k + 1):
    cnt += (m * m_exp[n - i - 1] * cmb(n - 1, i, mod, prelist))

print(cnt % mod)

Submission status: Time Limit Exceeded

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

def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
dp = [0]*(k+1)
dp[0] = m* modpow(m-1, n-1, MOD) % MOD
for j in range(1, k+1):
  bunsi = 1
  for i in range(n-1-j+1, n):
    bunsi = bunsi * i % MOD

  bunbo = 1
  for i in range(1, j+1):
    bunbo = bunbo * i % MOD

  comb = bunsi * modpow(bunbo, MOD-2, MOD) % MOD
  dp[j] = (m * modpow(m-1, n-1-j, MOD)*comb % MOD + dp[j-1]) % MOD
print(dp[k])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def f(N, M, k, mf):
    '''
    >>> mf = ModFactorial(MOD, 10)
    >>> f(3, 2, 0, mf)
    2
    >>> f(3, 2, 1, mf)
    4
    >>> f(3, 2, 2, mf)
    2
    >>> f(4, 2, 0, mf)
    2
    >>> f(4, 2, 1, mf)
    6
    >>> f(4, 3, 0, mf)
    24
    >>> f(4, 3, 1, mf)
    36
    '''
    if k == N:
        return M
    base = M * pow(M-1, N-k-1, MOD) % MOD
    return base * mf.combination(N-1, k) % MOD


def solve(N: int, M: int, K: int):
    mf = ModFactorial(MOD, N)
    ans = 0
    for k in range(K+1):
        ans = (ans + f(N, M, k, mf)) % MOD
    return ans


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    print(solve(N, M, K))

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % mod

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
    
    def mod_inv(self, n):
        return mod_inv(self._mod, n)
    
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 # リストの参照は遅いので減らす
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self.mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        >>> ModFactorial(1000000007).permutation(10, 0)
        1
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        >>> ModFactorial(1000000007).combination(10, 0)
        1
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

if M == 1:
    if N-1 <= K:
        print(1)
    else:
        print(0)
    exit()

ans = 0
fn = 1
fk = 1
a = M * (M-1)**N
for k in range(K+1):
    n = N - k
    a //= M-1
    if k == 0:
        b = 1
    else:
        fn *= N-k
        fk *= k
        b = fn // fk
    ans += a * b
    ans %= 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,k = mp()

def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


mod = 998244353
now_comb = 1
now_pow = pow(m-1, n-1, mod)
ans = now_pow*m
for i in range(1, k+1):
    # u1 = (now_comb * (n-i) * pow(i, mod-2, mod)) % mod
    u1 = combination(n-1, i, mod)
    u2 = (now_pow * pow(m-1, mod-2, mod)) % mod
    now_comb = u1
    now_pow = u2
    ans += u1*u2*m
    ans %= mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
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
for t in range(K+1):
    temp = M*pow(M-1,N-t-1,998244353)
    temp = temp*cmb(N-1, t)%998244353
    ans = (ans+temp)%998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from scipy.special import comb
N, M, K= map(int, input().split())

div = 998244353


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

t = N-1-K
score = 0
for nd in range(N):
    if N-1-nd > K:
        continue
    b = nd + 1
    s = M * pow(M-1, b-1)
    mul = comb(N-1, nd)

    score += s*mul

print(score%div)