Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

K = int(input())

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

print(sorted(LLs)[K-1])

Fixed submission:
K = int(input())

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

print(sorted(LLs)[K-1])

Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

K = int(input())

d = 10000

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

print(sorted(LLs)[K-1])

Fixed submission:
K = int(input())

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

print(sorted(LLs)[K-1])

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


def check(a):
    s = str(a)
    if len(s) == 1:
        return True
    
    for i in range(1, len(s)):
        if abs(int(s[i-1]) - int(s[i])) > 1:
            return False
    return True
    
def solve(N):
    m = 10**5
    ct = 0
    i = 1
    while True:
        if check(i):
            ct += 1
            if ct == N:
                return i
        i+=1

print(solve(N))

Fixed submission:
K = int(input())

LLs = []

def dfs(d, num):
    LLs.append(num)
    
    if d == 10: return

    a = num % 10
    for i in [-1, 0, 1]:
        b = a + i
        if  0 <= b < 10:
            dfs(d+1, num * 10 + b)

d = 1
for i in range(1, 10):
    dfs(d, i)

print(sorted(LLs)[K-1])
Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")

Fixed submission:
S = input()

def solve(S):
    if S[2] == S[3] and S[4] == S[5]:
        return "Yes"
    else:
        return "No"

print(solve(S))

Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")

Fixed submission:
S = input()

def solve(S):
    if S[2] == S[3] and S[4] == S[5]:
        return "Yes"
    else:
        return "No"

print(solve(S))

Buggy python submission (verdict: Runtime Error):
S = input()

def solve(S):
    if S[4] == S[5] and S[6] == S[7]:
        return "Yes"
    else:
        return "No"

print(solve(S))

Fixed submission:
S = input()

def solve(S):
    if S[2] == S[3] and S[4] == S[5]:
        return "Yes"
    else:
        return "No"

print(solve(S))
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

N = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

def solve(N, a):
    return a[N]

print(solve(N, a))

Fixed submission:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

N = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

def solve(N, a):
    return a[N-1]

print(solve(N, a))

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

N = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

def solve(N, a):
    return a[N]

print(solve(N, S))

Fixed submission:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

N = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

def solve(N, a):
    return a[N-1]

print(solve(N, a))
Buggy python submission (verdict: Runtime Error):
N = [int(_) for _ in input().split()]

H, W = N[0], N[1]


def solve(H, W):
    acnt = floor(W / 2) + 1
    bcnt = W - acnt
    
    if H == 1 or W == 1:
        return 1
    
    if H % 2 == 0:
        cnt = acnt * floor(H/2) + bcnt * floor(H/2)
    else:
        cnt = acnt * (floor(H/2) + 1) + bcnt * floor(H/2)
    return cnt

print(solve(H, W))

Fixed submission:
from math import floor

N = [int(_) for _ in input().split()]

H, W = N[0], N[1]


def solve(H, W):
    acnt = floor(W / 2) + 1
    bcnt = W - acnt
    
    if H == 1 or W == 1:
        return 1
    else:
        return floor((H * W + 1) / 2)
    
    # if H % 2 == 0:
    #     cnt = acnt * floor(H/2) + bcnt * floor(H/2)
    # else:
    #     cnt = acnt * (floor(H/2) + 1) + bcnt * floor(H/2)
    # return cnt

print(solve(H, W))
Buggy python submission (verdict: Runtime Error):
N = [int(_) for _ in input().split()]

def solve(a, b, c):
    
    # if c < a or c < b:
    #     return "No"

    # if a + 2*sqrt(a*b) + b - c < 0.0:
    #     return "Yes"
    # else:
    #     return "No"
    
    d = c-a-b
    if  0 < d and 4ab < d * d:
        return "Yes"
    else:
        return "No"

print(solve(N[0], N[1], N[2]))

Fixed submission:
N = [int(_) for _ in input().split()]

def solve(a, b, c):
    
    # if c < a or c < b:
    #     return "No"

    # if a + 2*sqrt(a*b) + b - c < 0.0:
    #     return "Yes"
    # else:
    #     return "No"
    
    d = c-a-b
    if  0 < d and 4*a*b < d * d:
        return "Yes"
    else:
        return "No"

print(solve(N[0], N[1], N[2]))
Buggy python submission (verdict: Time Limit Exceeded):
A, B, M = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
xyc = [[int(_) for _ in input().split()] for i in range(M)]

rets = []
for i in a:
    for j in b:
        rets += [i + j]
for x, y, c in xyc:
    rets += [a[x-1] + b[y-1] - c]
print(min(rets))

Fixed submission:
A, B, M = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
xyc = [[int(_) for _ in input().split()] for i in range(M)]

rets = [min(a) + min(b)]

for x, y, c in xyc:
    rets += [a[x-1] + b[y-1] - c]
print(min(rets))
Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

if S[0] == S[1] == S[2]:
    print("No")
    exit()
print("Yes")

Fixed submission:
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

if S[0] == S[1] == S[2]:
    print("No")
    exit()
print("Yes")
Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, A, B = [int(_) for _ in input().split()]


a = N // (A+B)
b = N % (A+B)
if b > A:
    b = A

print(int(a * A + b))

Fixed submission:
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, A, B = [int(_) for _ in input().split()]


a = N // (A+B)
b = N % (A+B)
if b > A:
    b = A

print(int(a * A + b))

Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, A, B = [int(_) for _ in input().split()]


a = N / (A+B)
b = N % (A+B)
if b > A:
    b = A

print(int(a * A + b))

Fixed submission:
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, A, B = [int(_) for _ in input().split()]


a = N // (A+B)
b = N % (A+B)
if b > A:
    b = A

print(int(a * A + b))
Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

A, B = [int(_) for _ in input().split()]

for i in range(100+1):

    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        exit()
print(-1)


Fixed submission:
A, B = [int(_) for _ in input().split()]

for i in range(0, 1250+1):

    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        exit()
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):

N, M=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
LR=[[int(i) for i in input().split()] for i in range(M)]  # 二次元配列入力　二次元マップみたいな入力のとき

ret = set(range(LR[0][0], LR[0][1]+1))

for i in LR[1:]:
    ret = set(range(i[0], i[1]+1)) & ret

print(len(ret))
    

Fixed submission:

N, M=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
LR=[[int(i) for i in input().split()] for i in range(M)]  # 二次元配列入力　二次元マップみたいな入力のとき

mi, ma = 0, 10**5

for i in LR:
    mi = max(mi, i[0])
    ma = min(ma, i[1])

if ma-mi < 0:
    print(0)
else:
    print(ma-mi + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        ne += [i[1]]

for j in ab:
    if j[0] in ne and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Fixed submission:
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
import copy
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]
N = str(N)

ab = sorted(ab)
firsts = []
nokori = copy.copy(ab)

for i in ab:
    if i[0] == "1":
        firsts += [i]
        nokori.remove(i)
    else:
        break

for i in firsts:
    for j in nokori:
        if j[0] == i[1] and j[1] == str(N):
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Fixed submission:
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]

ab = sorted(ab)

for i in ab:
    if i[0] == "1":   
        for j in ab:
            if j[0] == i[1] and j[1] == str(N):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Fixed submission:
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]

for i in ab:
    if i[0] == "1":   
        for j in ab:
            if j[0] == i[1] and j[1] == str(N):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Fixed submission:
N, M = [int(_) for _ in input().split()]
ab = [input().split() for _ in range(M)]

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
W, H, N = [int(_) for _ in input().split()]
xya = [[int(_) for _ in input().split()] for i in range(N)]

d = [[0], [W], [0], [H]]

for x, y, a in xya:
    if a == 1 or a == 2:
        d[a-1] += [x]
    else:
        d[a-1] += [y]

if (max(d[0]) - min(d[1])) > 0 and (max(d[2]) - min(d[3]) > 0:
    ret = (max(d[0]) - min(d[1])) * (max(d[2]) - min(d[3]))
    print(max(ret, 0))
else:
    print(0)

Fixed submission:
W, H, N = [int(_) for _ in input().split()]
xya = [[int(_) for _ in input().split()] for i in range(N)]

d = [[0], [W], [0], [H]]

for x, y, a in xya:
    if a == 1 or a == 2:
        d[a-1] += [x]
    else:
        d[a-1] += [y]

if min(d[1]) - max(d[0]) > 0 and min(d[3]) - max(d[2]) > 0:
    ret = (min(d[1]) - max(d[0])) * ( min(d[3]) - max(d[2]))
    print(max(ret, 0))
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
A = input()
B = input()
C = input()

ABC = {"a":deque(A), "b":deque(B), "c":deque(C)}
ABC_H = {"a":"A", "b":"B", "c":"C"}

ind = A[0]
while True:

    if len(ABC[ind]) == 0:
        break 
    ind = ABC[ind].popleft()

print(ABC_H[ind])


Fixed submission:
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

A = input()
B = input()
C = input()

ABC = {"a":deque(A), "b":deque(B), "c":deque(C)}
ABC_H = {"a":"A", "b":"B", "c":"C"}

ind = A[0]
while True:

    if len(ABC[ind]) == 0:
        break 
    ind = ABC[ind].popleft()

print(ABC_H[ind])
Buggy python submission (verdict: Runtime Error):
#! /usr/bin/env python3

# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

c = Counter(S)

for i in c:
    if c[i] % 2 != 0:
        print("No")
        exit()
print("Yes")


Fixed submission:
#! /usr/bin/env python3

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

S = input()

c = Counter(S)

for i in c:
    if c[i] % 2 != 0:
        print("No")
        exit()
print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):

import math
from collections import defaultdict


def factorization(x, d):
    """
    素因数分解する
    かつ途中結果を利用して計算を効率よく行いたい

    fa(x) をxの素因数分解とする ; a^x * b^y * ...
    例えばxが2で割り切れるとすると、
    fa(x) = 2 * fa(x // 2) = ... = 2 * .... * fa(1)
    となるため、計算過程を覚えておいて、逆算することで
    xを試し割りする途中の値についても素因数分解をえる
    """
    if x == 1:
        # d[1]はすでに格納済みの想定
        return d

    calc = [(1, x)]
    found = False
    for t in range(2, math.floor(math.sqrt(x)) + 1):
        if found:
            break
        
        while x % t == 0:
            calc.append((t, x // t))
            x //= t
            if x in d:
                found = True
                break

    if not found and x > 1:
        calc.append((x, 1))

    while len(calc) > 1:
        c, b = calc.pop()
        y = c * b
        d[y] = d[b].copy()
        d[y][c] += 1
    return d


def divisors(fact):
    values = fact.values()
    ans = 1
    for v in values:
        ans *= (v + 1)
    return ans


def submit():
    n = int(input())
    d = {1: defaultdict(int)}

    ans = 0
    while n > 1:
        if n not in d:
            d = factorization(n, d)
        
        ans += n * divisors(d[n])
        n -= 1
    print(ans + 1)


if __name__ == "__main__":
    submit()
    

Fixed submission:


def submit():
    n = int(input())
    d = [1 for _ in range(n + 1)]
    d[0] = 0

    # エラトステネスの篩風
    for i in range(2, n + 1):
        coef = 1
        while i * coef <= n:
            d[i * coef] += 1
            coef += 1

    ans = 0
    for k in range(1, n + 1):
        ans += k * d[k]

    print(ans)


if __name__ == "__main__":
    submit()
Buggy python submission (verdict: Time Limit Exceeded):


def submit():
    n = int(input())
    a = (int(e) for e in input().split())
    thr = 10 ** 18

    ans = 1
    for e in a:
        ans *= e
    
    if ans > thr:
        print(-1)
    else:
        print(ans)


submit()
        

Fixed submission:

def submit():
    n = int(input())
    a = [int(e) for e in input().split()]
    thr = 10 ** 18

    if 0 in a:
        print(0)
        return

    ans = 1
    for e in a:
        ans *= e
        if ans > thr:
            ans = -1
            break
    
    print(ans)


submit()
Buggy python submission (verdict: Time Limit Exceeded):


def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()    

Fixed submission:


def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()