Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
t = input()
u = list(t)
for i in range(len(u)):
    if u[i] == '?':
        u[i] = 'P'
        tmp = ''.join(u).count('D') + ''.join(u).count('PD')
        u[i] = 'D'
        tmp2 = ''.join(u).count('D') + ''.join(u).count('PD')
        if tmp >= tmp2:
            u[i] = 'P'
        else:
            u[i] = 'D'
print(''.join(u))

Fixed submission:
t = input()
u = list(t)
if u[0] == '?':
    u[0] = 'D'
if u[-1] == '?':
    u[-1] = 'D'
for i in range(1, len(u)-1):
    if u[i] == '?':
        if u[i-1] == 'P':
            u[i] = 'D'
        elif u[i+1] == 'D':
            u[i] = 'P'
        else:
            u[i] = 'D'
print(''.join(u))

Buggy python submission (verdict: Runtime Error):
t = input()
u = list(t)
if u[0] == '?':
    if u[1] == 'D':
        u[0] = 'P'
    else:
        u[0] = 'D'
if u[-1] == '?':
    u[-1] = 'D'
for i in range(1, len(u)-1):
    if u[i] == '?':
        if u[i-1] == 'P':
            u[i] = 'D'
        elif u[i+1] == 'D':
            u[i] = 'P'
        else:
            u[i] = 'D'
print(''.join(u))


Fixed submission:
t = input()
u = list(t)
if u[0] == '?':
    u[0] = 'D'
if u[-1] == '?':
    u[-1] = 'D'
for i in range(1, len(u)-1):
    if u[i] == '?':
        if u[i-1] == 'P':
            u[i] = 'D'
        elif u[i+1] == 'D':
            u[i] = 'P'
        else:
            u[i] = 'D'
print(''.join(u))
Buggy python submission (verdict: Runtime Error):
a, b, n = map(int, input().split())
ans = [0] * n
for i in range(n):
    ans[i] = (a * (i+1) / b) // 1 - a * (((i+1) / b) // 1)
print(int(max(ans)))

Fixed submission:
import math
a, b, n = map(int, input().split())
if b <= n:
    print(math.floor((a * (b-1)) / b) - a * math.floor((b-1) / b))
elif b > n:
    print(math.floor((a * (n)) / b) - a * math.floor((n) / b))

Buggy python submission (verdict: Runtime Error):
import math
a, b, n = map(int, input().split())
ans = [0] * n
for i in range(n):
    ans[i] = math.floor(a * (i+1) / b) - a * math.floor((i+1) / b)
print(max(ans))

Fixed submission:
import math
a, b, n = map(int, input().split())
if b <= n:
    print(math.floor((a * (b-1)) / b) - a * math.floor((b-1) / b))
elif b > n:
    print(math.floor((a * (n)) / b) - a * math.floor((n) / b))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    a.count(j)
    print(j)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split())
for i in a:
    print(a.count(str(i+1)))

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
a = list(input())
for i in a:
    print(a.count(str(i+1)))

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = list(input())
for i in range(n):
    print(a.count(str(i+1)))

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))


Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
Buggy python submission (verdict: Runtime Error):
import math
k = int(input())
sum =0
for a in range(1, k+1):
     for b in range(1, k+1):
         x = gcd(a, b)
         for c in range(1, k+1):
             sum += gcd(x, c)
print(sum)

Fixed submission:
import math
k = int(input())
sum =0
for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += math.gcd(math.gcd(a, b), c)
print(sum)

Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
sum =0
count = 0

def euclidean(p, q):
     if p % q == 0:
          return q
     else:
          return euclidean(q, p % q)

for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += euclidean(euclidean(a, b), c)
print(sum)

Fixed submission:
import math
k = int(input())
sum =0
for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += math.gcd(math.gcd(a, b), c)
print(sum)

Buggy python submission (verdict: Time Limit Exceeded):
import math
k = int(input())
sum =0
for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += math.gcd(math.gcd(a, b), c)
print(sum)

Fixed submission:
import math
k = int(input())
sum =0
for a in range(1, k+1):
     for b in range(1, k+1):
          for c in range(1, k+1):
               sum += math.gcd(math.gcd(a, b), c)
print(sum)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
if min(n, k) ==1:
    print("0")
else:
    if n < k:
        n, k = k, n
    while n % k != 0:
        n, k = k, n % k
    print(k)

Fixed submission:
n, k = map(int, input().split())
a = n % k
b = k - a
print(min(a, b))

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
x = n
i = 0
c = max(n, k) / min(n, k)
if k == 1:
    print("0")
else:
    while i <= c:
        x = abs(x - k)
        i += 1
    print(min(n, x))


Fixed submission:
n, k = map(int, input().split())
a = n % k
b = k - a
print(min(a, b))

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
x = n
i = 0
c = max(n, k) / min(n, k)
if k == 1:
    print("0")
else:
    while i <= c:
        x = abs(x - k)
        i += 1
print(min(n, x))


Fixed submission:
n, k = map(int, input().split())
a = n % k
b = k - a
print(min(a, b))
Buggy python submission (verdict: Runtime Error):
s = input()
l = s[:(len(s)-1)//2:]
r = s[(len(s)+1)//2:]
if a == b and a == a[::-1]:
     print("Yes")
else:
     print("No")

Fixed submission:
s = input()
a = s[:(len(s)-1)//2:]
b = s[(len(s)+1)//2:]
if a == b and a == a[::-1]:
     print("Yes")
else:
     print("No")
Buggy python submission (verdict: Runtime Error):
l = int(input())
ans = []
for i in range(1, l//3+1):
    for j in range(1, l//3+1):
        ans.append(i*j*(l-i-j))
print(max(ans))

Fixed submission:
print((int(input())/3)**3)
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())
if n%(a+b) < a:
    print(n//(a+b)*a+n%(a+b))
else:
    print(n//(a+b)*a+a)

Fixed submission:
import math
a, b = map(int, input().split())
x = []
y = []
for i in range(math.ceil(b/0.1), math.floor((b+1)/0.1)):
    y.append(i)
for i in range(math.ceil(a/0.08), math.floor((a+1)/0.08)):
    x.append(i)
    if y.count(i) == 1:
        print(i)
        exit()
print('-1')
Buggy python submission (verdict: Runtime Error):
x = list(map(int, input().split()))
print(x)
x = sorted(x)
print(x)
if count(x[1]) == 2:
     print("Yes")
else:
     print("No")


Fixed submission:
x = list(map(int, input().split()))
x = sorted(x)
if x.count(x[1]) == 2:
     print("Yes")
else:
     print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(int, input().split()))

count = 0

for i in range(n):
    if p[i] == min(p[:i+1]):
        count += 1
print(count)

Fixed submission:
n = int(input())
p = list(map(int, input().split()))

count = 0
m = p[0]

for i in p:
    m = min(m, i)
    if m == i:
        count += 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(int, input().split()))

count = 0

for i in range(n):
    if p[i] == min(p[:i+1]):
        count += 1
print(count)

Fixed submission:
n = int(input())
p = list(map(int, input().split()))

count = 0
m = p[0]

for i in p:
    m = min(m, i)
    if m == i:
        count += 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n):
    count = 0
    for j in range(i+1):
        if p[i] <= p[j]:
            count += 1
    if count == i + 1:
        ans += 1
print(ans)


Fixed submission:
n = int(input())
p = list(map(int, input().split()))

count = 0
m = p[0]

for i in p:
    m = min(m, i)
    if m == i:
        count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
import math
a, b = map(int, input().split())
a = a // math.gcd(a, b)
print(a * b)

Fixed submission:
import fractions
a, b = map(int, input().split())
a = a // fractions.gcd(a, b)
print(a * b)
Buggy python submission (verdict: Runtime Error):
s = input()
x = [ '0', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT', 'SUN' ]
for i in range x:
     if s == x[i]:
          print(i)

Fixed submission:
s = input()
x = [ '0', 'SAT', 'FRI', 'THU', 'WED', 'TUE', 'MON', 'SUN']
for i in range(len(x)):
     if s == x[i]:
          print(i)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
l, r = map(int, input().split())
ans = 2019
for i in range(l, r+1):
    for j in range(i+1, r+1):
        tmp = 0
        tmp = i * j % 2019
        ans = min(ans, tmp)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
l, r = map(int, input().split())
ans = 2019
for i in range(l, r+1):
    for j in range(i+1, r+1):
        tmp = 0
        tmp = i * j % 2019
        ans = min(ans, tmp)
        if ans == 0:
            print(ans)
            exit()
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l, r = map(int, input().split())
ans = 2019
for i in range(l, r+1):
    for j in range(i+1, r+1):
        tmp = 0
        tmp = i * j % 2019
        ans = min(ans, tmp)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
l, r = map(int, input().split())
ans = 2019
for i in range(l, r+1):
    for j in range(i+1, r+1):
        tmp = 0
        tmp = i * j % 2019
        ans = min(ans, tmp)
        if ans == 0:
            print(ans)
            exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(int(input()))
if s[0] != s[1] and s[1] != s[2] and s[2] != s[3]:
     print('Good')
else:
     print('Bad')

Fixed submission:
s = list(input())
if s[0] != s[1] and s[1] != s[2] and s[2] != s[3]:
     print('Good')
else:
     print('Bad')
Buggy python submission (verdict: Runtime Error):
x, a = int(input())
if x < a:
     print("0")
else:
     print("10")

Fixed submission:
x, a = map(int,input().split())
if x < a:
     print("0")
else:
     print("10")
Buggy python submission (verdict: Runtime Error):
s = list(input())
count = 0
ans = []
for i in s:
    if i == 'A' or i =='C' or i =='G' or i =='T':
        count += 1
    else:
        ans.append(count)
        count = 0
print(max(ans))

Fixed submission:
s = input()
count = 0
ans = 0
for i in s:
    if i in'AGCT':
        count += 1
    else:
        count = 0
    ans = max(ans, count)
print(ans)

Buggy python submission (verdict: Runtime Error):
s = list(input())
t = [0] * len(s)
count = 0
ans = []
for i in range(len(s)):
    if s[i] == 'A' or s[i] =='C' or s[i] =='G' or s[i] =='T':
        t[i] = 1
        count += 1
    else:
        ans.append(count)
        count = 0
print(max(ans))

Fixed submission:
s = input()
count = 0
ans = 0
for i in s:
    if i in'AGCT':
        count += 1
    else:
        count = 0
    ans = max(ans, count)
print(ans)
Buggy python submission (verdict: Runtime Error):
n, t = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
x = []
for i in range(n):
     if a[i][1] <= t:
          x.append(a[i][0])
print(min(x))

Fixed submission:
n, t = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
x = []
for i in range(n):
     if a[i][1] <= t:
          x.append(a[i][0])
if x != []:
     print(min(x))
else:
     print("TLE")
Buggy python submission (verdict: Runtime Error):
n = int(input())

if n % 4 == 0 or n % 7 == 0
    print('Yes')

elif (n % 7) % 4 == 0:
    print('Yes')

else:
    print('No')

Fixed submission:
n = int(input())

ans = []
for i in range(n//4+1):
    for j in range(n//7+1):
        if 4*i+7*j <= n:
            ans.append(4*i+7*j)
if ans.count(n) != 0:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
s = input()
if s[0] == 'A' and s[2:-1].count('C') == 1 and s[:2].count('C') == 0 and s[-1:].count('C' == 0):
     list(s).remove("A")
     list(s).remove("C")
     print(s.islower())
     if s.islower() == 0:
          print("AC")
          exit()
else:
     print("WA")

Fixed submission:
s = input()
ans = 'WA'
a = []
if s[0] == 'A' and s[2:-1].count('C') == 1:
     a = list(s)
     a.remove('A')
     a.remove('C')
     a = str(a)
     if a.islower() == True:
          ans = 'AC'
print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
a = int(input())
b = int(input())
c = a * b
if c%2 == 0:
    print("Even")
else:
    print("Odd")

Fixed submission:
a, b = map(int, input().split())
if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")

Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = a * b
if c%2 == 0:
    print("Even")
else:
    print("Odd")

Fixed submission:
a, b = map(int, input().split())
if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")
Buggy python submission (verdict: Runtime Error):
a, b = map(str, input().split())
c = int(a+b)
if float.is_integer(math.sqrt(c)) == True:
    print('Yes')
else:
    print('No')

Fixed submission:
import math
a, b = map(str, input().split())
c = int(a+b)
if float.is_integer(math.sqrt(c)) == True:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
print(input().conut("1"))

Fixed submission:
print(input().count("1"))

Buggy python submission (verdict: Runtime Error):
print(input().conut("1"))

Fixed submission:
print(input().count("1"))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int(input()) for _ in range(n)]

a = sorted(a):
tmp = 0
ans = 0
for i in a:
    if i == tmp:
        ans -= 1
        tmp = 0
    else:
        ans += 1
        tmp = i
print(ans)

Fixed submission:
n = int(input())
a = [int(input()) for _ in range(n)]

a = sorted(a)
tmp = 0
ans = 0
for i in a:
    if i == tmp:
        ans -= 1
        tmp = 0
    else:
        ans += 1
        tmp = i

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]

b = set(sorted(a))
count = 0

for i in b:
    if a.count(i) % 2 == 0:
        pass
    else:
        count += 1

print(count)

Fixed submission:
n = int(input())
a = [int(input()) for _ in range(n)]

a = sorted(a)
tmp = 0
ans = 0
for i in a:
    if i == tmp:
        ans -= 1
        tmp = 0
    else:
        ans += 1
        tmp = i

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]

ans = []

for i in a:
    if ans.count(i) == 0:
        ans.append(i)

    else:
        ans.remove(i)

print(len(ans))

Fixed submission:
n = int(input())
a = [int(input()) for _ in range(n)]

a = sorted(a)
tmp = 0
ans = 0
for i in a:
    if i == tmp:
        ans -= 1
        tmp = 0
    else:
        ans += 1
        tmp = i

print(ans)
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int(input().split()))
print(sum(a, b, c)-max(a, b, c))

Fixed submission:
a, b, c = map(int, input().split())
print(a + b + c - max(a, b, c))
Buggy python submission (verdict: Runtime Error):
a, b, c = map(input().split())
if a[-1] == b[0] and b[-1] == c[0]:
    print('YES')
else:
    print('NO')

Fixed submission:
a, b, c = input().split()
if a[-1] == b[0] and b[-1] == c[0]:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
w, a, b = map(int, input().split())

if b + w < a:
    print(a - (b + w))
elif a <= b + w <= a + w:
    print(0):
elif a <= b <= a + w:
    print(0)
elif a + w < b:
    print(b- (a + w))

Fixed submission:
w, a, b = map(int, input().split())

if b + w < a:
    print(a - (b + w))
elif a <= b + w <= a + w:
    print(0)
elif a <= b <= a + w:
    print(0)
elif a + w < b:
    print(b - (a + w))
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
print(n*800-n//15*200)

Fixed submission:
n = int(input())
print(n*800-n//15*200)
Buggy python submission (verdict: Runtime Error):
a, op, b = map(input().split())
if op == '+':
  print(int(a)+int(b))
else:
  print(int(a)-int(b))

Fixed submission:
a, op, b = input().split()
if op == '+':
  print(int(a)+int(b))
else:
  print(int(a)-int(b))

Buggy python submission (verdict: Runtime Error):
a, op, b = map(input().split())
if op == '+':
  print(int(a)+int(b)
else:
  print(int(a)-int(b))

Fixed submission:
a, op, b = input().split()
if op == '+':
  print(int(a)+int(b))
else:
  print(int(a)-int(b))
Buggy python submission (verdict: Runtime Error):
c = input()
if c == 'a' or c =='i' or c == 'u' or c == 'e' or c =='o':
  priint('vowel')
else:
  print('consonant')

Fixed submission:
c = input()
if c == 'a' or c =='i' or c == 'u' or c == 'e' or c =='o':
  print('vowel')
else:
  print('consonant')

Buggy python submission (verdict: Runtime Error):
c = input()
if c == 'a' or c =='i' or c == 'u' or c == 'e' or c =='O':
  priint('vowel')
else:
  print('consonant')

Fixed submission:
c = input()
if c == 'a' or c =='i' or c == 'u' or c == 'e' or c =='o':
  print('vowel')
else:
  print('consonant')
Buggy python submission (verdict: Runtime Error):
n = list(map(int, input().split()))
if n.count(5) == 2 and n.count(7) == 1:
  print('YES')
else:
  orint('NO')

Fixed submission:
n = list(map(int, input().split()))
if n.count(5) == 2 and n.count(7) == 1:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
x,n=map(int,input().split())
if n==0:
  print(x)
else:
  p=list(map(int,input().split()))
  p.sort()
  ans=0
  on=1
  dif=1
  if x in p:
    now=p.index(x)
    while on==1:
      if p[now-dif]!=x-dif:
        ans=x-dif
        on=0
      elif p[now+dif]!=x+dif:
        ans=x+dif
        on=0
      else:
        dif+=1
    print(ans)
  else:
    print(x)

Fixed submission:
x,n=map(int,input().split())
if n==0:
  print(x)
else:
  p=list(map(int,input().split()))
  p.sort()
  ans=0
  on=1
  dif=1
  if x in p:
    now=p.index(x)
    while on==1:
      if now-dif<0:
        ans=x-dif
        on=0
      elif p[now-dif]!=x-dif:
        ans=x-dif
        on=0
      elif now+dif==n:
        ans=x+dif  
        on=0
      elif p[now+dif]!=x+dif:
        ans=x+dif
        on=0
      else:
        dif+=1
    print(ans)
  else:
    print(x)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
i=0
con=1
mod=10**18
ans=1
why=0
while con==1:
  ans=ans*a[i]
  i+=1
  if ans>mod:
    ans=1
    why=1
  elif i==n:
    con=0
if ans==0:
  print(0)
elif why==1:
  print(-1)
else:
  print(ans)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
i=0
con=1
mod=10**18
ans=1
why=0
while con==1:
  ans=ans*a[i]
  i+=1
  if ans>mod and i!=n:
    ans=1
    why=1
  elif ans>mod and i==n:
    con=0
    ans=1
    why=1
  elif i==n:
    con=0
if ans==0:
  print(0)
elif why==1:
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,k=map(int,input().split())
mod=998244353
ans=0
import math

  
kk=n-k
#print(kk)
color=m*(m-1)**(kk-1)%mod
#print(color)
com=math.factorial(n-1)//(math.factorial(n-kk)*math.factorial(kk-1))
while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(com%mod)%mod
  com=com*(n-kk)//kk
  kk+=1
  ans+=now
  ans=ans%mod
  #print(kk)
  #print(now)
  #print("color",color,"com",com)
print(ans)
  

Fixed submission:
n,m,k=map(int,input().split())
ans=0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


  
kk=n-k
#print(kk)
color=m*(m-1)**(kk-1)%mod
#print(color)
while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(cmb((n-1),(n-kk),mod))%mod
  kk+=1
  ans+=now
  ans=ans%mod
  #print(kk)
  #print(now)
  #print("color",color,"com",com)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[]
ans=0
for i in range(n):
  aa=str(input())
  if aa in a:
    b=0
  else:
    a.append(aa)
    ans+=1
print(ans)

Fixed submission:
n=int(input())
a={}
ans=0
for i in range(n):
  aa=str(input())
  if aa in a:
    b=0
  else:
    a[aa]=i
    ans+=1
    #print(i)
print(ans)
#print(a)
Buggy python submission (verdict: Time Limit Exceeded):
s=str(input())
n=len(s)
ans=0
l=[0 for i in range(2019)]
for i in range(n):
  t=int(s[i:])
  l[t%2019]+=1
#print(l[1817])
ans+=l[0]
l[0]=0
for i in l:
  ans+=int(i*(i-1)//2)
print(ans)

Fixed submission:
s=str(input())
n=len(s)
ans=0
l=[0 for i in range(2019)]
now=l[int(s[n-1])]
r=1
for i in range(1,n+1):
  now=(now+int(s[-i])*r)%2019
  l[now]+=1
  r=r*10
  r=r%2019
ans+=l[0]
for i in l:
  ans+=int(i*(i-1)//2)
print(ans)
#print(l)

Buggy python submission (verdict: Time Limit Exceeded):
n=str(input())
ans=0
nn=len(n)
for i in range(0,nn-3):
  for j in range(i+3,nn+1):
    now=n[i:j]
    now=int(now)
    if now%2019==0:
      ans+=1
print(ans)

Fixed submission:
s=str(input())
n=len(s)
ans=0
l=[0 for i in range(2019)]
now=l[int(s[n-1])]
r=1
for i in range(1,n+1):
  now=(now+int(s[-i])*r)%2019
  l[now]+=1
  r=r*10
  r=r%2019
ans+=l[0]
for i in l:
  ans+=int(i*(i-1)//2)
print(ans)
#print(l)

Buggy python submission (verdict: Time Limit Exceeded):
n=str(input())
ans=0
for i in range(0,len(n)-1):
  for j in range(i+1,len(n)+1):
    now=n[i:j]
    now=int(now)
    if now%2019==0:
      ans+=1
print(ans)

Fixed submission:
s=str(input())
n=len(s)
ans=0
l=[0 for i in range(2019)]
now=l[int(s[n-1])]
r=1
for i in range(1,n+1):
  now=(now+int(s[-i])*r)%2019
  l[now]+=1
  r=r*10
  r=r%2019
ans+=l[0]
for i in l:
  ans+=int(i*(i-1)//2)
print(ans)
#print(l)