Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0135
WA
"""
import sys
from sys import stdin
from math import sqrt, acos, cos, sin, radians, degrees
input = stdin.readline


def solve(time):
    # 12????????????90???
    short_hand_angle = time[1] * -6 + 90
    x_s = cos(radians(short_hand_angle))
    y_s = sin(radians(short_hand_angle))

    long_hand_angle = (time[0]*60+time[1])/(12*60) * -360 + 90
    x_l = cos(radians(long_hand_angle))
    y_l = sin(radians(long_hand_angle))
    c = (x_s * x_l + y_s * y_l) / (sqrt(x_s**2 + y_s**2) * sqrt(x_l**2 + y_l**2))
    ans = degrees(acos(c))

    if ans < 30:
        return 'alert'
    elif ans >= 90:
        return 'safe'
    else:
        return 'warning'


def main(args):
    # n = int(input())
    n = 1
    for _ in range(n):
        time = [int(x) for x in input().split(':')]
        result = solve(time)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0135
WA
"""
import sys
from sys import stdin
from math import sqrt, acos, cos, sin, radians, degrees
input = stdin.readline


def solve(time):
    # 12????????????90???
    short_hand_angle = time[1] * -6 + 90
    x_s = cos(radians(short_hand_angle))
    y_s = sin(radians(short_hand_angle))

    long_hand_angle = (time[0]*60+time[1])/(12*60) * -360 + 90
    x_l = cos(radians(long_hand_angle))
    y_l = sin(radians(long_hand_angle))
    c = (x_s * x_l + y_s * y_l) / (sqrt(x_s**2 + y_s**2) * sqrt(x_l**2 + y_l**2))
    ans = degrees(acos(c))

    if ans < 30:
        return 'alert'
    elif ans >= 90:
        return 'safe'
    else:
        return 'warning'


def main(args):
    n = int(input())
    # n = 1
    for _ in range(n):
        time = [int(x) for x in input().split(':')]
        result = solve(time)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])
ABC = map(int, input().split())
print(ABC[0]*ABC[1]/2)

### FIXED CODE ###

AB, BC, CA = map(int, input().split())
print(int(AB*BC/2))
N = int(input())
S = input()

count = 0
for i in range(n-2):
  if S[k:k+3] == "ABC":
    count +=1
print("%d"%(count))    

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n-2):
  if s[i:i+3] == 'ABC':
    ans += 1
print(ans)
N=input()
N=int(N)
A=1
B=1
flag=0
if N>81:
    flag=0
else:
    for A in range(10):
    for B in range(10):
        if N==A*B:
        flag=1
    else:
        flag=0
if flag==0:
    print('NO')
else:
    print('YES')


### FIXED CODE ###

n = int(input())

flag = 0

for i in range(1,10):
    for j in range(1,10):
        if i*j == n:
            flag = 1
            break

print( "Yes" if flag == 1 else "No" )
a,b = input().split()
if(a>(b*2)):
  print(a-b*2)
else:
  print(0)

### FIXED CODE ###

a,b = input().split()
a,b = int(a),int(b)
print(max(a-2*b,0))
def dfs(c,v,sheet,space,n):
  x,y=divmod(v,n)
  for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
    if 0<=x+dx<n and 0<=y+dy<n:
      nv=(x+dx)+(y+dy)*n
      if sheet[nv]>c:
        sheet[nv]=c
        dfs(c+space[nv],nv,sheet,space,n)

def main(n,p):
  sheet=[min(i%n,i//n,n-i%n-1,n-i//n-1) for i in range(n**2)]
  space=[1]*(n**2)
  #for i in range(n):
  #  print(sheet[i*n:(i+1)*n])
  ans=0
  for x in p:
    x-=1
    ans+=sheet[x]
    space[x]=0
    dfs(sheet[x],x,sheet,space,n)
  print(ans)

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

### FIXED CODE ###

from numba import njit
import numpy as np
@njit
def dfs(v,c,h,stay):
    # hを更新
    x,y=divmod(v,n)
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        nx,ny=x+dx,y+dy
        if 0<=nx<n and 0<=ny<n:
            nv=nx*n+ny
            if h[nv]>c:
                h[nv]=c
                dfs(nv,c+stay[nv],h,stay)

@njit
def main(n,p):
    h=[min(i//n,n-i//n-1,i%n,n-i%n-1) for i in range(n**2)]
    h=np.array(h)
    stay=np.full(n**2,1)
    ans=0

    for v in p:
        c=h[v]
        ans+=c
        stay[v]=0
        dfs(v,c,h,stay)
    print(ans)

    #for i in range(n):
    #    print(h[i*n:(i+1)*n])
if __name__=='__main__':
    n=int(input())
    p=np.array(list(map(int,input().split())),np.int32)
    p-=1
    main(n,p)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n,a,b=INT()
    print(min(n*a,b))

if  __name__=='__main__':
    main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n,a,b=MAP()
    print(min(n*a,b))

if  __name__=='__main__':
    main()
import math

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

E =C*D//math.gcd(C,D)

if A%C == 0:
    C_div = B//C - A//C + 1
else:
    C_div = B//C - A//C

if A%D == 0:
    D_div = B//D - A//D + 1
else:
    D_div = B//D- A//D


if A%E == 0:
    CandD_div  = B//E - A//E + 1
else:
    CandD_div  = B//E- A//E


ans = B - A + 1 - (C_div + D_div - CandD_div)
print(ans)


### FIXED CODE ###

import fractions

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

E =C*D//fractions.gcd(C,D)

if A%C == 0:
    C_div = B//C - A//C + 1
else:
    C_div = B//C - A//C

if A%D == 0:
    D_div = B//D - A//D + 1
else:
    D_div = B//D- A//D


if A%E == 0:
    CandD_div  = B//E - A//E + 1
else:
    CandD_div  = B//E- A//E


ans = B - A + 1 - (C_div + D_div - CandD_div)
print(ans)
s = list(str(input()))

if s[0] == s[1] or a[1] == s[2] or s[2] == s[3]:
    print('Bad')
else:
    print('Good')


### FIXED CODE ###

s = list(str(input()))

if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
    print('Bad')
else:
    print('Good')
def check(a,cnt)
  b = [int(x)%2 for x in a]
  if 1 in b:
    return 0,cnt
  else :
    cnt +=1
    b = [int(x)/2 for x in a]
    return 1,cnt

N = input()
a = input().split()
cnt = 0
while(1):
  m,cnt = check(a,cnt)
  if m == 0:
    print(cnt)
  else :
    continue

### FIXED CODE ###

def check(a,cnt):
  c = [int(x)%2 for x in a]
  if 1 in c:
    return 0,cnt,a
  else :
    cnt +=1
    b = [int(x)/2 for x in a]
    return 1,cnt,b
 
N = input()
a = input().split()
cnt = 0
m = 1
while(m != 0):
  m,cnt,a = check(a,cnt)
  if m == 0:
    print(cnt)
  else :
    continue
if n<10:
  print(n)
else:
  L=list(map(int, list(str(n))))
  if(L.count(9)==len(L)) or (L[0]!=9 and L.count(9)==len(L) -1):
    print(sum(L))
  else :
    print(9*(len(L)-1)+int(L[0])-1)



### FIXED CODE ###

n=int(input())
if n<10:
  print(n)
else:
  L=list(map(int, list(str(n))))
  if(L.count(9)==len(L)) or (L[0]!=9 and L.count(9)==len(L) -1):
    print(sum(L))
  else :
    print(9*(len(L)-1)+int(L[0])-1)
x =map(int, input().replace(" ", ""))
print("YES" if x%4 == 0 else "NO")

### FIXED CODE ###

x =int(input().replace(" ", ""))
print("YES" if x%4 == 0 else "NO")
xs,ys,xt,yt=map(int,input().split())
N=int(input())
import numpy as np
XYR=np.empty((N+2,3),dtype=np.float64)
XYR[1:-1,:]=np.array([input().split() for i in range(N)])
XYR[0,:]=[xs,ys,0]
XYR[-1,:]=[xt,yt,0]
X,Y,R=XYR.T
c=np.maximum(0,np.sqrt(np.square(X[None,:]-X[:,None])+np.square(Y[None,:]-Y[:,None]))-R[None,:]-R[:,None])
from scipy.sparse import*
g=csgraph.csgraph_from_dense(c,null_value=np.inf)
print(csgraph.dijkstra(g,directed=0,indices=0)[-1])

### FIXED CODE ###

xs,ys,xt,yt=map(int,input().split())
N=int(input())
import numpy as np
XYR=np.empty((N+2,3),dtype=np.float64)
XYR[1:-1,:]=np.array([input().split() for i in range(N)])
XYR[0,:]=xs,ys,0
XYR[-1,:]=xt,yt,0
X,Y,R=XYR.T
c=np.maximum(0,np.sqrt(np.square(X[None,:]-X[:,None])+np.square(Y[None,:]-Y[:,None]))-R[None,:]-R[:,None])
c[range(N+2),range(N+2)]=-1
from scipy.sparse import*
g=csgraph.csgraph_from_dense(c,null_value=-1)
print(csgraph.dijkstra(g,indices=0)[-1])
n = int(raw_input())
sum = 0
tmp = n

while tmp > 0:
    sum += tmp % 10
    tmp /= 10

if n % sum == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())

def S(N):
  if N < 10:
    return N
  return N%10 + S(N//10)

answer = 'No' if N%S(N) else 'Yes'
print(answer)
a,b=map(int,input().split())
if a-2＊b>0:
  print(a-2＊b)
else:
  print(0)


### FIXED CODE ###

a,b=map(int,input().split())
if a-2*b>0:
  print(a-2*b)
else:
  print(0)
import sys
input = sys.stdin.readline
w=input().strip()
from collections import Counter
s~Counter(w)
for a in s.values():
    if a%2==1:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

import sys
input = sys.stdin.readline
w=input().strip()
from collections import Counter
s=Counter(w)
for a in s.values():
    if a%2==1:
        print("No")
        exit()
print("Yes")
H,W,M = map(int, input().split())
hNum = [0]*H
wNum = [0]*W
bom = [[0] * W for i in range(H)]
for i in range(M):
  h,w = map(int, input().split())
  bom[h-1][w-1] = 1
  hNum[h-1] += 1
  wNum[w-1] += 1

hmax = max(hNum)
wmax = max(wNum)
ans = hmax + wmax
if bom[hNum.index(hmax)][wNum.index(wmax)] == 1:
  ans -= 1

print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
hs = [0] * H
ws = [0] * W
s = set()

for i in range(M):
  r,c = map(int,input().split())
  r -= 1
  c -= 1
  hs[r] += 1
  ws[c] += 1
  s.add((r,c))
mh = 0
mw = 0
for i in range(H):
  mh = max(mh, hs[i])
for j in range(W):
  mw = max(mw, ws[j])

i_s = list()
j_s = list()
for i in range(H):
  if mh == hs[i]:
    i_s.append(i)
for j in range(W):
  if mw == ws[j]:
    j_s.append(j)
ans = mh + mw
for i in i_s:
  for j in j_s:
    if (i,j) in s:
      continue
    print(ans)
    exit()
ans -= 1
print(ans)
import numpy as np
from numba import njit
@njit
def main():
    N = int(input())
    An = list(map(int, input().split()))
    ans = 0
    ng = set()
    a_An = np.array(An)
    for i, a in enumerate(An):
        temp = a_An / a
        temp[i] = 0.1
        check = np.where(temp % 1 == 0)
        check = check[0]
        # check = np.delete(check, np.where(check == i))
        # check = check[check != i]
        if len(check) > 0:
            ng = ng | set(check)
    print(N-len(ng))

if __name__ == "__main__":
    main()

### FIXED CODE ###

N = int(input())
An = list(map(int, input().split()))
An.sort()
max_n = max(An)
dp = [0] * (max_n + 1)
for i in range(N):
    if dp[An[i]] != 0:
        dp[An[i]] = 2
        continue
    for j in range(1, max_n//An[i] + 1):
        dp[An[i]*j] += 1
ans = 0
for a in An:
    if dp[a] == 1:
        ans += 1
print(ans)
from math import factorial
import sys
input = sys.stdin.readline
def ncr(n,r):
 if n <= 1:
  return 0
 elif n == 2:
  return 1
 else:
  return  factorial(n) / factorial(r) / factorial(n - r)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
   tmp += 1
  else:
   ans += ncr(tmp,2)
   tmp = 1
ans += ncr(tmp,2)
print(int(ans))


### FIXED CODE ###

from math import factorial
import sys
input = sys.stdin.readline
def ncr(n):
 if n <= 1:
  return 0
 elif n == 2:
  return 1
 else:
  return  (factorial(n) // 2) // factorial(n - 2)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
   tmp += 1
  else:
   ans += ncr(tmp)
   tmp = 1
ans += ncr(tmp)
print(ans)
import string

count = {x: 0 for x in string. ascii_lowercase}
lines = ""

while True:
    try:
        lines += input().lower()
    except EOFError:
        break

for c in lines:
    if 'a' <= c <= 'z':
        count[c] += 1

for key, num in string.ascii_lowercase:
    print("{0} : {1}".format(key, count[key]))

### FIXED CODE ###

import string
   
count = {x: 0 for x in string.ascii_lowercase}
lines = ""
   
while True:
    try:
        lines += input().lower()
    except EOFError:
        break
           
for c in lines:
    if 'a' <= c <= 'z':
        count[c] += 1
           
for key in string.ascii_lowercase:
    print("{0} : {1}".format(key, count[key]))
import sys
dp=[0]+[1<<20]*10000
n=int(input())
a=list(map(int,sys.stdin.readlines()))
for i in range(1,len(a)):
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a[i-1]),(dp[i-j],dp[j]+a[i-1])])
print(dp[n//2])

### FIXED CODE ###

dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    a=int(input())
    for j in range(i//2+1):
        if dp[j]>dp[i-j]+a:dp[j]=dp[i-j]+a
        if dp[i-j]>dp[j]+a:dp[i-j]=dp[j]+a
print(dp[n//2])
n,k = map(int,input().split())
p_ = list(map(int,input().split()))

def calc_ex(x):
    return  x/2 + 0.5
p_ = list(map(calc_ex,p_))

cnt,res =0,[]
for i in range(2,n):
    cnt = sum(p_[i-k+1:i+1])
    res.append(cnt)

print(max(res))


### FIXED CODE ###

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

def calc_ex(x):
    return  x/2 + 0.5
p_ = list(map(calc_ex,p_))

res = sum(p_[:k])
cnt = sum(p_[:k])
for i in range(1,n-k+1):
    cnt = cnt - p_[i-1] + p_[i+k-1]
    res = max(res,cnt)
print(res)
import math
r=int(input())
print(r**2*math.pi,r*2*math.pi)

### FIXED CODE ###

import math
r=float(input())
print(r**2*math.pi,r*2*math.pi)
x, n = map(int, input().split())
p = list(map(int, input().split()))

res = []
for i in range(1, 101):
    if i not in p:
        res.append([abs(i-x), i])

res.sort(key=lambda x:x[0])
print(res[0][1])



### FIXED CODE ###

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

ans = 0
m = float("inf")
for i in range(-200, 200):
    if i not in p:
        if abs(i-x) < m:
            ans = i
            m = abs(i-x)

print(ans)
{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "g\n",
      "a\n"
     ]
    }
   ],
   "source": [
    "A='ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "a='abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "n=input()\n",
    "\n",
    "if n in A:\n",
    "    print(\"A\")\n",
    "\n",
    "if n in a:\n",
    "    print(\"a\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}


### FIXED CODE ###

A='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
a='abcdefghijklmnopqrstuvwxyz'

n=input()

if n in A:
    print("A")

if n in a:
    print("a")
A, B, X = int(input())

if A <= X <= (A+B):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

if A <= X <= (A+B):
    print('YES')
else:
    print('NO')
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 14:42:43 2018

@author: maezawa
"""

def print_array(g):
    ans = str(g[0])
    if len(g) > 1:
        for i in range(1,len(g)):
            ans += ' '+str(g[i]) 
    print(ans)

name=[]
time=[]
current_time = 0

n, q = list(map(int, input().split()))
for i in range(n):
    s = input().split()
    name.append(s[0])
    time.append(int(s[1]))
# =============================================================================
# print(n,q)
# print(name)
# print(time)
# =============================================================================
finished = []
fin_time = []
i=0
remain = n
while True:
    if time[i] <= q:
        current_time += time.pop(i)
        finished.append(name.pop(i))
        fin_time.append(current_time)      
        remain -= 1
        i = i%remain
        if remain == 0:
            break
    else:
        time[i] -= q
        current_time += q
        i = (i+1)%remain

for i in range(n):
    print("{} {}".format(finished[i], fin_time[i]))
        
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 18:04:22 2018
ALDS1_3b_r リングバッファによる実装
@author: maezawa
"""

def fifo_enque(data):
    global tail
    global fifo
    fifo[tail] = data
    tail = (tail+1)%fifo_size
    
def fifo_deque():
    global head
    global fifo
    data = fifo[head]
    head = (head+1)%fifo_size
    return data

fifo_size = 100000
fifo = [0 for _ in range(fifo_size)]
head = 0
tail = 0

n, q = list(map(int, input().split()))
for i in range(n):
    s = input().split()
    data = [s[0], int(s[1])]
    fifo_enque(data)
    
current_time = 0
finished = []
fin_time = []

while True:
    data = fifo_deque()
    if data[1] > q:
        current_time += q
        data[1] -= q
        fifo_enque(data)
    else:
        current_time += data[1]
        finished.append(data[0])
        fin_time.append(current_time)
    if head == tail:
        break

for i in range(n):
    print("{} {}".format(finished[i], fin_time[i]))
a, b = map(int, input().split())
kuchi = 1
cnt = 0
if kuchi >= b:
    break
else:
    for i in range(1, 20):
        if kuchi >= b:
                break
        else:
            for j in range(1, a ** i):
                if kuchi >= b:
                    break
                else:
                    if j < a ** i:
                        cnt += 1
                        kuchi = kuchi - 1 + a
                    else:
                        kuchi = kuchi * a
                        cnt += kuchi / a 
print(cnt)

### FIXED CODE ###

a, b = map(int, input().split())
kuchi =  1
cnt = 0
if kuchi <= b:
    for i in range(1, 20):
        if kuchi >= b:
                break
        else:
            for j in range(1, a ** i):
                if kuchi >= b:
                    break
                else:
                    if j < a ** i:
                        cnt += 1
                        kuchi = kuchi - 1 + a
                    else:
                        kuchi = kuchi * a
                        cnt += kuchi / a 
print(cnt)
N,M,X,Y = map(int, input().split())
num_list = [list(map(int, input().split())) for _ in range(M)]

Z = list(range(X+1,Y+1))

for z in Z:
    if max(num_list[0]) < z and min(num_list[1]) >= z:
        print('No War')
        break
    if z == Z[-1]:
        print('War')

### FIXED CODE ###

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

num = sorted([A,B,C],reverse=True)
print(eval(str(num[0])+str(num[1])+'+'+str(num[2])))
import math

n= int(input())
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

res  = []
if is_prime(n):
    res = n - 1
else:
    for t in range(1, int(math.sqrt(n)) + 1):
        if n % t == 0:
                res.append(n//t + t - 2)


print(min(res))


### FIXED CODE ###

import math

n= int(input())
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

i, j = 10**12, 10**12
res  = 0
if is_prime(n):
    res = n - 1
else:
    for t in range(1, int(math.sqrt(n)) + 1):
        if n % t == 0:
            a, b = t, n//t
            if a + b < i + j:
                i, j = a, b
    res = i + j -2


print(res)
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
class Combination:
    """
    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

n,m,k = inpl()
conb = Combination(100010)
res = 0
for i in range(k+1):
    x = n - i - 1
    res += conb(n-1,x) * m * pow(m-1,x,mod)
    res %= mod
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
class Combination:
    """
    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

n,m,k = inpl()
conb = Combination(300010)
res = 0
for i in range(k+1):
    x = n - i - 1
    res += conb(n-1,x) * m * pow(m-1,x,mod)
    res %= mod
print(res)
import math

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

x = [X] + list(map(int, input().split()))
x.sort()

dic = []

for i in range(1, len(x)):
    tmp = x[i] - x[i - 1]
    if tmp not in dic:
        dic.append(tmp)

ans = max(dic)

for i in range(1, len(dic)):
    ans = min(ans, math.gcd(dic[i], dic[i - 1]))

print(ans)

### FIXED CODE ###

import fractions

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

x = [X] + list(map(int, input().split()))
x.sort()

dic = []

for i in range(len(x) - 1):
    tmp = x[i + 1] - x[i]
    if tmp not in dic:
        dic.append(tmp)

ans = max(dic)

for i in range(len(dic) - 1):
    ans = min(ans, fractions.gcd(dic[i], dic[i + 1]))

print(ans)