Harryxun/stf_run huggingface dataset:
import sys  
import numpy as np

input = sys.stdin.readline

S_ = input()
T = input()

S_ = list(S_)[:-1]
T = list(T)[:-1]

for i in range(len(S_)-len(T)+1):
    part = S_[-len(T):]
    j = False
    for k in range(len(part)-1,-1,-1):
        if part[k] == "?":
            if k==0:
                j = True
        elif part[k] == T[k]:
            if k==0:
                j = True

        else:
            break
    if j:
        break


if j:
    for p in range(len(T)):
        S_[len(S_)-len(T)-i+p] = T[p]
    # print("*",S_)
    for k in range(len(S_)):
        if S_[k] == "?":
            S_[k] = "a"

    print("".join(S_))
else:
    print("UNRESTORABLE")

### FIXED CODE ###


import sys  
import numpy as np

input = sys.stdin.readline

S_ = input()
T = input()

S_ = list(S_)[:-1]
T = list(T)[:-1]

j = False
for i in range(len(S_)-len(T)+1):
    if i==0:
        part = S_[-len(T):]
    else :
        part = S_[-len(T)-i:-i]
    j = False
    for k in range(len(part)-1,-1,-1):
        if part[k] == "?":
            if k==0:
                j = True
            continue
        elif part[k] == T[k]:
            if k==0:
                j = True
        else:
            break
    if j:
        break


if j:
    for p in range(len(T)):
        S_[len(S_)-len(T)-i+p] = T[p]
    # print("*",S_)
    for k in range(len(S_)):
        if S_[k] == "?":
            S_[k] = "a"

    print("".join(S_))
else:
    print("UNRESTORABLE")
N = int(input())
a = [0]*10**4
a = [0]+a
x = 0
y = 0
z = 0
total = 0
for i in range(1,N+1):
  x = i
  for j in range(i,N+1):
    y = j
    for k in range(i,j+1):
      z = k
      total = int(((x+y)**2+(y+z)**2+(z+x)**2)/2)
      if(x==y and y==z):
        a[total]+=1
      elif(x==y or y==z or z==x):
        a[total]+=3
      else:
        a[total]+=6
for l in range(1,N+1):
  print(a[l])

### FIXED CODE ###

N = int(input())
a = [0]*10**5
a = [0]+a
x = 0
y = 0
z = 0
total = 0
for i in range(1,101):
  x = i
  for j in range(i,101):
    y = j
    for k in range(i,j+1):
      z = k
      total = int(((x+y)**2+(y+z)**2+(z+x)**2)/2)
      if(x==y and y==z):
        a[total]+=1
      elif(x==y or y==z or z==x):
        a[total]+=3
      else:
        a[total]+=6
for l in range(1,N+1):
  print(a[l])
h, w = map(int, input().split())
s = [input() for _ in range(h)]

is_used = [[False] * w for _ in range(h)]

di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]


def dfs(i, j):
    if s[i][j] == '#':
        cnt_w, cnt_b = 0, 1
    else:
        cnt_w, cnt_b = 1, 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        if is_used[ni][nj]:
            continue
        if s[i][j] == s[ni][nj]:
            continue

        is_used[ni][nj] = True
        cw, cb = dfs(ni, nj)
        cnt_w += cw
        cnt_b += cb
    return (cnt_w, cnt_b)


ans = 0
for i in range(h):
    for j in range(w):
        if not is_used[i][j]:
            is_used[i][j] = True
            cnt_w, cnt_b = dfs(i, j)
            ans += cnt_w * cnt_b

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
s = [input() for _ in range(h)]

is_used = [[False] * w for _ in range(h)]

di = [+1, 0, -1, 0]
dj = [0, +1, 0, -1]


def dfs(i, j):
    if s[i][j] == '#':
        cnt_w, cnt_b = 0, 1
    else:
        cnt_w, cnt_b = 1, 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni < 0 or ni >= h or nj < 0 or nj >= w:
            continue
        if is_used[ni][nj]:
            continue
        if s[i][j] == s[ni][nj]:
            continue

        is_used[ni][nj] = True
        cw, cb = dfs(ni, nj)
        cnt_w += cw
        cnt_b += cb
    return (cnt_w, cnt_b)


ans = 0
for i in range(h):
    for j in range(w):
        if not is_used[i][j]:
            is_used[i][j] = True
            cnt_w, cnt_b = dfs(i, j)
            ans += cnt_w * cnt_b

print(ans)
N, K = [int(x) for x in input().split(' ')]
m = 10**9 + 7
import math
def combination(n, r):
  return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  
for k in range(1, K+1):
  print(combination(N-K+1, k) % m * combination(K-1, k-1) % m)


### FIXED CODE ###

N, K = [int(x) for x in input().split(' ')]
m = 10**9 + 7
fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i
  
def combination(n, r):
  return fact[n] // fact[r] // fact[n-r]
  
for k in range(1, K+1):
  print(combination(N-K+1, k) % m * combination(K-1, k-1) % m)
class Dice:
    def __init__(self, labels):
        self.labels = labels
        self.up = labels[0]
        self.front = labels[1]
        self.right = labels[2]
        self.left = labels[3]
        self.back = labels[4]
        self.down = labels[5]
    def east(self):
        self.up, self.right, self.down, self.left = self.left, self.up, self.right, self.down
        self.update_labels()
    def north(self):
        self.up, self.back, self.down, self.front = self.front, self.up, self.back, self.down
        self.update_labels()
    def south(self):
        self.up, self.front, self.down, self.back = self.back, self.up, self.front, self.down
        self.update_labels()
    def west(self):
        self.up, self.left, self.down, self.right = self.right, self.up, self.left, self.down
        self.update_labels()
    def clockwise(self):
        self.front, self.left, self.back, self.right = self.right, self.front, self.left, self.back
        self.update_labels()
    def counterclockwise(self):
        self.front, self.right, self.back, self.left = self.left, self.front, self.right, self.back
        self.update_labels()
    def set_up(self, up):
        for i in range(6):
            if up == self.up:
                break
            if i % 2:
                self.east()
            else:
                self.north()
    def set_front(self, front):
        while True:
            if front == self.front:
                break
            self.clockwise()
    def update_labels(self):
        self.labels = [self.up, self.front, self.right, self.left, self.back, self.down]

dice_1 = Dice(list(map(int, input().split())))
dice_2 = Dice(list(map(int, input().split())))
flag = False
for i in range(30):
    if dice_1.labels == dice_2.labels:
        flag = True
        break
    if i % 5 == 0:
        if i % 10 == 0:
            dice_2.east()
        else:
            dice_2.north()
    else:
        dice_2.clockwise()
if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

class Dice:
    def __init__(self, labels):
        self.up = labels[0]
        self.front = labels[1]
        self.right = labels[2]
        self.left = labels[3]
        self.back = labels[4]
        self.down = labels[5]
    def east(self):
        self.up, self.right, self.down, self.left = self.left, self.up, self.right, self.down
    def north(self):
        self.up, self.back, self.down, self.front = self.front, self.up, self.back, self.down
    def south(self):
        self.up, self.front, self.down, self.back = self.back, self.up, self.front, self.down
    def west(self):
        self.up, self.left, self.down, self.right = self.right, self.up, self.left, self.down

dice = Dice(list(map(int, input().split())))
for cmd in list(input()):
    if cmd == 'E':
        dice.east()
    if cmd == 'N':
        dice.north()
    if cmd == 'S':
        dice.south()
    if cmd == 'W':
        dice.west()
print(dice.up)
n,a = [input() for i in range(2)]

x=n%500 

if x<=a:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n,a = [int(input()) for i in range(2)]

x=n%500 

if x<=a:
  print('Yes')
else:
  print('No')
n=int(input())
a=sorted(list(map(int,input().split())))
b=a.pop(-1)
d=0
for i in b:
    c=1
    A=a[i]
    for j in range(i+1)[A:i+1]:
        c*=j
    for k in range(1,A+1):
        c/=k
    if d < c:
        d=c
print(b,d)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=a.pop(-1)
print(b,min(a,key=lambda x :abs(b-2*x)))
from sys import stdin
import bisect
from itertools import groupby
 
n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
 
li.sort()
lin = []

for key, value in groupby(li):
    lin.append((key,len(list(value))))

if lin[0][0] != 0 or lin[0][1] > 1:
    print(0)
    exit()

point = 1
for i in range(1,len(lin)):
    if lin[i-1][0] +1 != lin[i][0]:
        print(0)
        exit()
    point *= lin[i-1][1]**lin[i][1]

print(point%998244353)

### FIXED CODE ###

from sys import stdin
import fractions

n = int(stdin.readline().rstrip())

if n %2 == 1:
    print(n//2)
else:
    print(n//2-1)
import numpy as np
N, K=map(int,input().split(' '))
H=np.array(list(map(int,input().split(' '))))
dp=np.zeros(N)

for i in range(N):
	if i==0:
		continue
	elif i==1:
      	#0->1に移動するコストは1通り
		dp[i]=(np.abs(H[1]-H[0]))
	else:
      	#i>=2のときはiに移動するコストは
        #dp[i-j]+abs(H[i-j]-H[i]) (j=1,...,min(K,i)) の最小値]
        dp[i] = np.min(dp[min(0,i-K):i] + np.abs(H[min(0,i-K):i] - H[i]))
		
print(dp[N-1])

### FIXED CODE ###

N, K=map(int,input().split(' '))
H=list(map(int,input().split(' ')))
dp=[]

for i in range(N):
	if i==0:
		dp.append(0)
	elif i==1:
		dp.append(abs(H[1]-H[0]))
	else:
		d = min([ dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,K+1) if i-j>=0])
		dp.append(d)
		
print(dp[N-1])
p = [2,1]
n = int(input())

if n >= 3:
    for i in range(2,n+1):
        p.append(p[i-2]+p[i-1])

print(p[n])

### FIXED CODE ###

p = [2,1]
n = int(input())

if n >= 2:
    for i in range(2,n+1):
        p.append(p[i-2]+p[i-1])

print(p[n])
n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower+s[k:])

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])
X = int(input())
y = 1
z = X
for i in range(2,int((X**(1/2)))+1):
  if X%i==0:
    y = i
    z = x//i
    break
    
for a in range(10**5):
  b = a-y
  if a**4 + (a**3)*b + (a**2)*(b**2) + a*(b**3) + b**4==z:
    print(a,b)
    exit()

### FIXED CODE ###

X = int(input())
for A in range(-1000,1001):
  for B in range(-1000,1001):
    if A**5-B**5==X:
      print(A,B)
      exit()
from math import gcd
import sys

N, M = map(int, input().split())
S = input()
T = input()

d = gcd(N, M)
m = N * M // d

for i in range(d):
    if S[i * (N // d)] != T[i * (M // d)]:
        print(-1)
        sys.exit()

print(m)


### FIXED CODE ###

# from math import gcd
from fractions import gcd
import sys

N, M = map(int, input().split())
S = input()
T = input()

d = gcd(N, M)
m = N * M // d

for i in range(d):
    if S[i * (N // d)] != T[i * (M // d)]:
        print(-1)
        sys.exit()

print(m)
import copy
import sys
li = list('abcdefghijklmnopqrstuvwxyz')
r = []
for i in range(len(s)-len(t)+1):
    ss = list(s)
    print(i)
    lo = [1 if ((s[i + j] == t[j]) or (s[i + j] == '?')) else 0 for j in range(len(t))]
    print(lo)
    if all(lo):
        ss[i:i+ len(t)] = t
        rs = ''.join(ss)
        rs = rs.replace('?','a')
        r += [rs]

if len(r) == 0:
    print('UNRESTORABLE')
    sys.exit()
r = sorted(r)
print(r[0])

### FIXED CODE ###

import copy
import sys

s = input()
t = input()
li = list('abcdefghijklmnopqrstuvwxyz')
r = []
for i in range(len(s)-len(t)+1):
    ss = list(s)
#     print(i)
    lo = [1 if ((s[i + j] == t[j]) or (s[i + j] == '?')) else 0 for j in range(len(t))]
#     print(lo)
    if all(lo):
        ss[i:i+ len(t)] = t
        rs = ''.join(ss)
        rs = rs.replace('?','a')
        r += [rs]

if len(r) == 0:
    print('UNRESTORABLE')
    sys.exit()
r = sorted(r)
print(r[0])
print("Yes" if sorted(input()).join("") == "abc" else "No")

### FIXED CODE ###

print("Yes" if "".join(sorted(input())) == "abc" else "No")
number = int(input())
i = int(number / 111)
if number % 111 != 0:
  i += 1
 print(i * 111)

  
  

### FIXED CODE ###

n = int(input())
i = int(n / 111)
if n % 111 != 0:
    i += 1
print(i * 111)
N=int(input())
l=list(map(int,input().split()))
l=sorted(l)

if l[-1] < sum([:-1]):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
l=sorted(l)

if l[-1] < sum(l[:-1]):
  print("Yes")
else:
  print("No")
N, M = (int(x) for x in input().split())
par = [x for x in range(N)]

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

for i in range(M):
    x,y,_ = map(int, input().split())
    rx = root(x-1)
    ry = root(y-1)
    if rx != ry:
        par[rx] = ry

rlist = set()
for i in range(N):
    rlist.add(root(i))

print(len(rlist))



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.p[ry] = rx

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

    for i in range(M):
        x,y,_ = map(int, input().split())
        u.unite(x-1, y-1)

    rlist = set()
    for i in range(N):
        rlist.add(u.root(i))

    print(len(rlist))

if __name__ == '__main__':
    main()
N , M = map(int,input().split())
L = []
for _ in range(M):
    m = tuple(map(int,input().split()))
    L.append(m)
if N == 1:
    for ans in range(0,10):
        ans = str(ans)
        for x in L:
            if ans[x[0] - 1] != str(x[1]):
                break
        else:
            eixt()
    print(-1)
    exit()
else:
    for ans in range(10 ** (N - 1),10 ** N ):
        ans = str(ans)
        for x in L:
            if ans[x[0] - 1] != str(x[1]):
                break
        else:
            print(ans)
            exit()
    print(-1)
    exit()



### FIXED CODE ###

N , M = map(int,input().split())
L = []
for _ in range(M):
    m = tuple(map(int,input().split()))
    L.append(m)
if N == 1:
    for ans in range(0,10):
        ans = str(ans)
        for x in L:
            if ans[x[0] - 1] != str(x[1]):
                break
        else:
            print(ans)
            exit()
    print(-1)
    exit()
else:
    for ans in range(10 ** (N - 1),10 ** N ):
        ans = str(ans)
        for x in L:
            if ans[x[0] - 1] != str(x[1]):
                break
        else:
            print(ans)
            exit()
    print(-1)
    exit()
#79B
N=int(input())
import ita
data=ita.array.make1d(N+1)
data[0]=2
data[1]=1
for i in range(2,N+1):
    data[i]=data[i-1]+data[i-2]
print(data[N])  

### FIXED CODE ###

#79B
N=int(input())
data=[2]
data.append(1)
for i in range(2,N+1):
    data.append(data[i-1]+data[i-2])
    
print(data[N])
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
CB = []
for i in range(M):
    B, C = list(map(int, input().split()))
    CB.append([C, B])
 
A.sort()
A.reverse()
CB.sort()
CB.reverse()
 
ans = 0
a_index = 0
cb_index = 0
f = 0
 
while True:
    if f = 1 or A[a_index] >= CB[cb_index][0]:
        ans += A[a_index]
        a_index += 1
        N -= 1
        if N == 0:
            break
    else:
        if N <= CB[cb_index][1]:
            ans += CB[cb_index][0] * N
            break
        else:
            ans += CB[cb_index][0] * CB[cb_index][1]
            N -= CB[cb_index][1]
            cb_index += 1
            if len(CB) == cb_index:
              f = 1
 
print(ans)
 

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
CB = []
for i in range(M):
    B, C = list(map(int, input().split()))
    CB.append([C, B])
 
A.sort()
A.reverse()
CB.sort()
CB.reverse()
 
ans = 0
a_index = 0
cb_index = 0
f = 0
 
while True:
    if f == 1 or A[a_index] >= CB[cb_index][0]:
        ans += A[a_index]
        a_index += 1
        N -= 1
        if N == 0:
            break
    else:
        if N <= CB[cb_index][1]:
            ans += CB[cb_index][0] * N
            break
        else:
            ans += CB[cb_index][0] * CB[cb_index][1]
            N -= CB[cb_index][1]
            cb_index += 1
            if len(CB) == cb_index:
              f = 1
 
print(ans)
a=int(input())
b=0
xy = [map(int, input().split()) for _ in range(a)]
x, y = [list(i) for i in zip(*xy)]
for i in range(a-2):
  if x[i]==y[i] and x=[i+1]==y[i+1] and x=[i+2]==y[i+2]:
    b=b+1
if b==0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

a=int(input())
b=0
xy = [map(int, input().split()) for _ in range(a)]
x, y = [list(i) for i in zip(*xy)]
for i in range(a-2):
  if x[i]==y[i] and x[i+1]==y[i+1] and x[i+2]==y[i+2]:
    b=b+1
if b==0:
  print("No")
else:
  print("Yes")
N, Q = map(int, input().split())
S = input()
data = [0] * (N+1)
for i in range(N):
    data[i+1] = data[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r =map(int, input().split())
    print(data[r-1] - t[l-1])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
data = [0] * (N+1)
for i in range(N):
    data[i+1] = data[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r =map(int, input().split())
    print(data[r-1] - data[l-1])
class coordinates:
  def __init__(self, x, y):
    self.x = x
    self.y = y
 
def koch(n, a, b):
  if n == 0:
    return
  s = coordinates((2*a.x + b.x)/3, (2*a.y + b.y)/3)
  t = coordinates((a.x + 2*b.x)/3, (a.y + 2*b.y)/3)
  ux = (t.x - s.x)*cos(pi/3) - (t.y - s.y)*sin(pi/3) + s.x
  uy = (t.x - s.x)*sin(pi/3) + (t.y - s.y)*cos(pi/3) + s.y
  u = coordinates(ux, uy)
  
  koch(n-1, a, s)
  print  s.x, s.y
  koch(n-1, s, u)
  print  u.x, u.y
  koch(n-1, u, t)
  print  t.x, t.y
  koch(n-1, t, b)
  
n = input()
  
p1 = coordinates(0.0, 0.0)
p2 = coordinates(100.0, 0.0)
  
print p1.x, p1.y
koch(n, p1, p2)
print p2.x, p2.y

### FIXED CODE ###

import math

rad = math.radians(60)

class coordinates:
  def __init__(self, x, y):
    self.x = x
    self.y = y
 
def koch(n, a, b):
  if n == 0:
    return
  s = coordinates((2.0*a.x + b.x)/3.0, (2.0*a.y + b.y)/3.0)
  t = coordinates((a.x + 2.0*b.x)/3.0, (a.y + 2.0*b.y)/3.0)
  ux = (t.x - s.x)*math.cos(rad) - (t.y - s.y)*math.sin(rad) + s.x
  uy = (t.x - s.x)*math.sin(rad) + (t.y - s.y)*math.cos(rad) + s.y
  u = coordinates(ux, uy)
  
  koch(n-1, a, s)
  print  s.x, s.y
  koch(n-1, s, u)
  print  u.x, u.y
  koch(n-1, u, t)
  print  t.x, t.y
  koch(n-1, t, b)
  
n = input()
  
p1 = coordinates(0.0, 0.0)
p2 = coordinates(100.0, 0.0)
  
print p1.x, p1.y
koch(n, p1, p2)
print p2.x, p2.y
class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        nodeB.addEdge(self.edges[0])
        self.dir = True
        self.vec = None

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
    def another(self):
        return self.edge.edges[1 if self.edge.edges[0] == self else 0]

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
        self.parent = None
        self.judge = 0
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return str((self.id, None if self.parent is None else self.parent.node.id))

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

nodes = [Node(i) for i in range(N+1)]
bridges = []
for A, B in (map(int, input().split()) for _ in range(N)):
    bridges.append(Bridge(nodes[A], nodes[B]))

s = [(None, nodes[1])]
idx = 0
ok = True
while idx < len(s):
    pre, cur = s[idx]
    idx += 1


    for nxt in cur.bridges:
        if nxt.node.judge <= 0:
            nxt.node.parent = nxt.another()
            cur.judge += 1
            nxt.edge.vec = (cur.id, nxt.node.id)
            s.append((cur, nxt.node))


    if cur.judge % 2 == 1:
        ok = not ok
        wrk = cur
        while wrk.parent is not None:
            br = wrk.parent.edge
            br.dir = not br.dir
            wrk = wrk.parent.node

if ok:
    for br in bridges:
        if br.dir:
            print("{} {}".format(br.vec[1], br.vec[0]))
        else:
            print("{} {}".format(br.vec[0], br.vec[1]))
else:
    print("-1")


### FIXED CODE ###

from collections import Counter

N= int(input())

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

x = Counter(a)

ok = False
if len(x) == 3 and len(a) % 3 == 0:
    for i in a:
        if x[i] != len(a) // 3:
            break
    else:
        w = 0
        for j in x:
            w ^= j
        if w == 0:
            ok = True
elif len(x) == 1:
    if x.get(0) is not None:
        ok = True
elif len(x) == 2 and len(a) % 3 == 0:
    if x.get(0) is not None and x[0] == len(a) // 3:
        ok = True

if ok:
    print("Yes")
else:
    print("No")
14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))

if n%2 == 1:
    print(0)
else:
    print(d[len(d)//2]-d[(len(d)//2)-1])
#!/usr/bin/env python3

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

if M == 1:
    if K >= cmb(N, 2):
        print(1)
    else:
        print(0)

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

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

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)
def gcd_t(s):
    if(len(s)==1):    return s[0]
    if(s[-2]==0):    return s[-1]
    else:
        if(len(s)==2):
            return gcd(s[0],s[1])
        m=gcd(s[-1],s[-2])
        s.pop()
        s.pop()
        s.append(m)
        return gcd_t(s)
    
def gcd(m,n):   
    if(n==0):    return m
    else:    return gcd(n,m%n)

x=[]
N,X=list(map(int,input().split()))
x=list(map(int,input().split()))
    
gcd_list=[]
for i in range(N):
    gcd_list.append(X-x[i])
    
print(abs(gcd_t(gcd_list)))

### FIXED CODE ###

def gcd(m,n):   
    if(n==0):    return m
    else:    return gcd(n,m%n)

x=[]
N,X=list(map(int,input().split()))
x=list(map(int,input().split()))
    
ans=abs(X-x[0])
for i in range(N):
    ans=gcd(ans,abs(x[i]-X))

print(ans)
a,b,c = map(int,input())
print(min(c-(a-b),0))

### FIXED CODE ###

a,b,c = map(int,input().split())
if c>a-b:
    print(c-a+b)
else:
    print(0)
n = int(input())
print(800 * n - (n // 15) * 200

### FIXED CODE ###

n = int(input())
print(800 * n - (n // 15) * 200)
N = int(input())
divisor = [i for i in range(2, N // 2 + 1) if N % i == 0]
XY = [div + N // div - 2 for div in divisor]
print(min(D))

### FIXED CODE ###

import math
N = int(input())
n = int(math.sqrt(N))
divisor = [i for i in range(1, n + 1) if N % i == 0]
XY = [div + N // div - 2 for div in divisor]
print(min(XY))