Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03098 (python)

Fixed submission:
from operator import itemgetter


def get_identity():
    return list(range(1, n + 1))


def composition(ppp, qqq):
    return [ppp[q - 1] for q in qqq]


def reverse_composition(ppp, qqq):
    return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))]


def solve(k, ppp, qqq):
    qp = reverse_composition(qqq, ppp)
    qpq = reverse_composition(qp, qqq)
    qpqp = composition(qpq, ppp)
   
    l, m = divmod(k - 1, 6)
    res = get_identity()
    tmp = qpqp
    while l:
        if l % 2 == 1:
            res = composition(res, tmp)
        tmp = composition(tmp, tmp)
        l >>= 1

    m = (k - 1) % 6
    if m == 0:
        base = ppp
    elif m == 1:
        base = qqq
    elif m == 2:
        base = reverse_composition(qqq, ppp)
    elif m == 3:
        res = composition(res, qqq)
        base = reverse_composition(get_identity(), ppp)
    elif m == 4:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
    elif m == 5:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
        base = composition(base, ppp)
    else:
        raise NotImplementedError

    ans = composition(res, base)
    ans = reverse_composition(ans, res)
    return ans


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

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
ini_p = ppp.copy()
ini_q = qqq.copy()
i = 0
for i in range(k - 2):
    rrr = [q for p, q in sorted(zip(ppp, qqq))]
    if rrr == ini_p:
        break
    ppp = qqq
    qqq = rrr
else:
    print(*qqq)
    exit()

k = k % (i + 2)
ppp = ini_p
qqq = ini_q
for i in range(k - 2):
    rrr = [q for p, q in sorted(zip(ppp, qqq))]
    ppp = qqq
    qqq = rrr
print(*qqq)
Problem p03208 (python)

Fixed submission:
n, k = map(int, input().split())
hhh = [int(input()) for _ in range(n)]
hhh.sort()
ans = float('inf')
for i in range(n - k + 1):
    ans = min(ans, hhh[i + k - 1] - hhh[i])
print(ans)

Buggy submission (verdict: Runtime Error):
from operator import sub

n, k = map(int, input().split())
hhh = sorted(int(input()) for _ in range(n))
print(min(map(sub, zip(hhh[k - 1:], hhh))))
Problem p03346 (python)

Fixed submission:
n = int(input())
ppp = list(map(int, (input() for _ in range(n))))

tmp_f = {}
for p in ppp:
    if p - 1 in tmp_f:
        tmp_f[p] = tmp_f[p - 1] + 1
    else:
        tmp_f[p] = 1

# tmp_b = {}
# for p in ppp[::-1]:
#     if p + 1 in tmp_b:
#         tmp_b[p] = tmp_b[p + 1] + 1
#     else:
#         tmp_b[p] = 1

cnt = max(tmp_f.values())
print(n - cnt)

Buggy submission (verdict: Runtime Error):
n = int(input())
ppp = list(map(int, (input() for _ in range(n))))

tmp = [0] * n
for p in ppp:
    tmp[p] = tmp[p - 1] + 1

print(n - max(tmp))
Problem p03776 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10000)


def memoize(f):
    cache = {}

    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    return func


@memoize
def combi(n, r):
    if r == 0 or n == r:
        return 1
    return combi(n - 1, r - 1) + combi(n - 1, r)


n, a, b = map(int, input().split())
items = sorted(map(int, input().split()), reverse=True)
max_ave_list = items[:a]
print(sum(max_ave_list) / len(max_ave_list))

m = max_ave_list.count(max_ave_list[-1])
l = items.count(max_ave_list[-1])
if l == m:
    print(1)
elif max_ave_list[0] != max_ave_list[-1]:
    print(combi(l, m))
else:
    print(sum(combi(l, k) for k in range(m, min(b, l) + 1)))

Buggy submission (verdict: Runtime Error):
def memoize(f):
    cache = {}

    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    return func


@memoize
def combi(n, r):
    if r == 0 or n == r:
        return 1
    return combi(n - 1, r - 1) + combi(n - 1, r)


n, a, b = map(int, input().split())
items = sorted(map(int, input().split()), reverse=True)
max_ave_list = items[:a]
print(sum(max_ave_list) / len(max_ave_list))

m = max_ave_list.count(max_ave_list[-1])
l = items.count(max_ave_list[-1])
if l == m:
    print(1)
elif max_ave_list[0] != max_ave_list[-1]:
    print(combi(l, m))
else:
    print(sum(combi(l, k) for k in range(m, max(b, l) + 1)))
Problem p02552 (python)

Fixed submission:
x = int(input())
print(x^1)

Buggy submission (verdict: Runtime Error):
#include<bits/stdc++.h>
using namespace std;

#define int long long

int mod = 1000000007;

// #include "debug.cpp"

int dp[1000010][4];

int32_t main(){
	int n;
	cin >> n;

	if(n == 1){
		cout << "0\n";
		return 0;
	}

	dp[2][0] = 64;
	dp[2][1] = 17;
	dp[2][2] = 17;
	dp[2][3] = 2;

	for(int i=3; i<=n; i++){
		dp[i][0] = dp[i-1][0]*8;
		dp[i][1] = dp[i-1][0] + dp[i-1][1]*9;
		dp[i][2] = dp[i-1][0] + dp[i-1][2]*9;
		dp[i][3] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3]*10;

		dp[i][0] %= mod;
		dp[i][1] %= mod;
		dp[i][2] %= mod;
		dp[i][3] %= mod;
	}

	cout << dp[n][3] << "\n";
}
Problem p02577 (python)

Fixed submission:
s = input()
ans = 0
for x in s:
	ans += int(x)

if ans%9 == 0:
	print("Yes")
else:
	print("No")

Buggy submission (verdict: Runtime Error):
s = input()
ans = 0
for x in s:
  ans += int(x)
if x%9 == 0:
  print("Yes")
else:
  print("No")
Problem p02793 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000000)
def gcd(a,b): 
    if (b == 0): 
         return a 
    return gcd(b, a%b) 


mod = 10**9 + 7

n = int(input())
arr = [int(j) for j in input().split()]

prod = 1
l = 1
for x in arr:
	g = gcd(l, x)
	prod = l*x
	l = prod//g

su = 0
for x in arr:
	su += (l//x)
print(su%mod)

Buggy submission (verdict: Runtime Error):
from math import gcd
mod = 10**9 + 7

n = int(input())
arr = [int(j) for j in input().split()]

# prod = 1
# l = 1
# for x in arr:
# 	g = gcd(l, x)
# 	prod = l*x
# 	l = prod//g

# su = 0
# for x in arr:
# 	su += (l//x)
# print(su%mod)

Buggy submission (verdict: Runtime Error):
from math import gcd
mod = 10**9 + 7
n = int(input())
arr = [int(j) for j in input().split()]

prod = 1
l = 1
for x in arr:
	g = gcd(l, x)
	prod = l*x
	l = prod//g

su = 0
for x in arr:
	su += (l//x)
print(su%mod)

Buggy submission (verdict: Runtime Error):
from math import gcd

n = int(input())
arr = [int(j) for j in input().split()]

prod = 1
l = 1
for x in arr:
	g = gcd(l, x)
	prod = l*x
	l = prod//g
	# print(l)

su = 0

for x in arr:
	su += (l//x)
print(su%(10**9 + 7))
Problem p02970 (python)

Fixed submission:
import math
n, d = map(int, input().split())
x = 2*d + 1
print(int(math.ceil(n/x)))

Buggy submission (verdict: Runtime Error):
import math
n, d = map(int, input().split())
x = 2*n + 1
print(int(math.ceil(n/x))
Problem p02594 (python)

Fixed submission:
x = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
x = int(input())
if x => 30:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
x = input()
if x => 30:
  print("Yes")
else:
  print("No")
Problem p02779 (python)

Fixed submission:
def check(seq):
    return len(seq) != len(set(seq))

def main():
  N = int(input())
  A = list(map(int, input().split()))
  ans = check(A)
  if ans:
    print("NO")
  else:
    print("YES")
main()

Buggy submission (verdict: Runtime Error):
def check(seq):
    return len(seq) != len(set(seq))

def main():
  N = int(input())
  A = list(map(int, input.split()))
  ans = check(A)
  if ans:
    print("NO")
  else:
    print("Yes")
main()
Problem p02935 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
if N == 2:
  print(sum(A)/2)
  exit()
else:
  temp = (A[0]+A[1])/2
  for i in range(2, N):
    temp = 1/2*(A[i] + temp)
print(temp)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
if N == 2:
  print(sum(A)/2)
else:
  temp = (A[0]+A[1])/2
  for i in range(2, N):
    temp = 1/2*(A[i] + temp)
print(temp)
Problem p02623 (python)

Fixed submission:
# author:  Taichicchi
# created: 15.09.2020 21:14:18

import sys

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

A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0]
b = [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans = 0
j = M

for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
N, M, K = map(int, input().split())

A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

cum_A = np.cumsum(A)
cum_B = np.cumsum(B)

a = 0
b = 0

flg = False

ans = 0

if cum_A[N] + cum_B[M] <= K:
    ans = N + M
else:
    while True:
        if cum_A[a] <= cum_B[b]:
            if (a < N) & (cum_A[a + 1] + cum_B[b] <= K):
                a += 1
            else:
                flg = True
        elif cum_A[a] > cum_B[b]:
            if (b < M) & (cum_A[a] + cum_B[b + 1] <= K):
                b += 1
            else:
                flg = True
        
        if flg:
            ans = a + b
            break


print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
N, M, K = map(int, input().split())

A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

cum_A = np.cumsum(A)
cum_B = np.cumsum(B)

a = 0
b = 0

flg = False

if cum_A[N] + cum_B[M] <= K:
    ans = N + M
else:
    while True:
        if cum_A[a] <= cum_B[b]:
            if (a < N) & (cum_A[a + 1] + cum_B[b] <= K):
                a += 1
            else:
                flg = True
        elif cum_A[a] > cum_B[b]:
            if (b < M) & (cum_A[a] + cum_B[b + 1] <= K):
                b += 1
            else:
                flg = True
        
        if flg:
            ans = a + b
            break


print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
N, M, K = map(int, input().split())

A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

cum_A = np.cumsum(A)
cum_B = np.cumsum(B)

a = 0
b = 0

flg = False

if cum_A[N] + cum_B[M] <= K:
    ans = N + M
elif cum_A[N - 1] + cum_B[M] <= K:
    ans = N + M - 1
elif cum_A[N] + cum_B[M - 1] <= K:
    ans = N + M - 1
else:
    while True:
        if cum_A[a] <= cum_B[b]:
            if cum_A[a + 1] + cum_B[b] <= K:
                a += 1
            else:
                flg = True
        elif cum_A[a] > cum_B[b]:
            if cum_A[a] + cum_B[b + 1] <= K:
                b += 1
            else:
                flg = True
        
        if flg:
            ans = a + b
            break

print(ans)
Problem p02629 (python)

Fixed submission:
# author:  Taichicchi
# created: 15.09.2020 21:11:53

import sys

N = int(input())
ans = ''
while N > 0:
    N -= 1
    ans += chr(ord('a') + N % 26)
    N //= 26
print(ans[::-1])

Buggy submission (verdict: Runtime Error):
# author:  Taichicchi
# created: 15.09.2020 21:11:53

import sys

N = int(input())
ans = ''
while N > 0:
N -= 1
ans += chr(ord('a') + N % 26)
N //= 26
print(ans[::-1])
Problem p03017 (python)

Fixed submission:
N, A, B, C, D = map(int, input().split())

S = list(input().split()[0])

result = "Yes"
flag = False

for i in range(B, D - 1):
    if S[i] == "#" and S[i + 1] == "#":
        result = "No"
        print(result)
        flag = True
        break
if not flag:
    for i in range(A, C - 1):
        if S[i] == "#" and S[i + 1] == "#":
            result = "No"
            print(result)
            flag = True
            break

if not flag:    
    if A < B and B < D and D < C:
        for i in range(B - 2, D - 1):
            if S[i] == "." and S[i + 1] == "." and S[i + 2] == ".":
                result = "Yes"
                print(result)
                flag = True
                break
            else:
                result = "No"
                flag = False
if not flag:
    print(result)

Buggy submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())

S = list(input().split()[0])

result = "Yes"

if C < D:
    for i in range(B, D - 1):
        if S[i] == "#" and S[i + 1] == "#":
                result = "No"
                print(result)
                break
else:
    for i in range(B, C - 1):
        if S[i] == "#" and S[i + 1] == "#":
                result = "No"
                print(result)
                flag = True
                break
    if not flag:
        for i in range(B - 1, C - 2):
            if S[i] == "." and S[i + 1] == "." and S[i + 2] == ".":
                print("Yes")
                break
Problem p03127 (python)

Fixed submission:
# author:  Taichicchi
# created: 14.09.2020 22:18:44

import sys
from math import gcd

N = int(input())

A = list(map(int, input().split()))

ans = gcd(A[0], A[1])
for i in range(2, N):
    ans = gcd(ans, A[i])

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

from functools import reduce
import math

R = reduce(math.gcd,A)

print(int(R))

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

from functools import reduce
import math

R = reduce(math.gcd,A)

print(R)
Problem p03013 (python)

Fixed submission:
import sys


input = sys.stdin.readline

N, M = map(int, input().split())
has_broken = [1]*(N+1)
for _ in range(M):
    has_broken[int(input())] = 0

dp = [1]*(N+1)
dp[1] = 1 if has_broken[1] == 1 else 0
MOD = 10**9+7
for i in range(2, N+1):
    dp[i] = has_broken[i]*(dp[i-1] + dp[i-2])

print(dp[N]%MOD)

Buggy submission (verdict: Runtime Error):
import sys


input = sys.stdin.readline

N, M = map(int, input().split())
has_broken = [False]*(N+3)
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True

dp = [0]*(N+3)
dp[2] = 1
MOD = 10**9+7
for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += (dp[i-1] + dp[i-2])%MOD

print(dp[N+2])

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
has_broken = [True, True, False] + [False for _ in range(N)]
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    # 壊れているのが連続していたら上がれない
    if prev_a == a+1:
        print(0)
        exit(0)
    has_broken[a+2] = True


# dp[i] := i段目にたどり着く移動方法の総数
# 一歩で1段か2段上れるのだから、dp[i]は前段と前々段へたどり着く方法の和
# dp[i] = dp[i-1] + dp[i-2]
# dp配列は-1段目と-2段目の分大きくなっています
dp = [0 for _ in range(N+3)]
# 一段目初期化
dp[2] = 1

for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += dp[i-1] + dp[i-2]

print(dp[N+2]%1000000007)
Problem p03053 (python)

Fixed submission:
H, W = map(int, input().split())

has_visited = [[True]*(W+2)]
has_visited += [[True] + [m == "#" for m in input().rstrip()] + [True] for _ in range(H)]
has_visited += [[True]*(W+2)]

search_que = []
for y in range(1, H+1):
    for x in range(1, W+1):
        if has_visited[y][x]:
            search_que.append((y, x))

count = -1
while search_que:
    count += 1
    next_que = []
    for y, x in search_que:
        if not has_visited[y+1][x]:
            has_visited[y+1][x] = True
            next_que.append((y+1, x))
        if not has_visited[y-1][x]:
            has_visited[y-1][x] = True
            next_que.append((y-1, x))
        if not has_visited[y][x+1]:
            has_visited[y][x+1] = True
            next_que.append((y, x+1))
        if not has_visited[y][x-1]:
            has_visited[y][x-1] = True
            next_que.append((y, x-1))
    search_que = next_que

print(count)

Buggy submission (verdict: Runtime Error):
from collections import deque


H, W = map(int, input().split())

has_visited = [[True]*(W+2)]
has_visited += [[True] + [m == "#" for m in input().rstrip()] + [True] for _ in range(H)]
has_visited += [[True]*(W+2)]

search_que = deque()
for y in range(1, W+1):
    for x in range(1, H+1):
        if has_visited[y][x]:
            search_que.append((y, x))

count = -1
while search_que:
    count += 1
    next_que = deque()
    for y, x in search_que:
        if not has_visited[y+1][x]:
            has_visited[y+1][x] = True
            next_que.append((y+1, x))
        if not has_visited[y-1][x]:
            has_visited[y-1][x] = True
            next_que.append((y-1, x))
        if not has_visited[y][x+1]:
            has_visited[y][x+1] = True
            next_que.append((y, x+1))
        if not has_visited[y][x-1]:
            has_visited[y][x-1] = True
            next_que.append((y, x-1))
    search_que = next_que

print(count)
Problem p02625 (python)

Fixed submission:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


class CombMod:

    def __init__(self, N, MOD=10**9 + 7):

        N = N + 1
        inv = [0] * N
        fact = [0] * N
        fact_inv = [0] * N

        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD

        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD

        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

        self.fact = fact
        self.fact_inv = fact_inv
        self.inv = inv

    def comb(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[r] % mod * self.fact_inv[n - r] % mod

    def perm(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[n - r] % mod


def main():

    N, M = in_nn()
    mod = 10**9 + 7
    c = CombMod(M)

    ans = 0
    for i in range(N + 1):
        t = c.comb(N, i)

        t *= (-1)**(i % 2)
        t %= mod

        t *= c.perm(M, i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


class CombMod:

    def __init__(self, N, MOD=10**9 + 7):

        N = N + 1
        inv = [0] * N
        fact = [0] * N
        fact_inv = [0] * N

        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD

        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD

        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

        self.fact = fact
        self.fact_inv = fact_inv
        self.inv = inv

    def comb(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[r] % mod * self.fact_inv[n - r] % mod

    def perm(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[n - r] % mod


def main():

    N, M = in_nn()
    mod = 10**9 + 7
    c = CombMod(M)

    ans = 0
    for i in range(N + 1):
        t = c.comb(N, i)

        t *= (-1)**(i % 2)
        t %= mod

        t *= c.perm(M, i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()
Problem p02685 (python)

Fixed submission:
class Combination:

    """
    (使用例)
    comb = Combination(n_max, mod)
    comb(n, r)

    (注意)
    n_max != 0
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


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

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

print(ans)

Buggy submission (verdict: Runtime Error):
class Combination:

    """
    n_max = 10**6のとき前処理は約950ms(PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


N, M, K = map(int, input().split())
mod = 998244353
comb = Combination(N-1, mod)

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

print(ans)