Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = input()
ans = 0
D = Counter(S)
id = 0
dic = {}
for k in D.keys():
    dic[k] = id
    id += 1
m = 0
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]
        m = max(m,dic[S[i]])
SSS = [[] for i in range(m+1)]
for i in range(N):
    SSS[OB[i]].append(i)

for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(i,lss):
            if i==j or ans>SSS[n][j]-SSS[n][i] or ans>N-SSS[n][j]:
                continue
            id = 0
            while True:
                if SSS[n][i]+id>=N or SSS[n][j]+id>=N or SSS[n][i]+id>=SSS[n][j]:
                    break
                if S[SSS[n][i]+id]==S[SSS[n][j]+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
right = 0
for left in range(N):
    while S[left:right + 1] in S[right + 1:]:
        ans = max(ans, right + 1 - left)
        right += 1
print(ans)
### BUGGY CODE ###

N = int(input())
p = list(map(int, input().split()))

ans = 0
for i, j in enumerate(p):
    if i == 0:
        ans += 1
        continue
    
    for k in p[:i]:
        if j < k:
            continue
        else:
            break
    else:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))

minval = p[0]
ans = 1
for i in p:
    if i < minval:
        ans += 1
        minval = i

print(ans)
### BUGGY CODE ###

N = int(input())
ans = 1
A = list(map(int, input().split()))

for i in range(N):
  ans = ans * A[i]

if ans > 10 ** 18:
  print('-1')
else:
  print(ans)

### FIXED CODE ###

N = int(input())
ans = 1
A = list(map(int, input().split()))
flag = 0

for j in range(len(A)):
  if A[j] == 0:
    flag = 1
    ans = 0

if flag == 0:
  for i in range(N):
    ans = ans * A[i]
    if ans > 10 ** 18:
      break


if ans > 10 ** 18:
  print('-1')
else:
  print(ans)
### BUGGY CODE ###

from collections import deque

n, k = map(int, input().split())
ps = list(map(int, input().split()))
ps = [(p + 1)/2 for p in ps]
# print(ps)

d = deque()
vmax = 0
for p in ps:

    if len(d) == k:
        old = d.popleft()
        new = p
        d.append(new)
        if sum(d) > vmax:
            vmax = sum(d)
    else:
        d.append(p)
        vmax += p
    # print(vmax, d)

print(vmax)






### FIXED CODE ###

from collections import deque

n, k = map(int, input().split())
ps = list(map(int, input().split()))
ps = [(p + 1)/2 for p in ps]
# print(ps)

d = deque()
vmax = 0
v = 0
for p in ps:

    if len(d) == k:
        old = d.popleft()
        new = p
        d.append(new)
        v = v + new - old
        if v > vmax:
            # print("v > vmax")
            vmax = v
    else:
        d.append(p)
        v += p
        vmax = v
    # print(vmax, v, d)

print(vmax)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [float('inf')] * n
cost[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j < 0:
            break
        else:
            cost[i] = min(cost[i], cost[i - j] + abs(h[i] - h[i - j]))
print(cost[n - 1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf')] * n
    cost[0] = 0
    for i in range(1, n):
        for j in range(1, k + 1):
            if i - j < 0:
                break
            else:
                cost[i] = min(cost[i], cost[i - j] + abs(h[i] - h[i - j]))
    print(cost[n - 1])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, X, M = map(int, input().split())
A = []
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

A.append(X)
if N > 1:
  for i in range(N-1):
    a = a ** 2 % M
    if A.count(a) >= 1:
      if a == 0:
        s = sum(A)
        break
      else:
        r0 = A.index(a)
        l = len(A[r0:])
        r = (N - i - 1) // l
        amari = (N - i - 1) % l
        s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
        break
    else:
      A.append(a)
      s += A[-1]
  
print(s)

### FIXED CODE ###

N, X, M = map(int, input().split())
A = [X]
A_dict = {X}
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(M+1):
  a = a ** 2 % M
  if a in A_dict:
    r0 = A.index(a)
    l = len(A[r0:])
    r = (N - i - 1) // l
    amari = (N - i - 1) % l
    s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
    break
  A.append(a)
  A_dict.add(a)
  s += A[-1]

print(s)
### BUGGY CODE ###


N=int(input())

S=[]
for n in range(N):
    s=input()
    s=''.join(sorted(s))
    S.append(s)

S=sorted(S)
total=0
for i in range(len(S)):
    key=S[i]
    for j in range(i+1,N):
        if key==S[j]:
            total+=1
        else:
            break

print(total)

### FIXED CODE ###


N=int(input())
S=[]
total=0

for s in range(N):
    tmp=input()
    S.append("".join(sorted(tmp)))

S=sorted(S)
S_key=list(set(S))
count=[0]*len(S_key)
S_dict=dict(zip(S_key,count))


for s in S:
    total+=S_dict[s]
    S_dict[s]+=1

print(total)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n,m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))

dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2,n+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))


### FIXED CODE ###

import sys
input=sys.stdin.readline

def fib(n):
    a, b = 1, 0
    for _ in range(n):
        a, b = a + b, a
    return b

n,m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
if len(a) >= 2:
    for i in range(m-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()

tmp = 0
ans = 1
for i in range(len(a)):
    ans *= fib(a[i]-tmp)
    tmp = a[i]+1
if tmp < n:
    ans *= fib(n-tmp+1)
print(ans%(10**9+7))
### BUGGY CODE ###

class Node:
  def __init__(self,data):
    self.left=None
    self.right=None
    self.data=data

class BST:
  def __init__(self,num_list):
    self.root=None
    for node in num_list:
      self.insert(node)

  def insert(self,data):
    n = self.root
    if n == None:
      self.root=Node(data)
      return
    else:
      while True:
        entry=n.data
        if data<entry:
          if n.left is None:
            n.left=Node(data)
            return
        elif data > entry:
          if n.right is None:
            n.right=Node(data)
            return
          n=n.right
        else:
          n.data=data
          return
  def search(self,search):
    n = self.root
    if n is None:
      return None
    else:
      lst=[]
      lst.append(n)
      while len(lst)>0:
        node=lst.pop()
        if node.data==search:
          return node.data
        if node.left is not None:
          lst.append(node.left)
        if node.right is not None:
          lst.append(node.right)
      return False

n=int(input())
A=list(map(int,input().split()))
bst=BST(A)
B=[]
for i in range(n):
  B.append(bst.search(A[i]))
  B=B[::-1]
print(*B)


### FIXED CODE ###

n=int(input())
A=list(input().split())
print(" ".join(A[::-2]+A[n%2::2]))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 1
for i in range(1,N):
    if P[i] < min(P[0:i]):
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 1
m = P[0]
for i in range(1,N):
    if P[i] < m:
        cnt += 1
        m = P[i]
print(cnt)
### BUGGY CODE ###

books1= list(map(int, input().split()))
i=0
while(i<len(books1)):
  if(books1[i]==0):
    print(i+1)
    break
    i+=1

### FIXED CODE ###

books1= list(map(int, input().split()))
i=0
while(i<len(books1)):
  if(books1[i]==0):
    break
  i+=1
print(i+1)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
l=[0]
c=0

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i] not in l and l[c]+1 == A[i]:
        l.append(A[i])
        c+=1

if l[-1]+1==A[-1]:
    l.append(A[-1])

print(N+1-len(l))


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
ne=1
c=0

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i]==ne:
        c+=1
        ne+=1
if A[-1]==ne:
    c+=1
print(N-c)
### BUGGY CODE ###

import copy
a=int(input())
b=int(input())
w=b
d=[0]*3
count=0
c=[int(i) for i in str(b)]
for i in range(a-len(c)):
    c.insert(0,0)
for i in range(0,1000,1):
    for j in range(2,-1,-1):
        d[j]=i%10
        i=i//10#ここまでは「０，０，０」とか
    for x in range(a-2):
        if d[0]==c[x]:
            for y in range(x+1,a-1):
                if d[1]==c[y]:
                    for z in range(y+1,a):
                        if d[2]==c[z]:
                            count+=1
                            break
                    break
            break
print(count)    

### FIXED CODE ###

import copy
a=int(input())
b=int(input())
w=b
d=[0]*3
count=0
c=[int(i) for i in str(b)]
for i in range(a-len(c)):
    c.insert(0,0)
for i in range(0,1000,1):
    for j in range(2,-1,-1):
        d[j]=i%10
        i=i//10#ここまでは「０，０，０」とか
    for x in range(a-2):
        if d[0]==c[x]:
            for y in range(x+1,a-1):
                if d[1]==c[y]:
                    for z in range(y+1,a):
                        if d[2]==c[z]:
                            count+=1
                            break
                    break
            break
print(count)
### BUGGY CODE ###

N = input()

ans = 0
while(True):
    changeFlg = False
    for a in range(len(N)-1):
        if N[a] != N[a + 1]:
            N = N[0:a] + N[a+2 : len(N)]
            ans += 2
            changeFlg = True
            break
    if  changeFlg == False:
        break

print(ans)

### FIXED CODE ###

S = input()
s = ['01', '10']
 
ans = 0
count = len(S)
i = 0
while count >= 2:
    if S[i:i + 2] in s:
        S = S[:i] + S[i + 2:]
        ans += 2
        count -= 1
        i -= 1
    else:
        i += 1
        count -= 1
 
print(ans)
### BUGGY CODE ###

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

cnt = 1
for i in range(1,N):
	if P[i] < min(P[:i]):
		cnt += 1
print(cnt)

### FIXED CODE ###

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

mi = 1000000
cnt = 0
for i in range(N):
	mi = min(P[i],mi)
	if P[i] <= mi:
		cnt += 1
print(cnt)
### BUGGY CODE ###

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


def primes(n):
    is_prime = [True] * (n + 1)
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return {i: True for i in range(n + 1) if is_prime[i]}

import fractions
def common_divisors(a, b):
    a = fractions.gcd(a, b)
    divisors =  [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
    if not 1 in divisors:
        divisors.append(1) 
    return divisors

import math

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

d = common_divisors(A, B)
p = set(primes(max(d)))
ans = 0
for x in d:
    if is_prime(x):
        ans += 1
#print(p)
#print(d)
print(ans)

### FIXED CODE ###

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


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

import math

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

import fractions
x = fractions.gcd(A, B)
divisors = make_divisors(x)
ans = 0
for d in divisors:
    if is_prime(d):
        ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        x[l][r] += 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            c[i][j] = c[i][j-1] + x[i][j]
    
    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        ans = 0
        for j in range(qp, qq+1):
            ans += c[j][qq] - c[j][qp-1]
        print(ans)


if __name__=='__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]
    z = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        x[l][r] += 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            c[i][j] = c[i][j-1] + x[i][j]

    for j in range(1, n+1):
        for i in range(1, n+1):
            z[i][j] = z[i-1][j] + c[i][j]
    
    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(z[qq][qq] - z[qq][qp-1] - z[qp-1][qq] + z[qp-1][qp-1])


if __name__=='__main__':
    main()
### BUGGY CODE ###

from heapq import heappush, nlargest

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]
    h = []
    for i in A:
        for j in B:
            for k in C:
                heappush(h, i + j + k)
    for i in nlargest(K, h):
        print(i)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import heappush, nlargest

def main():
    X, Y, Z, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]
    h = []
    for i in A:
        for j in B:
            heappush(h, i + j)
    H = []
    for i in nlargest(K, h):
        for j in C:
            heappush(H, i+j)
    for i in nlargest(K, H):
        print(i)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
import heapq
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
ans = 0
al = [ls[-1],ls[0]]
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(n):
    di = ls[:i]
    heapq.heapify(di)
    heapq.heappush(di,ls[i]//2)
    di.sort()
    ind = di.index(ls[i]//2)
    il,ir = ind,ind
    if ind > 0:
        il -= 1
    else:
        il = -1
    if ind < len(di)-1:
        ir += 1
    else:
        ir = -1
    c = 0
    if ir > 0:
        if il > 0:
            mx = max(combinations_count(ls[i],di[ir]),combinations_count(ls[i],di[il]))
            c = 1
        else:
            mx = combinations_count(ls[i],di[ir])
            c = 3
    else:
        if il > 0:
            mx = combinations_count(ls[i],di[il])
            c = 2
        else:
            mx = 0
    if mx > ans:
        ans = mx
    if ans == mx:
        if c == 1:
            if combinations_count(ls[i],di[ir]) >= combinations_count(ls[i],di[il]):
                al = [ls[i],di[ir]]
            else:
                al = [ls[i],di[il]]
        elif c == 2:
            al = [ls[i],di[il]]
        elif c == 3:
            al = [ls[i],di[ir]]
print(*al)

### FIXED CODE ###

import math
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
di = ls[:]
di.append(ls[-1]//2)
di.sort()
ind = di.index(ls[-1]//2)
il,ir = -1,-1
if ind > 0:
    il = ind - 1 
if ind < n-1:
    ir = ind + 1
if il < 0 or ir < 0:
    now = max(ir,il)
else:
    if ls[-1] % 2 == 0:
        if abs(ls[-1]//2 - di[ir]) < abs(ls[-1]//2 - di[il]):
            now = di[ir]
        else:
            now = di[il]
    else:
        if min(abs(ls[-1]//2 - di[ir]),abs(ls[-1]//2 + 1 - di[ir])) < min(abs(ls[-1]//2 - di[il]),abs(ls[-1]//2 + 1 - di[il])):
            now = di[ir]
        else:
            now = di[il]
print(ls[-1],now)
### BUGGY CODE ###


N = int(input())
I = input()

R = []
G = []
B = []
for i in range(N):
    if I[i] == 'R':
        R.append(i)
    if I[i] == 'G':
        G.append(i)
    if I[i] == 'B':
        B.append(i)

ans = 0

for a in R:
    for b in G:
        for c in B:
            n = sorted([a, b, c])
            if( (n[2] - n[1]) != (n[1] - n[0]) ):
                ans += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
I = input()

R =0
G =0
B =0
for i in range(N):
    if (I[i] == 'R'):
        R+=1
    if (I[i] == 'G'):
        G+=1
    if (I[i] == 'B'):
        B+=1


sum = R * G * B

for i in range(N):
    for j in range(i+1,N):
        if I[i] != I[j]:
            k = j + j - i
            if k >= N:
                continue
            if I[i] != I[k] and I[j] != I[k]:
                sum -= 1

print(sum)
### BUGGY CODE ###

k, s = (int(i) for i in input().split())
count = 0
for x in range(k+1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = (int(i) for i in input().split())
count = 0
for x in range(k+1):
    for y in range(k + 1):
        if s - (x + y) >= 0 and s - (x + y) <= k:
            count += 1

print(count)
### BUGGY CODE ###

def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  if (p,q) not in l:
    l.append((p,q))
parent = [i for i in range(n)]
for i,j in l:
  x = find(i)
  y = find(j)
  if x > y:
      x, y = y, x
  parent[y] = x
dic = {}
for i in parent:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
mx = 0
for i in dic.values():
    mx = max(mx,i)
print(mx)


### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split())
    uf1.union(a-1,b-1)

for i in range(n):uf1.find(i)
X = uf1.par

ans = [0]*n
for i in range(n):
    ans[X[i]] += 1

print(max(ans))
### BUGGY CODE ###

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0] * 3
V = UV[:,1] * 3
S,T = map(int,input().split())

rows = np.zeros(3*M, dtype=np.int32)
cols = np.zeros(3*M, dtype=np.int32)

rows[:M] = U
rows[M:2*M] = U + 1
rows[2*M:] = U + 2
cols[:M] = V + 1
cols[M:2*M] = V + 2
cols[2*M:] = V

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

### FIXED CODE ###

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)
### BUGGY CODE ###

def f(scores, d):
    if len(scores) == 1:
        if scores[0] % 10 == d:
            res = 0
        else:
            res = scores[0]
    else:
        f1 = scores[0] + f(scores[1:], get_fld(scores[0], d))
        if f1 % 10 == d:
            f1 = 0
        f2 = f(scores[1:], d)
        res = max(f1, f2)
    return res
 
def get_fld(score, d):
    res = d - score % 10
    if res < 0:
        res += 10
    return res     
 
N = int(input())
scores = []
for _ in range(N):
    scores.append(int(input()))
print(f(scores, 0))

### FIXED CODE ###


def f(scores):
    res = sum(scores)
    if res % 10 == 0:
        candidates = list(score for score in scores if score % 10 != 0)
        if candidates:
            res -= min(candidates)
        else:
            res = 0
    return res
 
N = int(input())
scores = []
for _ in range(N):
    scores.append(int(input()))
print(f(scores))
### BUGGY CODE ###

import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
POWER = []
cur = 1#Nc0
for k in range(K+1):
    NcK.append(cur % MOD)
    cur *= (N-1-k)
    if k==K:break
    cur //= (k+1)    

ans = 0
Power = 1
for k in range(N-1-K):#M-1**n-1-K
    Power *= M-1
    Power %= MOD

for k in range(K,-1,-1):
    ans += Power * NcK[k]
        #M-1 ** N-1-k ということは…？
    if k:
        Power *= M-1

print((M*ans)%MOD)


### FIXED CODE ###

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
POWER = []
cur = 1#Nc0
for k in range(K+1):
    NcK.append(cur)
    cur *= (N-1-k)* mod_inv(k+1,MOD)
    cur %= MOD    

ans = 0
Power = 1
for k in range(N-1-K):#M-1**n-1-K
    Power *= M-1
    Power %= MOD

for k in range(K,-1,-1):
    ans += Power * NcK[k]
        #M-1 ** N-1-k ということは…？
    if k:
        Power *= M-1
        Power %= MOD
    

print((M*ans)%MOD)