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

from pprint import pprint

INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    #print(wsmap(y, x))
                    #print("--")
                    #print("y, x {0}, {1}".format(ny, nx))
                    #print(wsmap(ny, nx))
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
#print(dp)
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)




### FIXED CODE ###

from pprint import pprint

INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    #print(wsmap(y, x))
                    #print("--")
                    #print("y, x {0}, {1}".format(ny, nx))
                    #print(wsmap(ny, nx))
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
#print(dp)
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)
### BUGGY CODE ###

import fractions
import operator
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=0):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        """
        # size 以上である最小の 2 冪
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._tree = [default for _ in range(self._size * 2 - 1)]
        self._fn = fn

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


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

st = SegmentTree(size=N, fn=fractions.gcd, default=0)
for i, a in enumerate(A):
    st.set(i, a)

ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(st.get(0, i) or 0, st.get(i + 1, N) or 0))
print(ans)


### FIXED CODE ###

import sys
import math
import fractions

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


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


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')


N = inp()
A = inl()

ans = set()
ans.add(A[1])
gcd = A[0]
for i, a in enumerate(A):
    if i == 0:
        continue

    news = set()
    for ss in ans:
        news.add(fractions.gcd(ss, a))
    ans = news

    new_gcd = fractions.gcd(gcd, a)
    if new_gcd < gcd:
        ans.add(gcd)
    gcd = new_gcd

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

N=int(input())
m=N+1
for j in range(2,N//2+1):
  if N%j==0:
    a=j
    b=N//j
    if a>b:
      break
    else:
      m=min(m,(a+b))

print(m-2)

### FIXED CODE ###

import math
N=int(input())
m=N+1
for j in range(2,int(math.sqrt(N))+1):
    if N%j==0:
        a=j
        b=N//j
        if a>b:
            break
        else:
            m=min(m,(a+b))

print(m-2)
### BUGGY CODE ###

S = input()
S_li = list(S)
count = 0
flag = False
i = 0
while True:
  if i == len(S_li) or len(S_li) == 0:
    break
  if S_li[i-1] == "0" and S_li[i] == "1" and i-1 >= 0:
    flag = True
  elif S_li[i-1] == "1" and S_li[i] == "0" and i-1 >= 0:
    flag = True
  if flag == True:
    del S_li[i-1:i+1]
    count += 2
    i = 0
    flag = False
  else:
    i += 1
print(count)

### FIXED CODE ###

S = str(input())
count_0 = 0
count_1 = 0
for i in range(len(S)):
  if int(S[i]) == 0:
    count_0 += 1
  else:
    count_1 += 1
print((min(count_0,count_1))*2)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    INF = 10**15
    N, M = map(int, input().split())
    heap = []
    for _ in range(M):
        l, r, c = map(int, input().split())
        heappush(heap, (l-1, r-1, c))
    
    dp = [INF]*N
    dp[0] = 0
    while heap:
        l, r, c = heappop(heap)
        
        s = min(dp[l:r])
        dp[r] = min(dp[r], s+c)
        
    if dp[N-1] == INF:
        return -1
    
    return dp[N-1]

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
from heapq import heappop, heappush, heapify

def dijkstra(s, t, links):
    """Dijkstra algorism
    s: int, start node.
    t: int, target node.
    links: iterable, link infomation.
           links[i] contains edges from node i: (cost, target_node).

    return int, minimal cost from s node to t node.
    """
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while len(heap) > 0:
        cost, node = heappop(heap)
        if node == t:
            return cost

        if node in visited:
            continue

        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 in visited:
                continue

            heappush(heap, (cost + cost2, node2))

    return -1

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    links = [[] for _ in range(N)]
    for i in range(1, N):
        links[i].append((0, i-1))

    for _ in range(M):
        l, r, c = map(int, input().split())
        links[l-1].append((c, r-1))
    
    return dijkstra(0, N-1, links)
    

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

N, K = map(int, input().split())
P = [int(p) - 1 for p in input().split()]
C = list(map(int, input().split()))

max_score = -10**9
for i in range(N):
    memo = [P[i]]
    score = C[P[i]]
    move = 1
    max_score = max(score, max_score)

    while move < K and P[memo[-1]] not in memo:
        memo.append(P[memo[-1]])
        score += C[memo[-1]]
        move += 1
        max_score = max(score, max_score)

    if move < K and score > 0:
        score = (K // move) * score
        move *= (K // move)
        max_score = max(score, max_score)

        cur = i
        while move < K:
            cur = P[cur]
            score += C[cur]
            move += 1
            max_score = max(score, max_score)

print(max_score)

### FIXED CODE ###

N, K = map(int, input().split())
P = [int(p) - 1 for p in input().split()]
C = list(map(int, input().split()))

max_score = -10 ** 9
for i in range(N):
    memo = set()
    score = 0
    cur = i
    move = 0

    while move < K and P[cur] not in memo:
        cur = P[cur]
        memo.add(cur)
        score += C[cur]
        move += 1
        max_score = max(score, max_score)

    if move < K and score > 0:
        score = max(K // move - 1, 1) * score
        move *= max(K // move - 1, 1)
        max_score = max(score, max_score)

        cur = i
        while move < K:
            cur = P[cur]
            score += C[cur]
            move += 1
            max_score = max(score, max_score)

print(max_score)
### BUGGY CODE ###

def main():
	N, M = map(int, input().split())
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue.pop(0)
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
	print(-1)

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	N, M = map(int, input().split())
	INF = 2*31-1
	to = [[] for _ in range(N)]
	for _ in range(M):
		u, v = map(int, input().split())
		to[u-1].append(v-1)
	dist = [[INF, INF, INF] for _ in range(N)]

	S, T = map(int, input().split())
	queue = []
	for pos in to[S-1]:
		queue.append([pos, 1])
		dist[pos][1] = 1
	while queue:
		pos, l = queue.pop(0)
		next_positions = to[pos]
		for next_pos in next_positions:
			nl = (l+1)%3
			if dist[next_pos][nl] != INF:
				continue
			dist[next_pos][nl] = dist[pos][l]+1
			queue.append([next_pos, nl])
	ans = dist[T-1][0]
	if ans == INF:
		print(-1)
	else:
		print(ans//3)

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

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

tmp=1;
for i in range(n):
    tmp*=a[i]

if tmp>1000000000000000000:
    print(-1)
else:
    print(tmp)



### FIXED CODE ###

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

ans=1

if 0 in a:
    print(0)
    exit()

for i in a:
   ans*=i
   if ans>10**18:
    print(-1)
    exit()


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

s=list(map(ord,list(input())))

c=0
for i in range(len(s)):
    if s[i:i+3]==[65,66,67]:
        j=1
        ci=1
        while s[i-j]==65:
            ci+=1
            j+=1
            if i-j<0:
                break
        s[i-j+1]=66
        s[i-j+2]=67
        s[i-j+3:i+3]=[65 for i in range(j)]
        c+=ci        

print(c)


### FIXED CODE ###

s=input()

s=s.replace("BC","D")

count=0

c=0
while c<len(s):
    if s[c]=="A" or s[c]=="D":
        d=c
        while s[d]=="A" or s[d]=="D":
            d+=1
            if d==len(s):
                break
        an=0
        for i in range(c,d):
            if s[i]=="A":
                an+=1
            else:
                count+=an
        c=d
    else:
        c+=1

print(count)
### BUGGY CODE ###

s = input()
q_ = int(input())
query = [input().split() for _ in range(q_)]

for q in query:
    if q[0] == '1':
        s = s[::-1]
    elif q[0] == '2':
        if q[1] == '1':
            s = q[2] + s
        else:
            s = s + q[2]

print(s)

### FIXED CODE ###

from collections import deque
import copy
s = input()
q_ = int(input())
query = [input().split() for _ in range(q_)]
l = deque(s)
flag = 0

for q in query:
    if q[0] == '1':
        flag += 1
        continue
    elif q[0] == '2':
        if (int(q[1]) + flag) % 2 == 1:
            l.appendleft(q[2])
        else:
            l.append(q[2])

if flag % 2 == 1:
    l.reverse()

print(''.join(l))
### BUGGY CODE ###

from collections import Counter
N = int(input())
cnt = 0
for i in range(1, N+1, 2):
    c = Counter(str(i))
    if len(c) == 3 and '7' in c and '5' in c and '3' in c:
        # print(c)
        cnt += 1
print(cnt)


### FIXED CODE ###

from collections import deque
N = int(input())
memo = {i:1 for i in [357, 375, 537, 573, 735, 753]}
ans = 0
queue = deque()
mod = [10**i for i in range(10)]
for key in memo.keys():
  if key <= N:
    ans += 1
    queue.append(key)
while queue:
    key = queue.popleft()
    len_key = len(str(key))
    for i in range(len_key):
        for j in [3,5,7]:
            tmp = (key // mod[i]) * mod[i+1] + j * mod[i] + key % mod[i]
            if tmp not in memo and tmp <= N:
                ans += 1
                memo[tmp] = 1
                queue.append(tmp)
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    for i in range(N//2, 0, -1):
        if N-i*2 == 0:
            tmp = S[i:]
            if tmp.find(S[:i]) != -1:
                print(i)
                exit()
        else:
            for index in range(N-i*2):
                # 仮の文字列の生成
                tmp = S[index+i:]
                if tmp.find(S[index:index+i]) != -1:
                    print(i)
                    exit()

    print('0')


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)
### BUGGY CODE ###

from itertools import combinations
from decimal import Decimal

def expectval(num):
    up = [Decimal(str(n)) for n in range(1, num+1)]
    return sum(up) / Decimal(str(num))

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

ans = Decimal("-1")
for idx in range(len(l)):
    comb = l[idx:idx+k]
    _sum = sum(map(expectval, comb))
    if _sum > ans:
        ans = _sum

print("{:.12f}".format(ans))



### FIXED CODE ###

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

sums = [0 for _ in range(n+1)]
for i in range(n):
    exp = (1 + l[i]) / 2
    sums[i+1] = sums[i] + exp

ans = 0
for idx in range(n-k+1):
    diff = sums[idx+k] - sums[idx]
    ans = max(ans, diff)

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

n=int(input())
l=list(map(int,input().split(' ')))
c=0
for i in l:
    c+=l.count(i)
if(c<=len(l)):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split(' ')))
l.sort()
c=0
for i in range(len(l)-1):
    if(l[i]==l[i+1]):
        c=1 
        break
if(c==0):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N, M = map(int, input().split())
c = [tuple(map(int, input().split())) for _ in range(M)]
nums = []
for i in range(0, M):
    mi = list(range(c[i][0], c[i][1]+1))
    nums.append(mi)
ans = set(nums[0])
dim = nums[1:]
print(len(ans.intersection(*dim)))

### FIXED CODE ###

N, M = map(int, input().split())
c = [tuple(map(int, input().split())) for _ in range(M)]
right = N
left = 1
for i in range(0, M):
    left = max(left, c[i][0])
    right = min(right, c[i][1])
print(len(range(left, right+1)))
### BUGGY CODE ###

k,s=map(int,input().split())
print([x+y+z for z in range(k+1) for y in range(k+1) for x in range(k+1)].count(s))

### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

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

cnt = 0
s = 0

while True:
    for i in range(n):
        if s == 0:
            if li[i] % 2 == 0:
                li[i] //= 2
                s = 1
            else:
                li[i] *= 3
        else:
            li[i] *= 3
    else:
        if s == 0:
            break
        s = 0
        cnt += 1
        
print(cnt)

### FIXED CODE ###

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

cnt = 0
t = 0

while True:
    for i in range(t,n):
        if li[i] % 2 == 0:
            li[i] //= 2
            t = i
            cnt += 1
            break
    else:
        break

print(cnt)
### BUGGY CODE ###

from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

def solve():
  H,W = map(int,input().split())
  C_h,C_w = map(lambda x:int(x)-1,input().split())
  D_h,D_w = map(lambda x:int(x)-1,input().split())
  S = [readline() for _ in range(H)]

  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  move_b = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

  while len(deq):
    h,w = deq.popleft()
    if seen[h][w]:
      continue
      seen[h][w] = True
    for dh,dw in move_a:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]:
        dist[nh][nw] = dist[h][w]
        deq.appendleft((nh,nw))
    for dh,dw in move_b:
      nh,nw = h+dh,w+dw
      if nh>=0 and nw>=0 and nh<H and nw<W and S[nh][nw]!='#' and dist[nh][nw] > dist[h][w]+1:
        dist[nh][nw] = dist[h][w]+1
        deq.append((nh,nw))

  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
solve()

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=mod-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
  n,m,k=LI()
  ans=0
  col=m
  for x in range(n)[::-1]:
    now=col
    now*=com(n-1,x)
    if x<=k:
      ans+=now
      ans%=mod
    col*=m-1
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
  n,m,k=LI()
  res=0
  tmp=m*pow(m-1,n-k-1,mod)
   
  for r in range(n-k-1,n):
    res=(res+tmp*com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res

# main()
print(main())
### BUGGY CODE ###

L, R = map(int, input().split())
results = []
for i in range(L, R):
    for j in range(i+1,R+1):
        results.append((i*j)%2019)
print(min(results))

### FIXED CODE ###

L, R = map(int, input().split())
diff = R-L
for n in range(1):
    if diff > 2019:
        ret = 0
        break
        
        [inner for outer in init for inner in outer]
    ret = min([ (i*j)%2019 for i in range(L, R) for j in range(i+1,R+1) ])
print(ret)
### BUGGY CODE ###

from operator import sub
 
N = int(input())
data = list(map(int, input().split()))
step = N * (N+1) // 2
total = sum(data)
#print("-->", total, step)
if total % step:
  print("NO")
else:
  K = total // step
  #print("-->", total, step, K)
  datar = [data[i % N] for i in range(-1, N)] 
  delta = list(map(sub, datar[1:], datar))
  #print(*delta)
  #print("-->", *list(map(lambda x:(K-x) % N, delta)))
  #print("-->", *list(map(lambda x:(K-x) // N, delta)))
  if any(map(lambda x:(K-x) % N, delta)):
    print("NO")
  else:    
    ops = list(map(lambda x:(K-x) // N, delta))
    if sum(ops) == K:
      for i, v in enumerate(data):
        if (i & 1):
          vv = sum([ops[(i-k) % N] * (k+1) for k in range(N)])
          if v != vv:        
            print("NO")
            break
      else:    
        print("YES")
    else:
      print("NO")

### FIXED CODE ###

from operator import sub

N = int(input())
data = list(map(int, input().split()))
step = N * (N+1) // 2
total = sum(data)
#print("-->", total, step)
if total % step:
  print("NO")
else:
  K = total // step
  #print("-->", total, step, K)
  datar = [data[i % N] for i in range(-1, N)] 
  delta = list(map(sub, datar[1:], datar))
  #print(*delta)
  #print("-->", *list(map(lambda x:(K-x) % N, delta)))
  #print("-->", *list(map(lambda x:(K-x) // N, delta)))
  if any(map(lambda x:(K-x) % N, delta)):
    print("NO")
  elif any(map(lambda x: K-x < 0, delta)): 
    print("NO")
  else:    
    ops = list(map(lambda x:(K-x) // N, delta))
    if sum(ops) == K:
      for i, v in enumerate(data[0:1]):
        vv = sum([ops[(i-k) % N] * (k+1) for k in range(N)])
        if v != vv:        
          print("NO")
          break
      else:    
        print("YES")
    else:
      print("NO")