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

import itertools
from collections import Counter
N = int(input().strip())
seq_list = [Counter(input().strip()) for _ in range(N)]
print(len([1 for i,j in itertools.combinations(range(N), 2) if seq_list[i] == seq_list[j]]))


### FIXED CODE ###

import itertools
N = int(input().strip())
seq_list = [''.join(sorted(input().strip())) for _ in range(N)]
hash = {}
result = 0
for seq in seq_list:
  if seq in hash:
    result += hash[seq]
    hash[seq] += 1
  else:
    hash[seq] = 1
print(result)
### BUGGY CODE ###

#じゅっぴーフロイド
from collections import*
from itertools import*
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[(i,j)] = min(d[(i,j)],d[(i,k)] + d[(k,j)])
    return d

##############################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数
d = defaultdict(lambda:float("inf"))
*r,=map(int,input().split())
#d[u][v] : 辺uvのコスト(存在しないときはinf)

for i in range(w):
    x,y,z = map(int,input().split())
    d[(x,y)] = z
    d[(y,x)] = z
#print(d)
for i in range(n):
    d[(i,i)] = 0 #自身のところに行くコストは０
d=warshall_floyd(d)
#print(d)
#print([d[i] for i in permutations(r)])
print(min(sum(d[(s,t)]for s,t in zip(i,i[1:]))for i in permutations(r)))

### FIXED CODE ###

from itertools import*
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
*R,=map(int,input().split())

table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d,p=floyd_warshall(csgraph=table, directed=False, return_predecessors=True)
cost=[sum(d[i[j]-1][i[j+1]-1]for j in range(r-1))for i in permutations(R)]
print(int(min(cost)))
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
count=0
for ai in a:
    if ai%2==0:
        while ai!=1:
            ai/=2
            count+=1
print(count)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
count=0
for ai in a:
        while ai%2==0:
            ai=ai/2
            count+=1
print(count)
### BUGGY CODE ###

import itertools

import numpy as np

H, W, M = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(M)]

A = np.zeros(H, dtype=np.int64)
B = np.zeros(W, dtype=np.int64)

for h, w in HW:
    A[h - 1] += 1
    B[w - 1] += 1

maxA = np.max(A)
maxB = np.max(B)

# 最大値を取るindex
ind_A = np.arange(H)[A == maxA]
ind_B = np.arange(W)[B == maxB]

# 解の候補の数
nn = len(ind_A) * len(ind_B)

# Mより候補の数のほうが多いとok
# 少ないときはM以下なので可算
ans = maxA + maxB
if nn <= M:
    for h, w in itertools.product(ind_A, ind_B):
        if [h + 1, w + 1] not in HW:
            break
    else:
        ans -= 1

print(ans)


### FIXED CODE ###

import itertools

import numpy as np


def main():
    H, W, M = map(int, input().split())
    HW = [list(map(int, input().split())) for _ in range(M)]

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in HW:
            if A[h - 1] == maxA and B[w - 1] == maxB:
                nn -= 1

    print(ans if nn else ans - 1)


main()
### BUGGY CODE ###


import sys


def max_sum_seq(lis):
#    r = []
    m = 0
    l = len(lis)
    for n in range(1, l+1):
        for s in every_slice(lis, n):
            sm = sum(s)
            if sm > m:
                m = sm
    return m
#        r = r + every_slice(lis, n)
#    return max(map((lambda r1: reduce((lambda x, y: x + y), r1, 0)), r))

def every_slice(lis, n):
#    r = []
    l = len(lis)
    for i in range(l-n+1):
        yield lis[i:i+n]
#    return r


#input_file = open(sys.argv[1], "r")

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    lis = []
    for i in range(n):
        lis.append(int(sys.stdin.readline()))
    print max_sum_seq(lis)

### FIXED CODE ###


import sys


def max_sum_seq(lis):
    m = 0
    lis = compress(lis)
    l = len(lis)

    max_val = lis[0]
    for i in xrange(0, l):
        for j in xrange(i, l):
            if j == i:
                tmp_val = lis[j]
            else:
                tmp_val = tmp_val + lis[j]
            max_val = max(max_val, tmp_val)
    return max_val

def compress(tmp_lst):
    lim = len(tmp_lst)
    lst = []
    index = 0
    while index < lim:
        tmp = tmp_lst[index]
        index += 1
        while tmp > 0 and index < lim and tmp * tmp_lst[index] > 0:
            tmp += tmp_lst[index]
            index += 1
        lst.append(tmp)
    return lst


while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    lis = []
    for i in range(n):
        lis.append(int(sys.stdin.readline()))
    print max_sum_seq(lis)
### BUGGY CODE ###

import bisect
N=int(input())
As=list(map(int,input().split()))
Bs=list(map(int,input().split()))
Cs=list(map(int,input().split()))
As.sort()
Bs.sort()
Cs.sort()
pyout=0
for i in range(N):
    num1=bisect.bisect_left(Bs,Cs[i])
    for j in range(num1):
        num2=bisect.bisect_left(As,Bs[j])
        pyout+=num2
print(pyout)

### FIXED CODE ###

N=map(int,input().split())
A=sorted(list(map(int,input().split())))
B=list(map(int,input().split()))
C=sorted(list(map(int,input().split())))
 
def countA(target,L):
  ok=-1
  ng=len(L)
  while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if L[mid]<target:
      ok=mid
    else:
      ng=mid
  return (ok+1)
 
def countC(target,L):
  ok=len(L)
  ng=-1
  while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if L[mid]>target:
      ok=mid
    else:
      ng=mid
  return len(L)-ok
 
ans=0
for i in range(len(B)):
  data=B[i]
  ans+=(countA(data,A)*countC(data,C))
  
print(ans)
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=[int(x) for x in input().rstrip().split()]
A_s=list(set(A))
A_count=[]
cnt=0

A_count=[A.count(A_s[x]) for x in range(len(A_s))]
# for x in range(len(A_s)):
#   i=A.count(A_s[x])
#   A_count.append(i)



for i in A_count:
  if 2<=i:
    cnt+=(i*(i-1))//2



# [print(cnt) if A_count[A_s.index(A[i])]==1 else print(cnt-A_count[A_s.index(A[i])]+1) for i in range(N)]

for i in A:
  x=A_count[A_s.index(i)]
  if x==1:
    print(cnt)
  else:
    print(cnt-x+1)

### FIXED CODE ###

import collections
N=int(input())
A=[int(x) for x in input().rstrip().split()]
A_c=collections.Counter(A)
cnt=0

for i in A_c.values():
  cnt+=(i*(i-1))//2


for i in A:
  x=A_c[i]
  if x==1:
    print(cnt)
  else:
    print(cnt-x+1)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.99 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

def count_seq_l(s):
    tmp_cnt = 0
    for s_tmp in s[::-1]:
        if s_tmp == '<':
            tmp_cnt += 1
        else:
            break

    return tmp_cnt
def count_seq_r(s):
    tmp_cnt = 0
    for s_tmp in s:
        if s_tmp == '>':
            tmp_cnt += 1
        else:
            break
    return tmp_cnt

if __name__ == '__main__':
    S = input()
    res = 0
    for i in range(len(S) + 1):
        l_s = S[:i]
        r_s = S[i:]
        l_cnt = count_seq_l(l_s)
        r_cnt = count_seq_r(r_s)
        tmp = max(l_cnt, r_cnt)
        res += tmp
    print(res)
    

### FIXED CODE ###

if __name__ == '__main__':
    S = input()
    n = len(S)
    l_res = [0]
    r_res = [0]
    for i in range(n):
        if S[i] == '<':
            l_res.append(l_res[i] + 1)
        else:
            l_res.append(0)
    inv_S = S[::-1]

    for i in range(n):
        if inv_S[i] == '>':
            r_res.append(r_res[i] + 1)
        else:
            r_res.append(0)
    res = 0
    for l_cnt, r_cnt in zip(l_res, r_res[::-1]):
        res += max(l_cnt, r_cnt)
    print(res)
### BUGGY CODE ###

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

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        if 0<=s-(x+y)<=k:
            cnt+=1
print(cnt)
### BUGGY CODE ###

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

from bisect import bisect_left

if __name__ == '__main__':
    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    l = [int(input()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)


### FIXED CODE ###

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)
### BUGGY CODE ###

# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()


NM = list(map(int, input().split())) # 1行, 配列

N = NM[0]
M = NM[1]
H = list(map(int, input().split())) # 1行, 配列

AB=[]
while True:
  try:
    AB.append(list(map(int,input().split())))

  except:
    break;

good = 0

for i, item in enumerate(H):
  targetLoad = []
  for load in AB:
    t = list(set(load) - set([i+1]))
    if len(t) == 1:
      targetLoad.append(H[t[0]-1])
  if len(targetLoad) == 0:
      good = good + 1
  else:
    if max(targetLoad) < item:
      good = good + 1

print(good)

### FIXED CODE ###

# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()


N,M = map(int, input().split()) # 1行, 配列
H = list(map(int, input().split())) # 1行, 配列

AB={}

while True:
  try:
    A,B = map(int, input().split())
    AB.setdefault(A, []).append(H[B-1])
    AB.setdefault(B, []).append(H[A-1])
  except:
    break;

good = 0

for i, item in enumerate(H):

  try:
    targetLoad = AB[i+1]
    if max(targetLoad) < item:
      good = good + 1
  except:
    good = good + 1

print(good)
### BUGGY CODE ###

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

break_flag = 0
for i in range(len(num_list)):
    if num_list.count(num_list[i]) >= 2:
        break_flag = 1
        break

if break_flag == 1:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

import collections

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

c = collections.Counter(num_list)
if max(c.values()) == 1:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[]
c=[]

for i in range(m):
    ab.append(list(map(int,input().split())))
    c.append(list(map(int,input().split())))
    
for i in range(m):
    temp=0
    for j in range(len(c[i])):
        temp+=2**(c[i][j]-1)
    c[i]=temp
    #c[i]=(("0"*n)+bin(temp)[2:])[-n:]
   
dp=dict()

for i in range(2**n):
    dp[i]=10**9
    #dp[(("0"*n)+bin(i)[2:])[-n:]]=-1
    
dp[0]=0
    
#print(dp)
for i in range(m):
    for k,item in dp.items():
        dp[c[i]|k]=min(dp[c[i]|k],dp[k]+ab[i][0])

if dp[2**n-1]==10**9:
    print(-1)
else:
    print(dp[2**n-1])


### FIXED CODE ###

n,m=map(int,input().split())
ab=[]
c=[]

for i in range(m):
    ab.append(list(map(int,input().split())))
    c.append(list(map(int,input().split())))
    
for i in range(m):
    temp=0
    for j in range(len(c[i])):
        temp+=2**(c[i][j]-1)
    c[i]=temp
    #c[i]=(("0"*n)+bin(temp)[2:])[-n:]
   
dp=dict()

for i in range(2**n):
    dp[i]=10**9
    #dp[(("0"*n)+bin(i)[2:])[-n:]]=-1
    
dp[0]=0
    
#print(dp)
for i in range(m):
    for k,item in dp.items():
        dp[c[i]|k]=min(dp[c[i]|k],dp[k]+ab[i][0])

if dp[2**n-1]==10**9:
    print(-1)
else:
    print(dp[2**n-1])
### BUGGY CODE ###

N,X,M=map(int,input().split())
table=[X]

ans=X

for i in range(N-1):
    nx=table[i]**2
    nx%=M
    if nx in table:
        first=table.index(nx)
        oneloop=i+1-first
        rest=N-i-1
        loops=rest//oneloop
        totalofoneloop=sum(table[first:])
        ans+=totalofoneloop*loops
        remain=rest%oneloop
        ans+=sum(table[first:first+remain])
        print(ans)
        exit()
    else:
        table.append(nx)
        ans+=nx
 

print(ans)

### FIXED CODE ###

N,X,M=map(int,input().split())
table=[X]
visited=[-1]*M
visited[X]=1

ans=X

for i in range(N-1):
    nx=table[i]**2
    nx%=M
    if visited[nx]>0:
        first=table.index(nx)
        oneloop=i+1-first
        rest=N-i-1
        loops=rest//oneloop
        totalofoneloop=sum(table[first:])
        ans+=totalofoneloop*loops
        remain=rest%oneloop
        ans+=sum(table[first:first+remain])
        print(ans)
        exit()
    else:
        table.append(nx)
        visited[nx]=1
        ans+=nx
 

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

# 配るDP
# Hは1-index
import sys

input = sys.stdin.readline
n, k = map(int, input().split())
H = [0] + list(map(int, input().split()))
dp = [10 ** 10] * (n + 1)
dp[1] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i + j <= n:
            dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[n])


### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
#配るDPでやってみる
#dp[i]をi番目の足場まで行くときの最小コストとする。
dp=[float('inf')]*(2*n)
dp[0]=0
dp[1]=0
for i in range(1,n+1):
    for a in range(1,min(k+1,n-i+1)):
            dp[i+a]=min(dp[i+a], dp[i]+abs(H[i+a-1]-H[i-1]))
print(dp[n])
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for i in range(N):
    if max(L) <= i+1 <= min(R):
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
L_max = max(L)
L_min = min(R)

for i in range(N):
    if L_max <= i+1 <= L_min:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import Counter
from itertools import combinations

N = int(input())
S = input()
 
l = list(combinations(S,3))
print(len(Counter(l)))

### FIXED CODE ###

N = int(input())
S = input()

cnt = 0

for i in range(10):
    x100 = S.find(str(i))
    if x100 == -1:
        continue
    for j in range(10):
        x10 = S.find(str(j), x100 + 1)
        if x10 == -1:
            continue
        for k in range(10):
            if S.find(str(k), x10 + 1) != -1:
                cnt += 1
print(cnt)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()

for m in range(M):
    B,C = map(int,input().split())
    for i in range(B):
        if A[i] > C:
            break
        A[i] = C
    A.sort()

print(sum(A))


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)
 
ans = 0
b,c = BC.pop(0)
for i,a in enumerate(A):
    if b>=1:
        if c > a:
            ans += c
            b -= 1
        else:
            ans += a
    if b<=0:
        if len(BC)==0:
            ans += sum(A[i+1:])
            break
        else:
            b,c = BC.pop(0)
 
print(ans)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

childs = [0] * N
seen = [False] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD


def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    for nv in G[v]:
        if seen[nv]:
            nodes.append(N - childs[v] - 1)
        else:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = pow2[N - 1] - (sum(pow2[n] - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    for nv in G[v]:
        if not seen[nv]:
            dfs2(nv)
    return


dfs2(0)
denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
MOD = 998_244_353

p = MOD
N = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

# 事前計算した項を掛け合わせ
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

ans = 0
M_1_pwr = pow(M-1, N-1-K, MOD)
for j in range(K,-1,-1):
  tmp = 1
  tmp *= cmb(N-1,j,MOD)
  tmp *= M_1_pwr
  tmp %= MOD
  
  ans += tmp
  ans %= MOD
  
  M_1_pwr *= (M-1)
  M_1_per %= MOD
  
ans *= M
ans %= MOD

print(ans)

### FIXED CODE ###

Nn, M, K = map(int, input().split())
MOD = 998_244_353

p = MOD
N = Nn  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

# 事前計算した項を掛け合わせ
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

ans = 0
M_1_pwr = pow(M-1, Nn-1-K, MOD)
for j in range(K,-1,-1):
  tmp = 1
  tmp *= cmb(Nn-1,j,MOD)
  tmp *= M_1_pwr
  tmp %= MOD
  
  #print(cmb(Nn-1,j,MOD), tmp)
  
  ans += tmp
  ans %= MOD
  
  M_1_pwr *= (M-1)
  M_1_pwr %= MOD
  
ans *= M
ans %= MOD

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

import math
N = int(input())

def minus_2(n):
    ans = ''
    if n == 1:
        ans.append('1')
    else:
        while n != 1:
            if n % -2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans

ans = minus_2(N)

print(ans)

### FIXED CODE ###

import math
N = int(input())
 
def minus_2(n):
    ans = ''
    if n == 1:
        ans += '1'
    elif n == 0:
        ans += '0'
    else:
        while n != 1:
            if n % 2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans
 
print(minus_2(N))
### BUGGY CODE ###

N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
list.sort(A)
for _ in range(M):
    tmp = max(A)
    A[A.index(tmp)] = tmp // 2
print(str(sum(A)))

### FIXED CODE ###

N, M = map(int, input().split())  # 品物の数、割引券の枚数
A = list(map(int, input().split()))  # 品物の値段
A.sort(reverse=True)
i = 0
for _ in range(M):
    A[i] = A[i] // 2
    if i <= N - 2 and A[i] < A[i + 1] and A[0] < A[i+1]:
        i += 1
    else:
        A.sort(reverse=True)
        i = 0
print(str(sum(A)))