Harryxun/stf_run huggingface dataset:
from collections import deque

def solve():
    N, M, K = map(int, input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    a, b = [0], [0]
    for i in range(N):
        a.append(a[i] + A[i])
    for i in range(M):
        b.append(b[i] + B[i])

    ans = 0
    j = M

    for i in range(len(A)):
        if a[i] > K:
            break
        while b[j] < K - a[i]:
            j -= 1
        ans = max(ans, i+j)
    
    print(ans)
            
solve()

### FIXED CODE ###

from collections import deque
 
def solve():
    N, M, K = map(int, input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
 
    a, b = [0], [0]
    for i in range(N):
        a.append(a[i] + A[i])
    for i in range(M):
        b.append(b[i] + B[i])
 
    ans = 0
    j = M
 
    for i in range(len(a)):
        if a[i] > K:
            break
        while b[j] > K - a[i]:
            j -= 1
        ans = max(ans, i+j)
    
    print(ans)
            
solve()
x = int(input())
y = int(input())
print(x * y)

### FIXED CODE ###

x, y = list(map(int, input().split()))
print(x * y)
def f(a b)
return a*b 2*a+ 2*b

### FIXED CODE ###

nums = input().split(" ")
a =int( nums[0])
b = int(nums[1])

print(a*b, (a+b)*2)
n = int(input())
a=input().split()
a_int = [int(i) for i in a]

ans=[0]*n

for i in range(n-1):
    ans[i]=0

    for m in range(n-1):

        if a_int[m] == i+1:
            ans[i]=ans[i]+1

for i in range(n):
    print(str(ans[i]))

### FIXED CODE ###

import math

n = int(input())
print(str(2*math.pi*n))
N,K = map(int,input().split())
import sys
sys.setrecursionlimit(10000000)

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def dfs(N,X):
    if N == 0:
        return 0 
    elif X <= 1 + a[N-1]:
        return dfs(N-1, X-1)
    elif X == 2 + a[N-1]:
        return p[N-1]
    elif X <= 2 + 2*a[N-1]:
        return p[N-1] + 1 + dfs(N-1, X-2-a[N-1])
    else:
        2*p[N-1]+1
    
print(dfs(N,K))

### FIXED CODE ###

N,K = map(int,input().split())
import sys
sys.setrecursionlimit(10000000)

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def dfs(N,X):
    #print(N,X)
    if N == 0:
        return 0 if X != 1 else 1
    elif X <= 1 + a[N-1]:
        return dfs(N-1, X-1)
    elif X == 2 + a[N-1]:
        return p[N-1] + 1
    elif X <= 2 + 2*a[N-1]:
        return p[N-1] + 1 + dfs(N-1, X-2-a[N-1])
    else:
        return 2*p[N-1]+1
    
print(dfs(N,K))
import sys

h, w, m = map(int, input().split())
row = [0]*h
col = [0]*w
bomb = set()
for x in sys.stdin.readlines():
    H, W = map(int, input().split())
    bomb.add((H-1, W-1))
    row[H-1] += 1
    col[W-1] += 1

maxrow = max(row)
maxcol = max(col)
ans = maxcol + maxrow - 1
p, q = [], []
for i in range(h):
    if row[i] == maxrow:
        p.append(i)
for i in range(w):
    if col[i] == maxcol:
        q.append(i)

for i in p:
    for j in q:
        if (i, j) not in bomb:
            print(ans + 1)
            exit()
print(ans)


### FIXED CODE ###

import sys

h, w, m = map(int, input().split())
row = [0]*h
col = [0]*w
bomb = set()
for x in range(m):
    H, W = map(int, input().split())
    bomb.add((H-1, W-1))
    row[H-1] += 1
    col[W-1] += 1

maxrow = max(row)
maxcol = max(col)
ans = maxcol + maxrow - 1
p, q = [], []
for i in range(h):
    if row[i] == maxrow:
        p.append(i)
for i in range(w):
    if col[i] == maxcol:
        q.append(i)

for i in p:
    for j in q:
        if (i, j) not in bomb:
            print(ans + 1)
            exit()
print(ans)
N = int(input())

ALL = N*800
TIMES = N //15


if N < 15:
    print(ALL)
else:
    print(All - (800*TIMES))

### FIXED CODE ###

N = int(input())
sum = 800 * N
otsuri = (N // 15) * 200

print(sum - otsuri)
a,b,c = map(int,input().split())
print("Yes",if a<=c<=b else "No")

### FIXED CODE ###

a,b,c = map(int,input().split())
print("Yes" if a<=c<=b else "No")
N,A,B=map(int,input().split())
x=N//(A+B)
y=N%(A+B)
if y<A:
    print(x*A+y)
else:
    print(x*a+a)

### FIXED CODE ###

N,A,B=map(int,input().split())
x=N//(A+B)
y=N%(A+B)
if y<A:
    print(x*A+y)
else:
    print(x*A+A)
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
DistK=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

def dfs(s,dist,flag,Branch,DistK):
  DistK[s]=dist
  flag[s]=1
  
  for i in range(len(Branch[s])):
    if flag[Branch[s][i][0]]==0:
      dfs(Branch[s][i][0],dist+Branch[s][i][1],flag,Branch,DistK)
      
  return 1
dfs(K-1,0,flag,Branch,DistK)
for i in range(Q):
  x,y = map(int,input().split())
  print(DistK[x-1]+DistK[y-1])
  

### FIXED CODE ###

import collections
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
Dist=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

que=collections.deque()
que.append(K-1)
Dist[K-1]=0
while len(que):
  u=que.pop()
  for i,j in Branch[u]:
    if Dist[i]==float("Inf"):
      Dist[i]=Dist[u]+j
      que.append(i)

  
for i in range(Q):
  x,y = map(int,input().split())
  print(Dist[x-1]+Dist[y-1])
n = int(input())
ans = 0
for i in range(1,n + 1):
	if len(str(i)) % 2 == 1:
		ans += 1
print(ans) 

### FIXED CODE ###

a, b, c = input().split()
x = int(a) - int(b)
if int(c) <= x:
	print(0)
else:
	y = int(c) - x
	print(y)
_=int(input())
s=input()
mod=7+10**9
def dp(t,l):
    if len(t)==1:
        if t[0] in l:
            return 1
        else:
            return 2
    elif t[0] in l:
        return dp(t[1:],l)%mod
    else:
        g=l+[t[0]]
        ans=dp(t[1:],g)+dp(t[1:],l)
        ans%=mod
        return ans
print(dp(s,[])-1)

### FIXED CODE ###

_=input()
s=input()
mod=7+10**9
ans=1
for i in range(26):
    ans*=1+s.count(chr(ord('a') + i))
    ans%=mod
print(ans-1)
#C
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
i = 0
j = 0
for _ in range(n+m)
    # print(i,j,k)
    if n <= i:#
        k -= b[j]
        j += 1
        if k < 0:
            break
        ans += 1
        if k == 0:
            break
        continue
    elif n <= j:
        k -= a[i]
        i += 1
        if k < 0:
            break
        ans += 1
        if k == 0:
            break
        continue
    if a[i] < b[j]:
        k -= a[i]
        i += 1
    else:
        k -= b[j]
        j += 1
    if k < 0:
        break
    ans += 1
    if k == 0:
        break
print(ans)

### FIXED CODE ###

#C
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = [0]
B = [0]
#読書時間A,B
for i in range(n):
    A.append(A[i] + a[i])
for i in range(m):
    B.append(B[i] + b[i])
ans = 0
j = m
#Aを増やしたときA+Bがkより小さくなるようなi,jを決めて最大値を決めてる
for i in range(n + 1):
    if A[i] > k:
        break
    #K<=A[i]+B[j]となるまでjを引く>>k-A<=B
    while A[i] + B[j] > k:
        j -= 1
    ans = max(ans, i + j)
print(ans)
a,b,c,d=map(int,input().split())
x==c-a
y==d-b
print("U"*y+"R"*x+"D"*y+"L"*x+"L"+"U"*(y+1)*"R"*(x+1)+"D"+"R"+"D"*(y+1)+"L"*(x+1)+"U")

### FIXED CODE ###

a,b,c,d=map(int,input().split())
x=c-a
y=d-b
print("U"*y+"R"*x+"D"*y+"L"*x+"L"+"U"*(y+1)+"R"*(x+1)+"D"+"R"+"D"*(y+1)+"L"*(x+1)+"U")
N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(l[:N]))


### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
N = int(input())
t0, x0, y0 = 0, 0, 0
flag=True
for i in range(N):
    t1,x1,y1 = [int(j) for j in input().split()]
    dt = t1 - t0
    dist = abs(x0-x1) + abs(y0-y1)

    if dist > dt:
	print('NO')
	flag=False

    elif (dist%2==0 and dt%2==0) or  (dist%2==1 and dt%2==1):
	t0, x0, y0 = t1, x1, y1

    else:
	print('NO')
	flag=False

if flag:
    print('YES')

### FIXED CODE ###

import sys

def main():
    N = int(input())
    t, x, y = 0, 0, 0

    for _ in range(N):
        next_t, next_x, next_y = [int(__) for __ in input().split()]

        delta_t = next_t - t
        distance = abs(next_x - x) + abs(next_y - y)

        if distance > delta_t:
            print("No")
            sys.exit()

        if (delta_t - distance) % 2 != 0:
            print("No")
            sys.exit()

        t, x, y = next_t, next_x, next_y

    print("Yes")

main()
dic={}
for i in range(10001):
    dic[i]=0
input()
for n in map(int,input().split()):
    dic[n]+=1
m=0
for i in range(1,9999):
    m=max(m,dic[i]+dic[i+1]+dic[i+2])
print(m)


### FIXED CODE ###

dic={}
for i in range(100002):
    dic[i]=0
input()
for n in map(int,input().split()):
    dic[n]+=1
m=0
for i in range(0,100000):
    m=max(m,dic[i]+dic[i+1]+dic[i+2])
print(m)
n,x,=map(int, input().split())
w_list = list(map(int, input().split()))

d=0
for i in range(n+1):
   d=d+w_list[i]
   if(d>x):
       break
print(i+1)


### FIXED CODE ###

n,x = map(int,input().split())
li = list(map(int,input().split()))
 
ans = 1
now = 0
 
for i in li:
    now += i
    if now <= x:
        ans += 1
    else:
        break
 
print(ans)
n,m = map(int, input().split())
c = [0]*n
for i in range(m):
  a,b = map(int, input().split())
  c[a] += 1
  c[b] += 1
for i in c:
  print(i)

### FIXED CODE ###

n,m = map(int, input().split())
c = [0]*n
for i in range(m):
  a,b = map(int, input().split())
  c[a-1] += 1
  c[b-1] += 1
for i in c:
  print(i)
import collections
import sys
import itertools
from tqdm import tqdm
from pprint import pprint

def read_a_integer():
    return int(sys.stdin.readline())

def read_a_list(dtype):
    return list(map(dtype, sys.stdin.readline().split()))

def brute_force(N, D):
    def get_distance(G):
        queue = collections.deque()
        queue.append(1)
        distance = [-1] * N
        distance[0] = 0

        while queue:
            u = queue.popleft()
            for v in G[u]:
                if distance[v-1] == -1:
                    distance[v-1] = distance[u-1] + 1
                    queue.append(v)
        return distance

    ans = 0
    all_edges = [(u, v) for u in range(1, N+1) for v in range(1+u, N+1)]
    for graph in tqdm(itertools.combinations(all_edges, N - 1)):
        G = collections.defaultdict(list)
        # print(graph)
        # graph = [(1,4),(1,7),(3,4),(4,5),(4,6),(2,3)]
        for u, v in graph:
            G[u].append(v)
            G[v].append(u)
        # print(G)
        # exit(0)
        distance = get_distance(G)
        # print(distance)
        if distance == D:
            ans += 1
            print("-" * 50)
            pprint(G)
            print("-" * 50)
        # break
    print(ans)


def main():
    N = read_a_integer()
    D = read_a_list(int)
    if D[0] != 0:
        print(0)
        return
    counter = collections.Counter(D)
    if counter[0] != 1:
        print(0)
        return
    max_D = max(D)
    ans = 1
    for i in range(2, max_D + 1):
        if i not in counter:
            print(0)
            return
        ans = (ans * (counter[i-1] ** counter[i])) % 998244353
    print(ans)
    # brute_force(N, D)

        


if __name__ == "__main__":
    main()


### FIXED CODE ###

import collections
import sys
def read_a_integer():
    return int(sys.stdin.readline())

def read_a_list(dtype):
    return list(map(dtype, sys.stdin.readline().split()))


def main():
    N = read_a_integer()
    D = read_a_list(int)
    if D[0] != 0:
        print(0)
        return
    counter = collections.Counter(D)
    if counter[0] != 1:
        print(0)
        return
    max_D = max(D)
    ans = 1
    for i in range(2, max_D + 1):
        if i not in counter:
            print(0)
            return
        ans = (ans * (counter[i-1] ** counter[i])) % 998244353
    print(ans)
    # brute_force(N, D)

        


if __name__ == "__main__":
    main()
N = int(input())
m,k = input().split()
result=int(m)*int(k)
print("%d"%result)
if result>=10**18:
    print("-1")





### FIXED CODE ###

A= int(input())
B = list(map(int, input().split()))
result = 1
if 0 in B:
    print(0)
    exit()

for S in B:
    result *= S
    if result > 10**18:
        print(-1)
        exit()
print("%d"%result)
from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                que.append((i, j))
                a[i][j] = 0

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((nx,ny))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                que.append((i, j))
                a[i][j] = 0

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((ny,nx))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())
# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  naHn  = np.array(list(map(int, input().split())))
  naDP  = np.zeros(iNum, dtype='int64')
  naLen = np.ones(iK) * 10**9
  for iI0 in range(1, iK+1):
    naLen = naDP[0:iI0] + np.abs(- naHn[0:iI0] + naHn[iI0])
    naDP[iI0] = naLen.min()
  if iNum >= iK+1:
    for iI0 in range(iK+1, iNum):
      naLen = naDP[iI0-iK:iI0] + np.abs(- naHn[iI0-iK:iI0] + naHn[iI0])
      naDP[iI0] = naLen.min()
    print(naDP[iNum-1])

if __name__ == '__main__':
  fnSolv()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  naHn  = np.array(list(map(int, input().split())))
  naDP  = np.zeros(iNum, dtype='int64')
  naLen = np.ones(iK) * 10**9
  for iI0 in range(1, iNum):
    iK0 = min([iK, iI0])
    naLen = naDP[iI0-iK0:iI0] + np.abs(- naHn[iI0-iK0:iI0] + naHn[iI0])
    naDP[iI0] = naLen.min()
  print(naDP[iNum-1])

if __name__ == '__main__':
  fnSolv()
N, K = map(int,input().split())
def comb(n,k):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if k < 0:
        return 0
    if k == 0:
        return 1
    return comb(n-1,k-1) * n // k
R = N-K
MOD = 10**9+7
A = K-1
B = R-1
if N == K:
    print(1)
    for i in range(2, K+1):
        print(0)
else:
    for i in range(1, K+1):
        x = comb(A, i-1)
        y = comb(B, i-2)
        z = comb(B, i-1)
        w = comb(B, i)
        ans = x*(y+2*z+w)
        print(ans % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(3000)
N, K = map(int,input().split())
def comb(n,k):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if k < 0:
        return 0
    if k == 0:
        return 1
    return comb(n-1,k-1) * n // k
R = N-K
MOD = 10**9+7
A = K-1
B = R-1
if N == K:
    print(1)
    for i in range(2, K+1):
        print(0)
else:
    for i in range(1, K+1):
        x = comb(A, i-1)
        y = comb(B, i-2)
        z = comb(B, i-1)
        w = comb(B, i)
        ans = x*(y+2*z+w)
        print(ans % MOD)
(let ((s (read-line)))
  (princ (if (and (char= (char s 0) #\A)
                  (= 1 (count #\C s :start 2 :end (- (length s) 1) :test #'char=))
                  (not (some #'upper-case-p (remove #\C (subseq s 2) :count 1))))
    "AC"
    "WA")))

### FIXED CODE ###

s = input()
subs = s[2:-1]

if s[0] == 'A' and subs.count('C') == 1:
    for char in s[1:]:
        if char.isupper() and char != 'C':
            break
    else:
        print("AC")
        exit(0)

print("WA")
i,x = '1',input()
while x != "0":
  print('Case '+i+': '+x)
  i,x = i+1,input()


### FIXED CODE ###

i,x = 1,input()
while x != "0":
  print('Case '+str(i)+': '+x)
  i,x = i+1,input()
n=int(input())
a= list(map(int,input().split()))
print(*a[::-2],*a[a%2::2])

### FIXED CODE ###

n=int(input())
a= list(map(int,input().split()))
if n%2 ==1:
    ans = a[::-2]+a[1::2]
else:
    ans = a[::-2]+a[0::2]
print(*ans)
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans=[]
for i in range(n+1-k):
  ans.append(h[i+k-1]-h[i])
print(min(ans))


### FIXED CODE ###

day=int(input())
s='Christmas'
eve=25-day
for i in range(eve):
  s=s+' Eve'
print(s)
n, k = map(int,input().split())
def kai(m):
    r = 1
    for i in range(1,m+1):
        r = r * i
    return r
def c(a,b):
    r = kai(a)/kai(b)/kai(a-b)
    return r

for j in range(1,k+1):
    print(int(c(n-k+1,j)*c(k-1,j-1)))


### FIXED CODE ###



import sys
sys.setrecursionlimit(10000)

n, k = map(int,input().split())
nck = {}

def c(n, r):
    
    if n<r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

for j in range(1,k+1):
    r = (c(n-k+1,j)*c(k-1,j-1))%(10**9+7)
    print(r)
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)
import sys
S = int(input())
l = list(S)
s = int(len(S))

num = 0
for i in range(s):
    if l[i] == l[i+1]:
        print("Bad")
        sys.exit()
    else:
        num += 1
        if num == 3:
            print("Yes")

### FIXED CODE ###

S = str(input())
l = list(S)

for i in range(len(S)-1):
    if l[i] == l[i+1]:
        print("Bad")
        break
else:
     print("Good")
N, M, K = list(map(int,input().split()))
m = 998244353

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c

func = combination_mod(N-1,m)
ans = 0
for k in range(K+1):
    ans_temp = M
    ans_temp = (ans_temp * func.calc(k)) % m
    ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
    ans += ans_temp
    ans = ans % m
print(ans)


### FIXED CODE ###

N, M, K = list(map(int,input().split()))
m = 998244353

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == self.N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c
if N == 1:
    print(M%m)
    exit()
elif M == 1:
    if N > K+1:
        print(0)
    else:
        print(1)
    exit()
else:
    func = combination_mod(N-1,m)
    ans = 0
    for k in range(K+1):
        ans_temp = M
        ans_temp = (ans_temp * func.calc(k)) % m
        ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
        ans += ans_temp
        ans = ans % m
    print(ans)
A, B, C = map(int,input().split())
K = int(input())
L = [A, B, C]
S = sorted(L)

print(S[2] * 2 ** K + S[0] + S[1])


### FIXED CODE ###

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

if B >= A:
    print(A)
else:
    print(A-1)
a,b=map(int,input().sprit())
if a<=b:
  print("unsafe")
else:
  print("safe")

### FIXED CODE ###

a,b=map(int,input().split())
if a<=b:
  print("unsafe")
else:
  print("safe")
import fileinput
 
lines = list(fileinput.input())
 
for x in lines():
	print(x[:3])

### FIXED CODE ###

import fileinput
 
lines = list(fileinput.input())
 
for x in lines:
	print(x[:3])
a,b = inut().split()
ab = int(a+b)

print("Yes" if ab%(ab**0.5)==0 else "No")


### FIXED CODE ###


a,b = input().split()
ab = int(a+b)

print("Yes" if ab%(ab**0.5)==0 else "No")
a,b = map(int,input())
print(a+b if a+b < 10 else "error")

### FIXED CODE ###

a,b = map(int,input().split())
print(a+b if a+b < 10 else "error")
N = int(input())
p = list(map(int, input().split()))
cnt = 0
l = list()

for i in range(N-1):
    if p[i] > p[i+1]:
        cnt += 1
        l.append(i)

if cnt <= 1:
    print('YES')
elif (cnt==2) and (p[l[0]-1] <= p[l[1]+1] <= p[l[0]+1]) and (p[l[1]] <= p[l[0]] <= p[l[1]+2]):
    print('YES')
else: print('NO')


### FIXED CODE ###

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

for i in range(N-1):
    if p[i] > p[i+1]:
        cnt += 1
        l.append(i)

if cnt > 2:
    print('NO')
if cnt == 1:
    print('NO')
if cnt == 0:
    print('YES')
if cnt == 2:
    p[l[0]], p[l[1]+1] = p[l[1]+1], p[l[0]]
    cnt = 0
    for i in range(N-1):
        if p[i] > p[i+1]:
            cnt += 1
            l.append(i)
    if cnt == 0:
        print('YES')
    else:
        print('NO')