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

#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    day = -1

    while True:
        day += 1
        g = Graph(N)
        flag = False

        for i, h in enumerate(a_head):
            if h == N-1:
                continue
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


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

# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ll.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if ll[k] < ll[i] + ll[j]:
                ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

n = int(input())
ll = list(map(int,input().split()))

ll.sort()
ans = 0
for i in range(n - 2):
    for j in range(i+1, n - 1):
        lb = j + 1
        ub = n - 1
        b = ll[i] + ll[j]
        if ll[lb] >= b:
            continue
        if ll[ub] < b:
            ans += ub - lb + 1
            continue
        while True:
            if ub == lb:
                ans += ub - j
                break
            t = (lb + ub) // 2 + 1
            if ll[t] < b:
                lb = t
            else:
                ub = t - 1
print(ans)
### BUGGY CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3): 
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()


### FIXED CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
result=[1]
temp=1
i=0
while i<k:
  temp=a[temp-1]
  if temp in result:
    break
  result.append(temp)
  i=i+1
result.append(temp)
l=len(result)
temp=result.index(result[l-1])
if k<l:
  print(result[k+1])
else:
  l2=l-1-temp
  print(result[temp+(k-temp)%l2])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
result=[1]
temp=1
for i in range(n):
  temp=a[temp-1]
  result.append(temp)
temp=result.index(result[len(result)-1])
c=len(result)-temp-1
if k<n:
  print(result[k])
else:
  print(result[temp+(k-temp)%c])
### BUGGY CODE ###

import heapq

from operator import itemgetter

n,m = map(int,input().split())

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

info = [0] * m
for i in range(m):
    info[i] = list(map(int,input().split()))

info = sorted(info,key = itemgetter(1),reverse = True)
#print(a)

heapq.heapify(a)
#print(a)

d = 0

for j in range(m):
    for k in range(info[j][0]):
        if a[0] > info[j][1]:
            d = 1
            break
        else:
            heapq.heappushpop(a,info[j][1])
    if d == 1:
        break

print(sum(a))

### FIXED CODE ###

import heapq

from operator import itemgetter

n,m = map(int,input().split())

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

info = [0] * m
for i in range(m):
    info[i] = list(map(int,input().split()))

info = sorted(info,key = itemgetter(1),reverse = True)
#print(a)

heapq.heapify(a)
#print(a)

d = 0
count = 0

for j in range(len(info)):
    for k in range(info[j][0]):
        if a[0] > info[j][1]:
            d = 1
            break
        else:
            heapq.heappushpop(a,info[j][1])
            count += 1
        if count >= n:
            d = 1
            break
    if d == 1:
        break

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

n, k = map(int, input().split())
p = list(map(int, input().split()))

#連続するK個の要素の和で一番大きいもの
start = -1
maximum = -1
for i in range(len(p) - k + 1):
  temp = sum(p[i:i + k])
  if temp > maximum:
    maximum = temp
    start = i

#期待値の算出
exp = 0
for i in range(start, start + k):
  temp = 1 / 2 * p[i] * (p[i] + 1)
  exp += temp / p[i]

print(exp)




### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

#累積和を出す
t = [0] * (len(p) + 1)
for i in range(len(p)):
  t[i + 1] = t[i] + p[i]

#連続するK個の和で、最大の値を取得する。
maximum = -1
start = -1

for i in range(len(p) - k + 1):
  temp = t[i + k] - t[i]
  if temp > maximum:
    maximum = temp
    start = i

#期待値
exp = 0
for i in range(start, start + k):
  temp = 1 / 2 * p[i] * (p[i] + 1)
  exp += temp / p[i]

print(exp)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
ans_lis = np.ones(len(a))
ans_lis = np.array(ans_lis, dtype=int)
for i in range(len(a)):
    ans_lis[i] += int(a.index(i + 1))
print(*ans_lis)


### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
ans = [0] * n
for a, i in zip(As, range(1, n+1)):
  ans[a - 1] = i
print(*ans)
### BUGGY CODE ###

def main():
    import heapq
    inf = 10**20
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*5001 for _ in [0]*n]
    h = [(0, 0, min(s, 5000))]  # 時刻、位置、所持金
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 5000)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  # 行き先、運賃、時間
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()


### FIXED CODE ###

def main():
    import heapq
    inf = 10**16
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*2501 for _ in [0]*n]
    h = [(0, 0, min(s, 2500))]  # 時刻、位置、所持金
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 2500)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  # 行き先、運賃、時間
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()
### BUGGY CODE ###

maps = [s for s in str(input())]
people = [1] * len(maps)
store = {}
max_count = 10**100


def update(people):
    n_people = [0] * len(maps)
    for i in range(len(people)):
        for n in range(people[i]):
            if maps[i] == 'R':
                n_people[i] -= 1
                n_people[i+1] += 1
            else:
                n_people[i] -= 1
                n_people[i-1] += 1
    return [people[i] + n_people[i] for i in range(len(people))]


for c in range(max_count):
    people = update(people)
    map_key = ''.join(str(i) for i in people)
    if map_key in store:
        mod = round((max_count - c + 1) % (c - store[map_key]))
        for i in range(mod):
            people = update(people)
        break
    store[map_key] = c

print(' '.join(str(i) for i in people))


### FIXED CODE ###

maps = input()
people = [0] * len(maps)

counter = 0
for i in range(len(maps)):
    if maps[i] == 'R':
        counter += 1
        if maps[i+1] == 'L':
            people[i] += (counter+1) // 2
            people[i+1] += counter // 2
    else:
        counter = 0

counter = 0
for i in range(len(maps) - 1, 0, -1):
    if maps[i] == 'L':
        counter += 1
        if maps[i-1] == 'R':
            people[i] += (counter+1) // 2
            people[i-1] += counter // 2
    else:
        counter = 0

print(*people)
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = list(input())
c = Counter(s)
ans = c["R"]*c["G"]*c["B"]
for i in range(n-2):
  for j in range(1,n):
    if i+2*j >= n:
      break
    if sorted([s[i],s[i+j],s[i+2*j]]) == ["B","G","R"]:
      ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
if n <= 2:
  print(0)
  quit()
r,g,b = 0,0,0
for i in range(n):
  r += 1*(s[i]=="R")
  g += 1*(s[i]=="G")
  b += 1*(s[i]=="B")
ans = r*g*b

for i in range(n-2):
  for j in range(i+1,n):
    l = [i,j,2*j-i]
    if l[2] >= n:
      break
    r,g,b = 0,0,0
    for k in l:
      r += 1*(s[k]=="R")
      g += 1*(s[k]=="G")
      b += 1*(s[k]=="B")
    if r*g*b == 1:
      ans -= 1
print(ans)
### BUGGY CODE ###

'''
Sを連続する値の数のリストに変換
(ただし、左右端は必ず1が0個以上存在するとする)
S='0111010011' -> A=[0,1,3,1,1,2,2]

K=1なら、
sum(A[0:3]), sum(A[2:5]), sum(A[4:7])のmaxが答え
'''

N, K = map(int, input().split())
S = input()

# Sを0,1の区切りで分解したときのそれぞれの長さ
A = []
cur = S[0]
c = 0
for s in S[1:] + '*':
    c += 1
    if cur != s:
        cur = s
        A.append(c)
        c = 0

# 先頭、末尾が"0"のときは0を追加
if S[0] == '0':
    A = [0] + A
if S[-1] == '0':
    A = A + [0]

# Aの偶数番号インデックス(0始まり)から計算される
# 2K+1個の連続する要素の和の最大値が求める値
if len(A) <= 2 * K + 1:
    print(sum(A))
else:
    m = 0
    i = 0
    while i + 2*K+1 <= len(A):
        m = max(m, sum(A[i: i+2*K+1]))
        i += 2
    print(m)


### FIXED CODE ###

'''
Sを連続する値の数のリストに変換
(ただし、左右端は必ず1が0個以上存在するとする)
S='0111010011' -> A=[0,1,3,1,1,2,2]

K=1なら、
sum(A[0:3]), sum(A[2:5]), sum(A[4:7])のmaxが答え
'''

N, K = map(int, input().split())
S = input()

# Sを0,1の区切りで分解したときのそれぞれの長さ
A = []
cur = S[0]
c = 0
for s in S[1:] + '*':
    c += 1
    if cur != s:
        cur = s
        A.append(c)
        c = 0

# 先頭、末尾が"0"のときは0を追加
if S[0] == '0':
    A = [0] + A
if S[-1] == '0':
    A = A + [0]

# Aの累積値を計算
AA = [None] * len(A)
AA[0] = A[0]
for i in range(1, len(A)):
    AA[i] = AA[i-1] + A[i]

# Aの偶数番号インデックス(0始まり)から計算される
# 2K+1個の連続する要素の和の最大値が求める値
if len(A) <= 2 * K + 1:
    print(sum(A))
else:
    m = 0
    i = 0
    while i + 2*K <= len(A):
        # p: sum(A[i: i+2*K+1])
        p = AA[i+2*K] - (AA[i-1] if i > 0 else 0)
        m = max(m, p)
        i += 2
    print(m)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = list(int(input()) for i in range(Q))

for i in range(N):
    cnt = A.count(i + 1)
    if K - (Q - cnt) > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = list(int(input()) for i in range(Q))

P = [-(Q - K)] * N

for a in A:
    P[a - 1] += 1

for p in P:
    if p > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

S = list(input())
s = [int(s) for s in S]
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += s.pop()*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*N 
for i in range(N):
  if i==0:continue;
  dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(i-K,0),i)) 
print(dp[N-1])


### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]+[None]*(N-1) 
def func(N,K,h,dp):
  for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(i-K,0),i)) 

func(N,K,h,dp)
print(dp[-1])
### BUGGY CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
a=set(range(l,r+1))
for i in range(1,m):
  l,r=map(int,input().split())
  b=set(range(l,r+1))
  a=a.intersection(b)
print(len(a))

### FIXED CODE ###

n,m=map(int,input().split())
lll=[]
rrr=[]
for i in range(m):
  l,r=map(int,input().split())
  lll.append(l)
  rrr.append(r)
print(max(0,min(rrr)-max(lll)+1))
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(2,n+1):
    ans*=i
ans = ans % (pow(10,9)+7)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 1
p = pow(10,9)+7
for i in range(2,n+1):
    ans = (i * ans)%p
print(ans)
### BUGGY CODE ###

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

a = list(a)
for i in range(n):
    count = 0
    for j in range(i, n - 1):
        if a[j] == i + 1:
            count += 1
    print(count)


### FIXED CODE ###

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

a = list(a)
result = [0] * n
for i in range(n - 1):
    result[a[i] - 1] += 1

print(*result, sep='\n')
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for i in range(x):
    for j in range(y):
        an.append(lisa[i]+lisb[j])
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for i in range(z):
    for nu in an:
        ans.append(lisc[i]+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

S = input()
Q = int(input())
reverse = False
for _ in range(Q):
    cmd = input().split()
    op = cmd[0]
    if op == "1":
        reverse = not reverse
    else:
        top = (cmd[1] == "1") ^ reverse
        if top:
            S = cmd[2] + S
        else:
            S = S + cmd[2]
print(S[::-1]) if reverse else print(S)

### FIXED CODE ###

S = input()
Q = int(input())
head, tail = "", ""
reverse = False
for _ in range(Q):
    cmd = input().split()
    if cmd[0] == "1":
        reverse = not reverse
    else:
        top = (cmd[1] == "1") ^ reverse
        if top:
            head += cmd[2]
        else:
            tail += cmd[2]
print(tail[::-1] + S[::-1] + head) if reverse else print(head[::-1] + S + tail)
### BUGGY CODE ###

import numpy as np

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = np.zeros(62, dtype=np.int64)
one = np.ones(62, dtype=np.int64)
pow2 = (2 ** np.arange(62, dtype=np.int64)) % M


def bitcnt(a):
    j = 0
    bits = np.zeros(62, dtype=np.int64)
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = one - a1
for i in range(1, N):
    bits1 = bitcnt(A[i])
    bits0 = one - bits1
    ans += np.sum(pow2 * (a0 * bits1 % M) % M) % M
    ans %= M
    ans += np.sum(pow2 * (a1 * bits0 % M) % M) % M
    ans %= M
    a1 += bits1
    a0 += bits0

print(ans)


### FIXED CODE ###

M = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

zero = [0] * 60
one = [1] * 60
pow2 = [2 ** i % M for i in range(60)]


def bitcnt(a):
    j = 0
    bits = [0] * 60
    while a:
        bits[j] = a & 1
        a >>= 1
        j += 1
    return bits


ans = 0
a1 = bitcnt(A[0])
a0 = [(x + 1) % 2 for x in a1]
for i in range(1, N):
    a = A[i]
    for j in range(60):
        b1 = a & 1
        a >>= 1
        if b1:
            ans += pow2[j] * a0[j] % M
            a1[j] += 1
        else:
            ans += pow2[j] * a1[j] % M
            a0[j] += 1
        ans %= M

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

import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            dp[ss] = (dp[ss]*2 + dp[ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[ss] = dp[ss]*2 % MOD

print(int(dp[s]))

### FIXED CODE ###

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

MOD = 998244353

dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])
### BUGGY CODE ###

n,a,b = map(int,input().split())
su = 0
blue = 0
nn = 5**100

for i in range(nn):
    for x in range(0,a):
        if su < n:
            su += 1
            blue += 1
    for y in range(0,b):
        if su >= n:
            break
        su += 1
    else:
        continue
    break

print(str(blue))

### FIXED CODE ###

n,a,b = map(int,input().split())
su = 0
blue = 0

mo = n%(a+b)
mu = int(n/(a+b))

if mo > a:
    ma = mo-a
    blue = n-ma-b*mu
elif mo <= a:
    blue = n- b*mu

print(str(blue))
### BUGGY CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lf = [1]  # k!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]


lc = []  # n - 1 C i
for i in range(n):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    lc.append(c)


def n_pattern(n_pair):
    return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


answer = 0
for i in range(k + 1):
    answer += n_pattern(i)


print(answer % MOD)






### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)
### BUGGY CODE ###

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst=lst+[[int(s) for s in input().split()]]
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)

### FIXED CODE ###

N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)