Harryxun/stf_run huggingface dataset:
import math
def comb(n,r):
  return int(math.factorial(n)/(math.factorial(r)*math.factorial(n-r)))

N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=0
even=0
total=0
for i in range(N):
  total+=A[i]
  if A[i]%2==0:
    even+=1
  else: 
    odd+=1
total=total%2
evens=2**even

ans=0
if total==even%2:
  for i in range(int((odd)/2+1)): 
    ans+=comb(odd,2*i)
else:
  for i in range(int((odd-1)/2)+1):
    ans+=comb(odd,2*i+1)
print(ans*evens)

### FIXED CODE ###

N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=0
for i in range(N):
  if A[i]%2==1: odd+=1
if odd==0:
  if P==1: print(0)
  else: print(2**N)
else:
  print(2**(N-1))
a = map(int.input())
print(3*a**2)

### FIXED CODE ###

a = int(input())

b = 3*a**2

print(b)
n, m = map(int, input().split())
a_list = list(map(lambda x: int(x), input().split()))
for _ in range(m):
  b, c = map(int, input().split())
  ll = [c for _ in range(b)]
  a_list.extend(ll)
a_list.sort(reverse=True)
print(sum(a_list[::-n]))


### FIXED CODE ###

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

if a >=13:
  print(b)
elif a>=6:
  print(int(b/2))
else:
  print(0)
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力

import copy

n, m = map(int, input().split())
ary = [int(s) for s in input().split()]

if len(ary) > 1 :
    ary.sort()
    sa = []
    for i in range(0, m - 1):
        sa.append(ary[i + 1] - ary[i])
        
    for i in range(0, n -1):
        sa.remove(max(sa))
        
    print(sum(sa))
else :
    print(0)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力

import copy

n, m = map(int, input().split())
ary = [int(s) for s in input().split()]

if n < m :
    ary.sort()
    sa = []
    
    for i in range(0, m - 1):
        sa.append(ary[i + 1] - ary[i])
    
    #print(sa)
    
    sa.sort()
    
    for i in range(0, n - 1):
        sa.pop(-1)
    
    print(sum(sa))
else :
    print(0)
S = input()
K = int(input())

l = len(S)
pair = []
current = S[0]
seq = 1
for i in range(1, l):
    if(i == l-1):
        if(S[i]==current):
            seq += 1
        if(seq != 1):
            pair.append(seq)
    elif(S[i] == current):
        seq += 1
    else:
        if(seq != 1):
            pair.append(seq)
        seq = 1
        current = S[i]

ans = 0
#print(pair)
if(S[0] != S[l-1]):
    for i in range(len(pair)):
        ans += K * (pair[i]//2)
else:
    if(len(pair) == 1):
        ans += ((pair[0]+1)//2)*(K-1) + (pair[0]//2)
    else:
        for i in range(len(pair)-1):
            ans += K * i
        ans += ((pair[i+1]+1)//2)*(K-1) + (pair[i+1]//2)

print(ans)

### FIXED CODE ###

S = input()
K = int(input())

S += "1"
l = len(S)
pair = []
current = S[0]
seq = 1
for i in range(1, l):
    if(i == l):
        pair.append(seq)
    elif(S[i] == current):
        seq += 1
    else:
        pair.append(seq)
        seq = 1
        current = S[i]

ans = 0
#print(pair)
if(len(pair) == 1):
    ans += (K * pair[0])//2
elif(S[0] != S[l-2]):
    for i in range(len(pair)):
        ans += K * (pair[i]//2)
else:
    for i in range(1, len(pair)-1):
        ans += K * (pair[i]//2)
    ans += (pair[0]//2) + (pair[i+1]//2) + ((pair[0]+pair[i+1])//2)*(K-1)

print(ans)
a=input()
b=0
for i in range(len(a)):
  if a[i]!=a[len(a)-i]:
    b=b+1
print(int(b/2))

### FIXED CODE ###

a=input()
b=0
for i in range(len(a)):
  if a[i]!=a[len(a)-i-1]:
    b=b+1
print(int(b/2))
A, B = list(map(int, input().split()))

if A<2 or A>20 or B<1 or B>20:
	sys.exit()

if B == 1:
	print(0)
	sys.exit()

a = 1
while A < B:
	B = B - A
	a += 1
print(a)

### FIXED CODE ###

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

if A<2 or A>20 or B<1 or B>20:
	exit()

if B == 1:
	print(0)
	exit()

a = 1
while A < B:
	B = B - A + 1 
	a += 1
print(a)
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

a,b=getNM()

print(int(a*b))

### FIXED CODE ###

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

i=input()

a,b=i.split(' ')
from decimal import Decimal
print(int(Decimal(a) * Decimal(b)))
n = int(input())
a = list(map(int, input().split()))
print("APPROVED" if all(i % 5 == 0 or i % 3 == 0 for i in a if i % 2 == 0 else "DENIED")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
print("APPROVED" if all(i % 5 == 0 or i % 3 == 0 for i in a if i % 2 == 0) else "DENIED")
import math
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

P = [A, B, C, D, E]
p = min(P)
if p>=N:
    print(5)
else:
    ans = 4+ceil(N/p)
    print(ans)

### FIXED CODE ###

import math
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

P = [A, B, C, D, E]
p = min(P)
if p>=N:
    print(5)
else:
    ans = 4+math.ceil(N/p)
    print(ans)
import math

n = int(input())

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

ans = a[0]
for i in range(1,len(a)):
    ans = math.gcd(ans,a[i])


print(ans)




### FIXED CODE ###

import fractions

n = int(input())

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

ans = a[0]
for i in range(1,len(a)):
    ans = fractions.gcd(ans,a[i])


print(ans)
n, x = map(int, input().split())
a = list(map(int, input().split()))

c = 0

if x == 0:
	print(sum(a))
if a[0] > x:
	c += a[i] - (x-1)
	a[i] = x - 1
	
else:
	for i in range(n-1):
		if a[i] + a[i+1] > x:
			if a[i+1] >= a[i]:
				c += (a[i+1] - (x - a[i]))
				a[i+1] -= (a[i+1] - (x - a[i]))
			else:
				c += (a[i+1] - abs(x - a[i]))
				a[i+1] -= (a[i+1] - abs(x - a[i]))              

print(c) 

### FIXED CODE ###

n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    delta = max(0, a[i] + a[i+1] - x)
    a[i+1] -= delta
    if a[i+1] < 0:
        a[i] += a[i+1]
        a[i+1] = 0
    ans += delta
print(ans)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, Q = map(int, input().split())
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)
P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x
ans = [-1] * N
#print(G)
#print(P)
"""
def dfs(v, p):
    ans[v] = P[v] + p
    for vi in G[v]:
        if ans[vi] != -1:
            continue
        dfs(vi, ans[v])
dfs(0, 0)
"""
for v 
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    main()
for x in range(0, 1000):
    if not len(str(x)) == N:
        continue
    p = []
    for i, y in enumerate(num, start=0):
        if not y:
            y.append("0")
        try:
            p.append(str(x)[i] in y)
        except:
            continue
    if all(p):
        print(x)
        exit()

print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
num = [input().split() for y in range(M)]


def check(target):
    if not len(target) == N:
        return False
    for x, y in num:
        if not target[int(x)-1] == y:
            return False
    return True


for i in range(1000):
    if check(str(i)):
        print(i)
        exit()

print(-1)
n, l = map(int(input().split()))
l = [for i in range(n)]
s = sorted(l)
print(*s,sep = "")

### FIXED CODE ###

n, l = map(int , input().split())
s = sorted([input() for i in range(n)])
print(*s, sep = "")

# 1次元リストをアンパックを使用して出力する場合、print(*リスト名)で出力する。
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n,k = input_list()
  p = input_list()
  kakus = [(1+p[0])/2]
  for i in range(1, n):
    kaku = (1+p[i])/2
    pre = kakus[i-1]
    kakus.append(kaku+pre)
  ans = []
  for i in range(len(p)-k):
    ans.append(kakus[i+k]-kakus[i])
  print(max(ans))
  
import math
import fractions
import collections
import itertools
from functools import reduce
main()

### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)
N = int(input(""))
M = int(input(""))
if N<100 and N>M and M>0:
    if N == M:
        print("yes")
    else:
        print("No")
else:
    print("error")


### FIXED CODE ###

n,m = map(int, input().split())
print('Yes' if n==m else 'No')
import math
a, b, c = map(int, input().split())
print("YES" if math.gcd(a,b)%c == 0 else "NO")

### FIXED CODE ###

import fractions
a, b, c = map(int, input().split())
print("YES" if c%(fractions.gcd(a,b)) == 0 else "NO")
import sys

dList = []

for i,d in sys.stdin:
  if i <> 0: #1行目の行数情報はいらないので読み飛ばす
    dList.append(d)

print(len(set(dList)))

### FIXED CODE ###

n = int(input())

dList = [int(input()) for i in range(n)]

print(len(set(dList)))
x = int(input())
print([360*n//x for n in range(1, 500) if 360 % x == 0][0])

### FIXED CODE ###

import math
x=int(input())
print(360//math.gcd(360,x))
N = input()
S = 0
for i in N:
    S += int(i)
print("Yes" if N % S == 0 else "No")


### FIXED CODE ###

N = input()
S = 0
for i in N:
    S += int(i)
print("Yes" if int(N) % S == 0 else "No")
K = 500
num = int(input())
coin = num * K
print (coin)
X = int(input())
if coin >= X:
  print("Yes")
if coin < X:
  print("No")

### FIXED CODE ###

k,x = [int(x) for x in input().split()]

k = k * 500 

if k >= x:
  print("Yes")
else:
	print("No")
A = int(input())
B = int(input())

if A >=10 or B >=10:
    print("-1")
else:
    print(A*B)

### FIXED CODE ###

# coding: utf-8
# Your code here!

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

if A >=10 or B >=10:
    print("-1")
else:
    print(A*B)
n = int(input())
a = list(map(int,input().split()))

judge = True
ans = 1
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        judge = false
        break
        
if judge == True:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

judge = True
ans = 0

if 0 not in a:
    ans = 1
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            judge = False
            break
        
if judge:
    print(ans)
else:
    print(-1)
r = map(int,input().split())
s = 3 * r * r
print("s")

### FIXED CODE ###

r = int(input())
s = 3 * r * r
print(s)
a, b = map(int, input().split())
  ans=a+b
     
if ans>=24:
  ans=ans-24
      
print(ans)

### FIXED CODE ###

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

m=a+b

if m>=24:
  print(int(m-24))
else:
  print(int(m))
a=raw_input().split(' ')
print(max(a)-min(a))

### FIXED CODE ###

N=input()
a=[int(n) for n in raw_input().split(' ')]
print(max(a)-min(a))
n = int(input())
s, t = input().split()

r = []
for i in range(len(s)):
  str.append(s[i])
  str.append(t[i])

print(''.join(r))


### FIXED CODE ###

n = int(input())
s, t = input().split()

r = []
for i in range(n):
    r.append(s[i])
    r.append(t[i])

print(''.join(r))
n = int(input())
x = list(map(int,input().split()))
s = sum(x)

for i,j in zip(x,range(n)):
    x.remove(i)
    t = sorted(x)
    print(t)
    print(t[int(n/2-1)])
    x.insert(j,i)
    print(x)

### FIXED CODE ###

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

s = sorted(x)
u = s[int(n/2)]
t =s[int(n/2-1)]

for i in (x):
    if i < u:
        print(u)
    else:
        print(t)
x,a=map(int,(input().split()))
if x<a:
  print("0")
else:
  print{"10")

### FIXED CODE ###

x,a=map(int,(input().split()))
if x<a:
  print("0")
else:
  print("10")
from numba import njit
 
# @njit(cache=True)
@njit()
def convolve(a, b):
    def poww(aa, bb, mm):
        ss = 1
        tt = aa
        while bb:
            if bb % 2:
                ss = ss * tt % mm
                bb -= 1
            tt = tt * tt % mm
            bb //= 2
        return ss
    def fft(n, p, g, w, invw, f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(n, p, g, w, invw, f):
        d = 1
        while d < n:
            v = poww(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p = 1107296257
    g = 5
    n0, n1 = len(a), len(b)
    n = 1
    while n < max(n0, n1) * 2:
        n *= 2
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)

    w = poww(g, (p - 1) // n, p)
    invw = poww(w, p-2, p)
    fft(n, p, g, w, invw, a), fft(n, p, g, w, invw, b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(n, p, g, w, invw, a)
    invn = poww(n, p - 2, p)
    for i in range(n0 + n1 - 1):
        a[i] = a[i] * invn % p
    return a[:n0 + n1 - 1]

N = 100000
A = []
B = []
s = 0
for i in range(N):
    s = (s * 3 + i * 7) % 100
    a = s
    b = (s * 3 + a * 11) % 100
    A.append(a)
    B.append(b)

AB = convolve(A, B)


#####
A, B, C, K = map(int, input().split())
if K <= A + B:
    print(min(A, K))
else:
    print(A - (K - A - B))

### FIXED CODE ###

A, B, C, K = map(int, input().split())
if K <= A + B:
    print(min(A, K))
else:
    print(A - (K - A - B))
[a,b]=map(int,input().split())
print(a*b,(a+b)*)

### FIXED CODE ###

[a,b]=map(int,input().split())
print(a*b,(a+b)*2)
from re import sub
LIST = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
K = int(input())
return sub(r"[,\s]", "", LIST)[K-1]

### FIXED CODE ###

from re import sub
LIST = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
K = int(input())
print(sub(r"[\s]", "", LIST).split(",")[K-1])
import math

A, B = list(map(lambda x: int(x), input().split()))

print(int((A * B) / math.gcd(A, B)))

### FIXED CODE ###

import fractions

A, B = list(map(lambda x: int(x), input().split()))

print(int((A * B) / fractions.gcd(A, B)))
import math
N,M=map(int,input().split())
a=list(map(int,input().split()))
l=1
count=0
A=a[0]
ans=0
flag=1
while A%2==0:
    A=A//2
    count=count+1
for i in range(N):
    A=a[i]
    b=A//(2**count)
    if b==0 or b%2==0:
        flag=0
        break
    A=A//2
    l=l*A//math.gcd(l,A)
if flag==1:
    ans=M//l
    if ans%2==0:
        print(ans//2)
    else:
        print(ans//2+1)
else:
    print(0)

### FIXED CODE ###

import fractions
N,M=map(int,input().split())
a=list(map(int,input().split()))
l=1
count=0
A=a[0]
ans=0
flag=1
while A%2==0:
    A=A//2
    count=count+1
for i in range(N):
    A=a[i]
    b=A//(2**count)
    if b==0 or b%2==0:
        flag=0
        break
    A=A//2
    l=l*A//fractions.gcd(l,A)
if flag==1:
    ans=M//l
    if ans%2==0:
        print(ans//2)
    else:
        print(ans//2+1)
else:
    print(0)
a,b,k=map(int,input().split())
l=list(range(a,b+1))
ans=sorted(list(set(l[:k]+l[-k:])))
for i in ans:
    print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())
r = range(a,b+1)
for i in sorted (set(r[:k])|set(r[-k:])):
    print(i)
V=10**5
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

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

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)


### FIXED CODE ###

V=10**5+5
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

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

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if rootx==rooty:
            return
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

# for i in range(V*2):
#     uf.find(i)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    comb=Combination(n-1)
    for i in range(n-1):
        mPow=(mPow*(m-1))%mod
        modPow.append(mPow)
    for i in range(n-1-k,n):
        ans+=(m*modPow[i]*comb(n-1,i))%mod
    print(ans%mod)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    if n==1:
        print(m)
    elif m==1:
        if k==n-1:
            print(1)
        else:
            print(0)
    else:
        comb=Combination(n-1)
        for i in range(n-1):
            mPow=(mPow*(m-1))%mod
            modPow.append(mPow)
        for i in range(n-1-k,n):
            ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
        print(ans%mod)
if __name__=="__main__":
    main()
n, a, b = map(int, input().split())


ans = (n //(a + b)) * a
if n % (a + b) < a:
  print(ans + (n % (a + b))
elif n % (a + b) > a:
  print(ans + a)
        

### FIXED CODE ###



n, a, b = map(int, input().split())
ans = n // (a + b) * a
rem = n % (a + b)
ans += min(rem, a)
print(ans)
n = input()
houses = map(lambda x: int(x), raw_input().split())
houses = sorted(list(set(houses)))
print houses[-1] - houses[0]

### FIXED CODE ###

r,g,b=tuple(map(lambda x: int(x), raw_input().split()))
ans = "YES" if (100*r+10*g+b) % 4 == 0 else "NO"
print ans
N, Q = map(int, input().split())

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

ans_list = [0] * N

points = [0] * N
for q in range(Q):
    p, x = map(int, input().split())
    points[p - 1] += x

ans_list[0] = points[0]
for n in range(1, N):
    ans_list[n] = ans_list[graph_lis[n][0]] + points[n]
print(*ans_list)

### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
graph_lis = [[] for n in range(N)]

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

ans = [0] * N
for q in range(Q):
    p, x = map(int, input().split())
    ans[p - 1] += x

deq = deque([0])
visited = [False] * N
while deq:
    parent = deq.popleft()
    edge = graph_lis[parent]
    for v in edge:
        if not visited[v]:
            ans[v] += ans[parent]
            deq.append(v)
    visited[parent] = True
print(*ans)
a=int(input())
if a<105:
  print(0)
elif 105<=a<135:
  print(1)
elif 135<=a<165:
  print(2)
elif 165<=a<189:
  print(3)
elif:189<=a:
  print(4)

### FIXED CODE ###

a=int(input())
if a<105:
  print(0)
if 105<=a<135:
  print(1)
if 135<=a<165:
  print(2)
if 165<=a<189:
  print(3)
if 189<=a<195:
  print(4)
if 195<=a:
  print(5)