Harryxun/stf_run huggingface dataset:
def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    

N,Q = map(int,input().split())
sys.setrecursionlimit(N**2)

a=[]
b=[]

p=[]
x=[]

#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())
    a.append(a0)
    b.append(b0)
    
    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())
    p.append(p0)
    x.append(x0)
    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    
def input():
    return sys.stdin.readline()[:-1]

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


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")
import math

a, b= map(int, input().split())
def lcm(x, y):
    return (x * y)//math.gcd(x, y)

print(lcm(a, b))


### FIXED CODE ###

import fractions as fr

a, b= map(int, input().split())
def lcm(x,y):
    return (x*y/fr.gcd(x,y))

print(int(lcm(a,b)))
s = list(input())

k = int(input())

cnt = 0

if len(s) == 1:
    print(s[0])
else:
    if s[0] == "1":
        while s[0] == "1":
            cnt += 1
            del s[0]
        if cnt>=k:
            print(1)
        else:
            print(s[0])
            
    else:
        print(s[0])

### FIXED CODE ###


s = list(input())

k = int(input())

cnt = 0

if len(s) == 1:
    print(s[0])
else:
    if s[0] == "1":
        
        while s[0] == "1":
            cnt += 1
            del s[0]
            if cnt>=k:
                print(1)
                break
            
        if cnt<k:
            print(s[0])
            
    else:
        print(s[0])
a, b = map(int, input().split())

if (a*b) % == 0:
  print("Even")
  
else:
  print("Odd")

### FIXED CODE ###

a,b=(int(x) for x in input().split())

if (a*b) % 2 == 0:
  print("Even")
  
else:
  print("Odd")
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n)]
group = [-1]*n
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x-1].append(y)
    graph[y-1].append(x)
for i, num in enumerate(p):
    space = [i]
    for point in space:
        if group[point]+1:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
# p = [int(i) for i in input().split()]
p = map(int,input().split())
# graph = [[]]*(N+1)
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)
w,h,x,y=map(int,input().split())
if x=w/2 and y=h/2:
    print(w*h/2,1,sep=' ')
else:
    print(w*h/2,0,sep=' ')

### FIXED CODE ###

w,h,x,y=map(int,input().split())
if x==w/2 and y==h/2:
    print(w*h/2,1,sep=' ')
else:
    print(w*h/2,0,sep=' ')
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

N,X,Y=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

memo={}
def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if (n,turn) in memo:    #カードの残り枚数と、どちらの手番かで最終スコアはいつも同じ
        return memo[(n,turn)]
    if n==1:
        ret=abs(last-A[N-n])
    elif turn==0:
        ret=max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        ret=min( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動
    memo[(n,turn)]=ret
    return ret


print func(N,Y,0)

### FIXED CODE ###

X,Y=raw_input().split()
if X<Y:
	print "<"
elif X>Y:
	print ">"
elif X==Y:
	print "="
r,g,b=map(int,input().split())
print('YES' if (10*g+b)%4=0 else 'NO'

### FIXED CODE ###

r, g, b = map(int, input().split())
if (g * 10 + b) % 4 == 0:
  print("YES")
else:
  print("NO")
flg = len(set(input())) == 1:
print('Yes' if flg else 'No')

### FIXED CODE ###

flg = len(set(input())) == 2
print('Yes' if flg else 'No')
import sys
sys.setrecursionlimit(200000)
 
n, k = map(int, input().split())
 
h = [int(i) for i in input().split()]
 
d = {}
 
def dp(p):
  if p in d:
    return d[p]
  if p == n-1:
    return 0
  m = min([dp(p+i)+abs(h[p]-h[p+i]) for i in range(1, min(n-p, k+1))])
  d[p] = m
  return m

print(dp(0))


### FIXED CODE ###

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

dp = [0] * n
dp[1] = abs(h[1]-h[0])
for i in range(2, n):
  a = [0] * min(i,k)
  for j in range(1, min(i,k)+1): 
    a[j-1] = dp[i-j]+abs(h[i]-h[i-j])
  dp[i] = min(a)

print(dp[-1])
#!/usr/bin
# -*- coding="utf-8" -*-

c1 = []
c2 = []
q = input().split()
n = [input() for i in range(int(q[1]))]
for j in range(n):
  m = j.split()
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1).intersection(c2):
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

### FIXED CODE ###

#!/usr/bin
# -*- coding="utf-8" -*-
c1 = []
c2 = []
q = input().split()
n = [input().split() for i in range(int(q[1]))]
 
for m in n:
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
P = [int(input()) for _ in range(N)]

cnt = 0
if P[0] == 1:
    isFirstNum = 1
else:
    isFirstNum = 0
    cnt +=1

if P[-1] == N:
    isLastNum = 1
else:
    isLastNum = 0
    cnt +=1
    
isBefore = 0
isAfter = 0

P.remove(1)
P.remove(N)


for i in range(len(P)-1):
    if P[i]>P[i+1]:
        cnt += 1
        if P[i]>N//2:
            isAfter = 1
        else:
            isBefore = 1

ope = cnt+isBefore*isFirstNum+isAfter*isLastNum

print(ope)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
P = [int(input()) for _ in range(N)]

Q = [0]*(N)
for i in range(N):
    Q[P[i]-1]=i

cnt = 1
ans = 1
for i in range(N-1):
    if Q[i+1]>Q[i]:
        cnt += 1
    else:
        ans = max(ans,cnt)
        cnt = 1
ans = max(ans,cnt)
print(N-ans)
A,B = max(int,input().split())
print(max(A+B,A-B,A*B))

### FIXED CODE ###

A,B = map(int,input().split())
print(max(A+B,A-B,A*B))
n = int(input())
alist  = list(map(int,input().split()))
list1 = alist[1::2]
list2 = alist[0::2]
from collections import Counter
dic1 = Counter(list1)
dic2 = Counter(list2)
sortdic1 = sorted(dic1.items(),key=lambda x:x[1], reverse=True)
sortdic2 = sorted(dic2.items(),key=lambda x:x[1], reverse=True)
vlist1 = list(sortdic1.items())
vlist2 = list(sortdic2.items())
if vlist1[0][0]!=vlist2[0][0]:
  print(n - vlist1[0][1] - vlist2[0][1])
else:
  if (vlist1[0][1] + vlist2[1][1])>(vlist1[1][1] + vlist2[0][1]):
    print(n - vlist1[0][1] - vlist2[1][1])
  else:
    print(n -vlist1[1][1] - vlist2[0][1])

### FIXED CODE ###

n = int(input())
alist  = list(map(int,input().split()))
list1 = alist[1::2]
list2 = alist[0::2]
from collections import Counter
dic1 = Counter(list1).most_common()
dic2 = Counter(list2).most_common()
dic1.append([0,0])
dic2.append([0,0])
if dic1[0][0]!=dic2[0][0]:
  print(n - dic1[0][1] - dic2[0][1])
else:
  print(min(n - dic1[0][1] - dic2[1][1], n -dic1[1][1] - dic2[0][1]))
def common():
   X = raw_input()
   Y = raw_input()
             
   for i in range(0, len(Y)+1):
      s[i] = 0
             
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if s[j] == j[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
          
   return s[-1]
    
q = input()     
for l in range(0, q):
   common()

### FIXED CODE ###

def common():
   X = raw_input()
   Y = raw_input()
  
   s = [0 for i in range(len(Y)+1)]
 
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if X[j] == Y[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
  
   print s[-1]
 
q = input()
for l in range(0, q):
   common()
a,b,c,d=map(int,input().split())
flag="F"
while flag="F":
  c=c-b
  if c<=0:
    print("Yes")
    break
  a=a-d
  if a<=0:
    print("No")
    break

### FIXED CODE ###

a,b,c,d=map(int,input().split())
flag="F"
while flag=="F":
  c=c-b
  if c<=0:
    flag="Y"
  else:
    a=a-d
    if a<=0:
      flag="N"
if flag=="Y":
  print("Yes")
else:
  print("No")
a = int(input())
b = int(input())
c = int(input())
d = int(input())

x = abs(a - b)
y = abs(b - c)
z = abs(a - c)

if x <= d and y <= d:
    print("Yes")
elif x > d and z <= d:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c, d = map(int, input().split())

x = abs(a - b)
y = abs(b - c)
z = abs(a - c)

if x <= d and y <= d:
    print("Yes")
elif z <= d:
    print("Yes")
else:
    print("No")
n = int(input())
for i in range(n):
    w = input()
    if i > 0:
        if  w[i-1][-1] == w[i][0]:
            for j in range(i):
                if w[i] == w[j]:
                    print('No')
                else:
                    print('Yes')
        else:
            print('No')

### FIXED CODE ###

n = int(input())
l = []
flag = 0
for i in range(n):
    w = input()
    l.append(w)
for k in range(1,n):
    if  l[k-1][-1] != l[k][0]:
        flag =1
        break

    for j in range(k):
        if l[k] == l[j]:
            flag = 1
            break
        
if(flag == 1):
    print('No')
else:
    print('Yes')
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        modmod = mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, mod) % mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % mod
        return tmp * self.fac[n] % mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % mod

def make_divisors(n):
    divisors = {}
    tmp = n
    div = 2
    while n > 1 and div <= tmp**0.5:
        if n % div == 0:
            divisors[div] = 0
        while n % div == 0:
            n //= div
            divisors[div] += 1
        div += 1
    if n > 1:
        divisors[n] = 1
    return divisors

n,m = map(int, input().split())
mod = 10**9 + 7
divisors = make_divisors(m)
fact = Factorial(n + max(divisors.values()) + 1)

ans = 1
for value in divisors.values():
    ans = ans * fact.comb(value+n-1,value) % mod
print(ans)


### FIXED CODE ###

class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        modmod = mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, mod) % mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % mod
        return tmp * self.fac[n] % mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % mod

def make_divisors(n):
    divisors = {}
    tmp = n
    for div in range(2, int(n**0.5)+1):
        if n % div == 0:
            divisors[div] = 0
        while n % div == 0:
            n //= div
            divisors[div] += 1
        div += 1
    if n > 1:
        divisors[n] = 1
    return divisors

n,m = map(int, input().split())
mod = 10**9 + 7
divisors = make_divisors(m)
fact = Factorial(n + sum(divisors.values()) + 1)

ans = 1
for value in divisors.values():
    ans = ans * fact.comb(value+n-1,value) % mod
print(ans)
A, B = map(int, input().split())
if A > B:
    print("GREATER")
elif A==B:
    print("EQUAL")
else:
    print("LESS")

### FIXED CODE ###

A = int(input())
B = int(input())
if A > B:
    print("GREATER")
elif A==B:
    print("EQUAL")
else:
    print("LESS")
n = int(input())
s = str(input())
c = len(s)
for i in range(c):
  if (ord(s[i])+n)>90:
    s[i] = chr(ord(s[i])+n-26)
  else:
    s[i] = chr(ord(s[i])+n)
print(s)

### FIXED CODE ###

n = int(input())
s = str(input())
c = len(s)
t = ''
for i in range(0,c):
  if (ord(s[i])+n)>90:
    a = ord(s[i])+n-26
  else:
    a = ord(s[i])+n
  t += chr(a)
print(t)
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  if k>N:
    continue
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      s = str(dp[i-k])
      m = int(s+str(dic[k]))
      dp[i] = max(dp[i], m)
print(dp[N])

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def Gcd(*numbers):
  return reduce(gcd, numbers)
N = int(input())
ls = [int(i) for i in input().split()]

print(Gcd(*ls))
def abis(l, key):
    le = 0
    ri = n
    while le < ri:
        mid = (le + ri) // 2
        if mid == n:
            return mid
        elif l[mid] == key:
            while mid<n and l[mid-1]==l[mid]:
                mid-=1
            return mid
        elif l[mid] > key:
            if mid != 0 and l[mid - 1] < key:
                return mid
            ri = mid
        else:
            le = mid + 1
    return mid + 1

def cbis(l, key):
    le = 0
    ri = n
    while le < ri:
        mid = (le + ri) // 2
        if mid == n:
            return 0
        elif l[mid] == key:
            while mid<n and l[mid+1]==l[mid]:
                mid+=1
            return n-mid-1
        elif l[mid] > key:
            if mid != 0 and l[mid - 1] < key:
                return n-mid
            ri = mid
        else:
            le = mid + 1
    return n-mid



n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    aa = abis(a, b[i])
    ca = cbis(c, b[i])
    ans += aa * ca
print(ans)


### FIXED CODE ###

import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    aa = bisect.bisect_left(a,b[i])
    ca = n-bisect.bisect_right(c,b[i])
    ans += aa * ca
print(ans)
n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [-1 for i in range(n+1)]
takahashi = [-1 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)

def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)
finished = set()
dfs(v,0,aoki)
finished = set()
path = []
node = v
pre_node = [0 for i in range(n+1)]
search_path(u,v)
while node != u:
    path = [node] + path
    node = pre_node[node]
start = 0
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set(path)
ans = [0 for i in range(n+1)]
dfs(start,0,ans)
print(ans)
print(min(0, max(ans) + aoki[start] - 1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,u,v = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

#辿って親保存しとく
finished = set()
dfs(v,0,aoki)

#さかのぼれるとこまで行く,startがさかのぼれる最大のノーど
par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)
from collections import deque

N, M = map(int, input().split())
path = [list(map(int, input().split())) for i in range(M)]

edges = [[] for j in range(N+1)]
for p in path:
    x, y = p
    edges[x].append(y)
    edges[y].append(x)

que = deque([])
dic = {1: 0}
def bfs(now):
    e = edges[now]
    for q in e:
        if not q in dic:
            dic[q] = now
            que.append(q)
    try:
        n = que.popleft()
        bfs(n)
    except IndexError:
        pass

bfs(1)

if len(dic) != N:
    print("No")
else:
    print('Yes')
    dic_sort = sorted(dic.items())
    for elem in dic_sort:
        if elem[0] != 1:
            print(elem[1])



### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
path = [list(map(int, input().split())) for i in range(M)]

edges = [[] for j in range(N+1)]
for p in path:
    x, y = p
    edges[x].append(y)
    edges[y].append(x)

que = deque([])
dic = {1: 0}
def bfs(now):
    e = edges[now]
    for q in e:
        if not q in dic:
            dic[q] = now
            que.append(q)
    try:
        n = que.popleft()
        bfs(n)
    except IndexError:
        pass

bfs(1)

if len(dic) != N:
    print("No")
else:
    print('Yes')
    dic_sort = sorted(dic.items())
    for elem in dic_sort:
        if elem[0] != 1:
            print(elem[1])
import collections
N=int(input())
a=0
list1 = list(map(int, input().split()))
c = collections.Counter(list1)
for i in range(N):
    a+=int(c[i+1]*(c[i+1]-1)/2)
for i in range(N):
    if c[list1[i]]!=0:
        print(a-c[list1[i]]+1)
    else:
        print(a)

### FIXED CODE ###

i = list(map(int, input().split()))
a=i[0]*(i[0]-1)/2+i[1]*(i[1]-1)/2
print(int(a))
A,P=map(int,input().split())

print((3A+P)//2)

### FIXED CODE ###

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

print((3*A+P)//2)
n = int(input())
P = list(map(str, input().split()))
Q = list(map(str, input().split()))
p, q = '' , ''
for i in range(n):
    p += P[i]
    q += Q[i]

a, b = 0, 0
num = 10 ** (n - 1)
count = 0
found = False
while found == False:
    num += 1
    waru = num
    conv_num = ''
    while waru != 0:
        conv_num = str(waru % (n + 1)) + conv_num
        waru = waru // (n + 1)
    if 0 in conv_num:
        pass
    else:
        count += 1
        if conv_num == p:
            a = count
        if conv_num == q:
            b = count
    if p != 0 and q != 0:
        found = True
ans = a - b
if ans < 0:
    ans *= -1
print(ans)

### FIXED CODE ###

import itertools
n = int(input())
P = int(input().replace(' ', ''))
Q = int(input().replace(' ', ''))
N = [i + 1 for i in range(n)]
per = list(itertools.permutations(N))
lis = []
for oc in per:
    lis.append(int(''.join(map(str, list(oc)))))
a = lis.index(P)
b = lis.index(Q)
print(abs(a - b))
# -*- coding:utf8 -*-

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

ans = 0
for i in range(n):
        ans += b[a[i]]
        if i != 0 and a[i] == a[i - 1] + 1:
                ans += c[a[i - 1]]
print(ans)

### FIXED CODE ###

# -*- coding:utf8 -*-

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

ans = 0
for i in range(n):
    ans += b[a[i] - 1]
    if i != 0 and a[i] == a[i - 1] + 1:
        ans += c[a[i - 1] - 1]
print(ans)
i = list(map(int,input().split()))
A_list[1,3,5,7,8,10,12]
B_list[4,6,9,11]
C_list[2]
if i[0] in A_list and i[1] in A_list:
  print("Yes")
if i[0] in B_list and i[1] in B_list:
  print("Yes")
if i[0] in C_list and i[1] in C_list:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

i = list(map(int, input().split()))
 
A_list = [1, 3, 5, 7, 8, 10, 12]
B_list = [4, 6, 9, 11]
C_list = [2]
 
if i[0] in A_list and i[1] in A_list:
    print("Yes")
elif i[0] in B_list and i[1] in B_list:
    print("Yes")
elif i[0] in C_list and i[1] in C_list:
    print("Yes")
else:
    print("No")
from scipy.special import comb


### FIXED CODE ###

from scipy.misc import comb

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

mod = 10 ** 9 + 7

for i in range(1, K + 1):
    a = comb(N - K + 1, i, exact=True)
    b = comb(K - 1, i - 1, exact=True)
    ret = a % mod * b % mod
    print(ret)
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

        a = int(sys.stdin.readline().strip())
        n, mod = divmod(a, 2)
    print(n if mod == 0 else n + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

a = input()
n, mod = divmod(int(a), 2)
print(n if mod == 0 else n + 1)
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



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

ans = 0
for i in range(1,N+1):
  if i < K:
    cnt = math.ceil(math.log2(K/i))
  else:
    cnt = 0
  ans += (1/2)**cnt

print(ans/N)

### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import math



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

ans = 0
for i in range(1,N+1):
  if i < K:
    cnt = math.ceil(math.log2(K/i))
  else:
    cnt = 0
  ans += (1/2)**cnt

print(ans/N)
a,b = map(int,ibput().split())
if a >= b:
  print(b)
else:
  print(a)

### FIXED CODE ###

a,b = map(int,input().split())
if a <= b:
  print(a)
else:
  print(a-1)
print(x * len(input()))

### FIXED CODE ###

s = input()
print('x'*len(s))
def comb(n,k):
  if n<k:
    return 0
  if n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

n,m,k=map(int,input().split())
mod=998244353
fac=[1]*n
finv=[1]*n
inv=[0]*n
inv[1]=1
for i in range(2,n):
  fac[i]=fac[i-1]*i%mod
  inv[i]=mod-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

ans=0
for i in range(k+1):
  ans+=m*comb(n-1,i)*pow(m-1,n-1-i,mod)
  ans%=mod
print(ans)


### FIXED CODE ###

class Combination:
    def __init__(self, n, mod):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % mod)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
        self.mod = mod

    def factorial(self, k):

        return self.fact[k]

    def inverse_factorial(self, k):
        return self.inv_fact[k]

    def permutation(self, k, r):
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.mod

    def combination(self, k, r):
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.mod

    def combination_large(self, k, r):
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.mod
        return (res * self.inv_fact[r]) % self.mod

n, m, k = map(int, input().split())
mod = 998244353
cmb = Combination(10**6, mod)

ans = 0
for i in range(k+1):
    ans += m*cmb.combination(n-1, i)*pow(m-1, n-1-i, mod)
    ans %= mod
print(ans)