Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7

n=int(data())
s=0
while n:
    s+=n%10
    n//=10
print("Yes" if s%9==0 else "No")


Fixed submission:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7

n=int(data())
print("Yes" if n%9==0 else "No")
Buggy python submission (verdict: Runtime Error):
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
#INF = float('inf')
mod = int(1e9)+7

n=int(data())
x=data()
c=x.count('1')
t1,t2=1,1
k1=0
k2=0
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k1=(k1+t1)%(c+1)
        k2=(k2+t2)%(c-1)
    t1=(t1*2)%(c+1)
    t2=(t2*2)%(c-1)
ans=[]
t1,t2=1,1
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k=(k2-t2+c-1)%(c-1)
    else:
        k=(k1+t1)%(c+1)
    cnt=1
    while k:
        k=k%(bin(k)[2:].count('1'))
        cnt+=1
    ans.append(cnt)
    t1 = (t1 * 2) % (c + 1)
    t2 = (t2 * 2) % (c - 1)
outl(ans[::-1])


Fixed submission:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
#INF = float('inf')
mod = int(1e9)+7

n=int(data())
x=data()
c=x.count('1')
t1,t2=1,1
k1=0
k2=0
for i in range(n-1,-1,-1):
    if x[i]=='1':
        k1=(k1+t1)%(c+1)
        if c==1:
            continue
        k2=(k2+t2)%(c-1)
    t1=(t1*2)%(c+1)
    if c != 1:
        t2=(t2*2)%(c-1)
ans=[]
t1,t2=1,1
for i in range(n-1,-1,-1):
    if x[i]=='1':
        if c==1:
            ans.append(0)
            continue
        k=(k2-t2+c-1)%(c-1)
    else:
        k=(k1+t1)%(c+1)
    cnt=1
    while k:
        k=k%(bin(k)[2:].count('1'))
        cnt+=1
    ans.append(cnt)
    t1 = (t1 * 2) % (c + 1)
    if c!=1:
        t2 = (t2 * 2) % (c - 1)
outl(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    else:
        n1=i
    ans*=a1[i][1]
if ans>=0:
    out(ans%mod)
else:
    for i in range(k,n):
        if a1[i][1]>=0:
            ans=max((ans//a1[n1][1])*a1[i][1],ans)
        if a1[i][1]<0 and p!=-1:
            ans=max((ans//a1[p][1])*a1[i][1],ans)
    if ans<0:
        ans=1
        for i in range(k):
            ans *= a1[n-i-1][1]
    out(ans%mod)









Fixed submission:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
from decimal import Decimal
from fractions import Fraction
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 10**9 + 7


n,k=mdata()
a=mdata()
n1,p=-1,-1
a1=[(abs(a[i]),a[i]) for i in range(n)]
a1.sort(reverse=True)
ans=1
c=1
for i in range(k):
    if a1[i][1]>0:
        p=i
    elif a1[i][1]<0:
        n1=i
        c*=-1
    else:
        c=0
    ans=(ans*a1[i][1])%mod
if c>=0:
    out(ans%mod)
else:
    b1=0
    b2=0
    for i in range(k,n):
        if a1[i][1]>=0 and b1==0:
            u1,v1=a1[n1][1],a1[i][1]
            b1=1
            c=1
        if a1[i][1]<0 and p!=-1 and b2==0:
            u2,v2=a1[p][1],a1[i][1]
            b2=1
            c=1
    if c<0:
        ans=1
        for i in range(k):
            ans = (ans*a1[n-i-1][1])%mod
    else:
        if b1==1 and b2==1:
            if Fraction(v1,u1)<Fraction(v2,u2):
                ans=ans*pow(u1,mod-2,mod)*v1
            else:
                ans = ans * pow(u2, mod - 2, mod) * v2
        elif b1==1:
            ans = ans * pow(u1, mod - 2, mod) * v1
        else:
            ans = ans * pow(u2, mod - 2, mod) * v2
    out(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = 998244353
#from decimal import Decimal

n,k=mdata()
A=mdata()
for i in range(k):
    A1=[0]*(n+1)
    for j in range(n):
        A1[max(0,j-A[j])]+=1
        A1[min(n,j+A[j]+1)]-=1
    flag=True
    A[0]=A1[0]
    for j in range(1,n):
        A1[j]+=A1[j-1]
        A[j]=A1[j]
        if A1[j]!=n:
            flag=False
    if flag==True:
        break
print(*A)


Fixed submission:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = 998244353
#from decimal import Decimal

n,k=mdata()
A=mdata()
for i in range(k):
    A1=[0]*(n+1)
    for j in range(n):
        A1[max(0,j-A[j])]+=1
        A1[min(n,j+A[j]+1)]-=1
    flag=True
    A[0]=A1[0]
    for j in range(1,n):
        A1[j]+=A1[j-1]
        A[j]=A1[j]
        if A1[j]!=n:
            flag=False
    if flag==True:
        break
print(*A)
Buggy python submission (verdict: Runtime Error):
a,b,c=mdata()
print(c,a,b)

Fixed submission:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
#def print(x): return sys.stdout.write(str(x)+'\n')
#sys.setrecursionlimit(100000)
mod=int(1e9+7)

a,b,c=mdata()
print(c,a,b)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)

n,k=mdata()
H=list(mdata())
d=[1e9]*n
d[0]=0
for i in range(1,n):
    for j in range(i-1,max(i-k-1,-1),-1):
        d[i]=min(d[i],d[j]+abs(H[i]-H[j]))
print(d[-1])


Fixed submission:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)

n,k=mdata()
H=list(mdata())
d=[1e9]*n
d[0]=0
for i in range(1,n):
    for j in range(i-1,max(i-k-1,-1),-1):
        d[i]=min(d[i],d[j]+abs(H[i]-H[j]))
print(d[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


n,m=mdata()
dp=[0]*n
g=[set() for i in range(n)]
par=[i for i in range(n)]
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
for i in range(n):
    if par[i]==i:
        s1=set()
        s1.add(i)
        while s1:
            s2=set()
            for i in s1:
                for j in g[i]:
                    s2.add(j)
                    dp[j]=max(dp[j],dp[i]+1)
            s1=s2.copy()
print(max(dp))





Fixed submission:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


n,m=mdata()
dp=[0]*n
g=[set() for i in range(n)]
par=[i for i in range(n)]
chl=[0]*n
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
    chl[y-1]=1
vis=[0]*n
for i in range(n):
    if chl[i]==0:
        s1=deque()
        s1.append(i)
        while s1:
            a=s1[-1]
            if vis[a]==1:
                if a!=i:
                    dp[par[a]]=max(dp[par[a]],dp[a]+1)
                s1.pop()
                continue
            vis[a]=1
            for j in g[a]:
                if vis[j]==0:
                    s1.append(j)
                    par[j]=a
                else:
                    dp[a]=max(dp[a],dp[j]+1)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    n,k=mdata()
    A=mdata()
    dp=[1 if A[0]>=i else 0 for i in range(k+1)]
    for i in range(1,n):
        for j in range(1,k+1):
            dp[j]+=dp[j-1]
        for j in range(k+1):
            if A[i]<j:
                dp[j]-=dp[j-A[i]-1]
    print(dp[-1]%mod)



if __name__ == '__main__':
    main()

Fixed submission:
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(n):
        dpsum = [0] * (k + 2)
        for l in range(k + 1):
            dpsum[l + 1] = dpsum[l] + dp[i][l]
            dpsum[l + 1] %= mod
        for j in range(k + 1):
            dp[i + 1][j] = (dpsum[j + 1] - dpsum[max(0, j - a[i])]) % mod
    print(dp[n][k])
    
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
from collections import Counter
AC = dict(Counter(A))
maxA, maxAcnt = max(AC.items(), key=lambda x: x[1])
BC = dict(Counter(B))
maxB, maxBcnt = max(BC.items(), key=lambda x: x[1])

if maxA==maxB and maxAcnt>=(N+2)//2 and maxBcnt>=(N+2)//2:
    print("No")
else:
    print("Yes")
    outB= [0]*N
    for i in range(N):
        if A[i]==maxA:
            start = i
            break
    from collections import deque
    que = deque(B)
    t = start
    while que:
        v = que.popleft()
        if v==A[t]:
            que.append(v)
        else:
            outB[t]=v
            t+=1
            if t==N:
                t=0
    print(*outB)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
Br = list(reversed(B))

NG = []
for i in range(N):
    if A[i]==Br[i]:
        NG.append(i)
        NGnumber = Br[i]
NGcnt = len(NG)

if NGcnt==0:
    print("Yes")
    print(*Br)
else:
    OK = []
    for i in range(N):
        if Br[i]!=NGnumber and A[i]!=NGnumber:
            OK.append(i)
    OKcnt = len(OK)

    if NGcnt>OKcnt:
        print("No")
    else:
        for i in range(NGcnt):
            Br[NG[i]],Br[OK[i]]=Br[OK[i]],Br[NG[i]]
        print("Yes")
        print(*Br)
Buggy python submission (verdict: Runtime Error):
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))

low=0
high=max(A)
X=max(A)
while low<=high:
  mid=(low+high)//2
  cnt = 0
  for i in range(N):
      cnt += A[i]//mid
  if K<cnt:
    low=mid+1
  else:
    X=min(X,mid)
    high=mid-1
print(X)


Fixed submission:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))

low=1
high=2*max(A)
X=max(A)
while low<=high:
  mid=(low+high)//2
  cnt = 0
  for i in range(N):
      if A[i]%mid==0:
          cnt += A[i]//mid-1
      else:
          cnt += A[i]//mid
  if K<cnt:
    low=mid+1
  else:
    X=min(X,mid)
    high=mid-1
print(X)

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

low=0
high=max(A)
X=max(A)
while low<=high:
  mid=(low+high)//2
  cnt = 0
  for i in range(N):
      cnt += A[i]//mid
  if K<cnt:
    low=mid+1
  else:
    X=mid
    high=mid-1
print(X)


Fixed submission:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))

low=1
high=2*max(A)
X=max(A)
while low<=high:
  mid=(low+high)//2
  cnt = 0
  for i in range(N):
      if A[i]%mid==0:
          cnt += A[i]//mid-1
      else:
          cnt += A[i]//mid
  if K<cnt:
    low=mid+1
  else:
    X=min(X,mid)
    high=mid-1
print(X)
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = list(input())

pop = [0]*(N+1)
amari = [0]*(N+1)
for i in range(1,N+1):
    pop[i]=pop[i-(i&(-i))]+1
    amari[i] = amari[i%pop[i]]+1

cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt1+=1
Y = cnt1+1
Z = cnt1-1

baseY = 0
baseZ = 0
for i in range(N):
    K = int(X[N-1-i])
    if K==1:
        baseY += pow(2,i,Y)
        baseZ += pow(2,i,Z)
baseY = baseY%Y
baseZ = baseZ%Z


for i in range(N):
    if X[i]=="0":
        out = (baseY + pow(2,N-1-i,Y))%Y
        print(amari[out]+1)
    elif X[i]=="1":
        out = (baseZ - pow(2,N-1-i,Z))%Z
        print(amari[out]+1)

Fixed submission:
N = int(input())
X = list(input())

pop = [0]*(N+1)
amari = [0]*(N+1)
for i in range(1,N+1):
    pop[i]=pop[i-(i&(-i))]+1
    amari[i] = amari[i%pop[i]]+1

cnt1 = 0
for i in range(N):
    if X[i]=="1":
        cnt1+=1
Y = cnt1+1
Z = cnt1-1

baseY = 0
baseZ = 0
for i in range(N):
    K = int(X[N-1-i])
    if K==1:
        baseY += pow(2,i,Y)
        if Z!=0:
            baseZ += pow(2,i,Z)
        else:
            baseZ =-1
baseY = baseY%Y
if Z!=0:
    baseZ = baseZ%Z
else:
    baseZ = -1

for i in range(N):
    if X[i]=="0":
        out = (baseY + pow(2,N-1-i,Y))%Y
        print(amari[out]+1)
    elif X[i]=="1":
        if Z!=0:
            out = (baseZ - pow(2,N-1-i,Z))%Z
            print(amari[out]+1)
        else:
            print(0)
Buggy python submission (verdict: Runtime Error):
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if Nplus==0:
    if K%2==0:
        t=0
        out = 1
        while t<=K-1:
            out = out*Aminus[t]%p
            t+=1
    else:
        t=0
        out = 1
        while t<=K-1:
            out = out*Aminus[N-1-t]%p
            t+=1
    print(out)
else:
    Aminus2 = []
    for i in range(Nminus//2):
        Aminus2.append(Aminus[2*i]*Aminus[2*i+1])

    out = 1
    l = 0
    r = 0
    while K>0:
        cand = [0,0]
        flag = 0
        if r<=Nminus-1 and K>=2 and Aminus2[r]>0:
            cand[0] = Aminus2[r]
            flag=1
        if l+1<=Nplus-1:
            cand[1] = Aplus[l]*Aplus[l+1]
            flag=1
        if flag==1:
            if cand[0]>cand[1]:
                r+=2
                K+=-2
                out = out*cand[0]%p
            elif cand[0]<=cand[1]:
                l+=1
                K+=-1
                out = out*cand[1]%p
        else:
            if l==Nplus-1 and r==Nminus-1 and K==2:
                out = out*Aplus[l]*Aminus2[r]%p
            elif l==Nplus-1 and r==Nminus-1 and K==1:
                out = out*Aplus[l]%p
            elif K==2:
                out = out*Aplus[l]*Aplus[l+1]%p
            else:
                out = out*Aplus[l]%p
            break
    print(out)

Fixed submission:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
p = 10**9+7
Aplus = []
Nplus = 0
Aminus = []
Nminus = 0
Aabs = []
for i in range(N):
    if A[i]>=0:
        Aplus.append(A[i])
        Nplus += 1
    else:
        Aminus.append(A[i])
        Nminus += 1
Aplus.sort(reverse=True)
Aminus.sort(reverse=False)

if K==N:
    out=1
    for i in range(K):
        out = out*A[i]%p
    print(out)
elif Nminus==N and K%2==1:
    out=1
    for i in range(K):
        out = out*Aminus[N-i-1]%p
    print(out)
else:
    l=0
    r=0
    out=1
    inf = float('inf')
    while K>0:
        if l+1<=Nplus-1:
            cand1 = Aplus[l]*Aplus[l+1]
        elif l==Nplus-1:
            cand1 = Aplus[l]
        else:
            cand1 = -1*inf

        if r+1<=Nminus-1:
            cand2 = Aminus[r]*Aminus[r+1]
        elif r==Nminus-1:
            cand2 = Aminus[r]
        else:
            cand2 = -1*inf

        if cand1>cand2 or K==1:
            out=out*Aplus[l]%p
            K += -1
            l += 1
        else:
            out=out*Aminus[r]*Aminus[r+1]%p
            K += -2
            r += 2
    print(out)
Buggy python submission (verdict: Time Limit Exceeded):
N,M,K=list(map(int,input().split()))

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

out = 0
p = 998244353
for i in range(K+1):
    out += M*comb(N-1,i,p)*power_func(M-1,N-1-i,p)
    out = out % p
print(out)

Fixed submission:
N,M,K=list(map(int,input().split()))

MAXN = 2*(10**5)+10
p = 998244353
MOD = p
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

out = 0
for i in range(K+1):
    out += M*nCr(N-1,i,p)*power_func(M-1,N-1-i,p)
    out = out % p
print(out)
Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

L = make_divisors(X)
flag = 0
for C in L:
    Y = X//C
    for A in range(Y+1):
        B = A-C
        if A**4 + A**3*B + A**2*B**2 + A*B**3 + B**4 == Y:
            print(A,B)
            flag = 1
        if flag==1:
            break
    if flag==1:
        break

Fixed submission:
X = int(input())
flag = 0
for A in range(-300,301):
    for B in range(-300,301):
        if A**5 - B**5 == X:
            print(A,B)
            flag = 1
        if flag==1:
            break
    if flag==1:
        break

Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())
flag = 0
minB = -1*int(X**0.2)
for B in range(minB,10**9+1):
    Y = (X+B**5)**0.2
    if Y==int(Y):
        print(int(Y),B)
        break


Fixed submission:
X = int(input())
flag = 0
for A in range(-300,301):
    for B in range(-300,301):
        if A**5 - B**5 == X:
            print(A,B)
            flag = 1
        if flag==1:
            break
    if flag==1:
        break