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

import numpy
import fractions

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

g = fractions.gcd(A, B)
d = []
p = []

for i in range(1,int(numpy.sqrt(g))+1):
    if g % i == 0:
        d.append(i)
        if i != g//i:
           d.append(g//i)

for i in d:
    s = 0
    for j in range(1,int(numpy.sqrt(i))+1):
        if i % j == 0:
            s += 1

    if s == 1:
        p.append(i)

print(len(p))


### FIXED CODE ###

import fractions

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

g = fractions.gcd(A, B)
d = []
p = []

for i in range(1,int(pow(g, 0.5))+1):
    if g % i == 0:
        d.append(i)
        if i != g//i:
           d.append(g//i)

for i in d:
    s = 0
    for j in range(1,int(pow(i, 0.5))+1):
        if i % j == 0:
            s += 1

    if s == 1:
        p.append(i)

print(len(p))
### BUGGY CODE ###

N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
D.sort()
def find(a, i):
    l = 0
    r = len(a)-1
    mid = (l+r)//2
    while l <= r:
        if i == a[mid]:
            return mid
        elif i < a[mid]:
            r = mid - 1
        else:
            l = mid + 1
        mid = (l+r)//2
    return -1

for i in range(M):
    j = find(D, T[i])
    if j == -1:
        print("NO")
        exit(0)
    D.pop(j)
print("YES")
    


### FIXED CODE ###

from collections import defaultdict
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
dic = defaultdict(int)
for d in D:
    dic[d] += 1
def find(a, i):
    l = 0
    r = len(a)-1
    mid = (l+r)//2
    while l <= r:
        if i == a[mid]:
            return mid
        elif i < a[mid]:
            r = mid - 1
        else:
            l = mid + 1
        mid = (l+r)//2
    return -1
keys = list(dic.keys())
keys.sort()
for i in range(M):
    j = find(keys, T[i])
    if j == -1 or dic[keys[j]] == 0:
        print("NO")
        exit(0)
    dic[keys[j]] -= 1
print("YES")
### BUGGY CODE ###

import numpy as np
a,b,n=map(int, input().split())
c = np.array([])
for x in range(n+1) :
     c = np.append(c,int(a*x/b)-a* int(x/b))
    
print(int(np.max(c)))

### FIXED CODE ###

a,b,n = map(int, input().split())
x = min(b-1,n)
print(int(a*x/b))
### BUGGY CODE ###

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

sum = 0
for i in range(0,n-1):
    k=i+1
    for j in range(k,n):
        sum  += a[i]^a[j]
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  ones = 0
  for i in A:
    if i>>j & 1:
      ones += 1
  ans += 2**j*((n-ones)*ones)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

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

for i in range(M):
	b, c = map(int, input().split())
	A.extend([c]*b)
A.sort(reverse=True)
B = A[0:N]
print(sum(B))


### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = [(-i, 1) for i in A]
heapq.heapify(a)

for i in range(M):
	b, c = map(int, input().split())
	heapq.heappush(a, (-c, b))
	
ans = 0

for i in range(N):
	pop = heapq.heappop(a)
	ans += pop[0]
	if pop[1] != 1:
		heapq.heappush(a, (pop[0], pop[1] - 1))

ans *= -1
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
while '0' in s and '1' in s:
    s = s.replace('01', '')
    s = s.replace('10', '')
    s = s.replace('01', '')
print(n - len(s))

### FIXED CODE ###

s = input()
a = s.count('0')
b = s.count('1')
print(a + b - abs(a - b))
### BUGGY CODE ###

n, m = map(int, input().split())
li_q = list()
for i in range(m):
    li_q.append(tuple(input().split()))

ac_count = 0
wa_count = 0

for v in range(1, n +1):
    if (str(v), 'AC') in li_q:
        ac_count += 1
        ac_idx = li_q.index((str(v), 'AC'))
        wa_count += li_q[:ac_idx].count((str(v), 'WA'))

print(ac_count, wa_count)


### FIXED CODE ###

n, m = map(int, input().split())
li_q = list()
for i in range(m):
    li_q.append(tuple(input().split()))

ac_count = 0
wa_count = 0

s_ac = set()
d_wa = dict()
for l in li_q:
    if l[1] == 'AC':
        if l[0] not in s_ac:
            s_ac.add(l[0])
            ac_count += 1
            wa_count += d_wa.get(l[0], 0)
        else:
            pass
    elif l[1] == 'WA':
        d_wa[l[0]] = d_wa.get(l[0], 0) + 1

print(ac_count, wa_count)
### BUGGY CODE ###

import sys

s = sys.stdin.readlines()

N,C = map(int,s[0].split())
XV = [[int(j) for j in s[i+1].split()] for i in range(N)]
ans = 0


Sum_left = [[0]*(N+1) for _ in range(N+1)]

for j in range(N):
    if j == 0:
        Sum_left[0][j+1] = Sum_left[0][j] + XV[j][1] - XV[j][0]
    else:
        Sum_left[0][j+1] = Sum_left[0][j] + XV[j][1] - (XV[j][0] - XV[j-1][0])
    ans = max(ans,Sum_left[0][j+1])

for i in range(N):
    if i == 0:
        Sum_left[i+1][0] = Sum_left[i][0] + XV[-i-1][1] - 2 * (C - XV[-i-1][0])
    else:
        Sum_left[i+1][0] = Sum_left[i][0] + XV[-i-1][1] - 2 * (XV[-i][0] - XV[-i-1][0])

for i in range(1,N):
    for j in range(1,N+1-i):
        Sum_left[i][j] = Sum_left[i][0] + Sum_left[0][j]
        ans = max(ans,Sum_left[i][j])



Sum_right = [[0]*(N+1) for _ in range(N+1)]

for j in range(N):
    if j == 0:
        Sum_right[0][j+1] = Sum_right[0][j] + XV[-1-j][1] - (C-XV[-1-j][0])
    else:
        Sum_right[0][j+1] = Sum_right[0][j] + XV[-1-j][1] - (XV[-j][0] - XV[-1-j][0])
    ans = max(ans,Sum_right[0][j+1])

for i in range(N):
    if i == 0:
        Sum_right[i+1][0] = Sum_right[i][0] + XV[i][1] - 2 * XV[i][0]
    else:
        Sum_right[i+1][0] = Sum_right[i][0] + XV[i][1] - 2 * (XV[i][0] - XV[i-1][0])

for i in range(1,N):
    for j in range(1,N+1-i):
        Sum_right[i][j] = Sum_right[i][0] + Sum_right[0][j]
        ans = max(ans,Sum_right[i][j])

print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
XV = [[0,0]] + [[int(i) for i in input().split()] for _ in range(N)] + [[C,0]]

Sum_left = [0] * (N+1)
Sum_right = [0] * (N+1)
for i in range(N):
    Sum_left[i+1] = Sum_left[i] + XV[i+1][1]
    Sum_right[i+1] = Sum_right[i] + XV[N-i][1]

Sum_right_maxA = [0] * (N+1)
Sum_right_maxB = [0] * (N+1)
for i in range(1,N+1):
    Sum_right_maxA[i] = max(Sum_right_maxA[i-1], Sum_right[i] - 2 * (C - XV[N+1-i][0]))
    Sum_right_maxB[i] = max(Sum_right_maxB[i-1], Sum_right[i] - (C - XV[N+1-i][0]))

ans = 0
for i in range(N+1):
    ans = max(ans, Sum_left[i] + Sum_right_maxA[N-i] - XV[i][0], Sum_left[i] + Sum_right_maxB[N-i] - 2*XV[i][0])
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
q=int(input())
dic=dict()
for i,j in enumerate("qwertyuioplkjhgfdsazxcvbnm"):
    dic[j]=i
No=2
while n>No:
    No*=2
tree=[set()]*(2*No)
def add(k,x):
    k+=No-1
    tree[k]=set([dic[x]])
    while k>0:
        k=(k-1)//2
        tree[k]=tree[2*k+1]|tree[2*k+2]
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=set()
    while L<=R:
        if R&1:
            s|=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s|=tree[L]
        L>>=1;R>>=1
    return len(s)
for i,j in enumerate(s):
    add(i,j)
for i in range(q):
    a,b,c=input().split()
    a,b=int(a),int(b)
    if a==1:
        add(b-1,c)
    if a==2:
        c=int(c)
        print(query(b-1,c-1))

### FIXED CODE ###

n=int(input())
s=input()
q=int(input())
dic=dict()
for i,j in enumerate("qwertyuioplkjhgfdsazxcvbnm"):
    dic[j]=i
No=2
while n>No:
    No*=2
tree=[set()]*(2*No)
def add(k,x):
    k+=No-1
    tree[k]=set([dic[x]])
    while k>0:
        k=(k-1)//2
        tree[k]=tree[2*k+1]|tree[2*k+2]
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=set()
    while L<=R:
        if R&1:
            s|=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s|=tree[L]
        L>>=1;R>>=1
    return len(s)
for i,j in enumerate(s):
    tree[i+No-1]=set([dic[j]])
for i in range(No-2,-1,-1):
    tree[i]=tree[2*i+1]|tree[2*i+2]
for i in range(q):
    a,b,c=input().split()
    a,b=int(a),int(b)
    if a==1:
        add(b-1,c)
    if a==2:
        c=int(c)
        print(query(b-1,c-1))
### BUGGY CODE ###

from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

start = []
for i in range(h):
    for j in range(w):
        if MAZE[i][j] == ".":
            start.append((i, j))


# BFS
def bfs(start):
    i, j = start
    INF = 10**18
    dist = [[INF] * w for _ in range(h)]
    dist[i][j] = 0
    next_v = deque([start])
    visited = set()
    while next_v:
        i, j = next_v.popleft()
        direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in direction:
            x, y = i+di, j+dj
            if MAZE[x][y] == "#":
                continue
            if (x, y) in visited:
                continue
            dist[x][y] = dist[i][j] + 1
            visited.add((i, j))
            next_v.append((x, y))
    return dist


ans = 0
for s1 in start:
    r = bfs(s1)
    for s2 in start:
        ans = max(ans, r[s2[0]][s2[1]])

print(ans)


### FIXED CODE ###

from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

# 全通りのstart位置から探索する
start = []
for i in range(h):
    for j in range(w):
        if MAZE[i][j] == ".":
            start.append((i, j))


INF = 10**18


def bfs(start):
    i, j = start
    dist = [[INF] * w for _ in range(h)]
    dist[i][j] = 0
    next_v = deque([start])
    while next_v:
        i, j = next_v.popleft()
        direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in direction:
            x, y = i+di, j+dj
            if MAZE[x][y] == "#":
                continue
            if dist[x][y] <= dist[i][j] + 1:
                continue
            dist[x][y] = dist[i][j] + 1
            next_v.append((x, y))
    return dist


ans = 0
for ls1 in start:
    r = bfs(ls1)
    for ls2 in start:
        ans = max(ans, r[ls2[0]][ls2[1]])

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

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

sum = 0

for i in range(N):
    for j in range(N - i - 1):
        sum += A[i] * A[N -1 - j]

print(sum % (1000000007))


### FIXED CODE ###

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

mod = 10 ** 9 + 7
sum = sum(A) **  2

squ = 0
for i in range(N):
    squ +=  A[i] ** 2

answer = int(((sum - squ)  //  2 ) % mod)
print(answer)
### BUGGY CODE ###

import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

heapq.heapify(cost)
nn,l = heapq.heappop(cost)
for i in range(n):
    while l <= i:
        nn,l = heapq.heappop(cost)
    print(10 ** 15 - nn)


### FIXED CODE ###

import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    graph_a[u].append((a, v))
    graph_a[v].append((a, u))
    graph_b[u].append((b, v))
    graph_b[v].append((b, u))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)
### BUGGY CODE ###

import sys
BIG = 10**9 + 7
def sumpp(n,a):
    acc = 0
    for i in range(n-1):
        for j in range(i+1,n):
            acc += a[i] * a[j]

    return acc % BIG
input = sys.stdin.readline
if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    print(sumpp(n,a))
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
BIG = 10**9 + 7

def sumpp(n,a):
    acc = 0
    tmp = 0
    sumv = sum(a)
    for i in range(n):
        tmp += a[i]
        acc += a[i] * (sumv - tmp)
    return acc % BIG

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    print(sumpp(n,a))
### BUGGY CODE ###

def main():
    s=input()
    cnt=0
    for i in range(len(s)+1):
        for j in range(i+1,len(s)+1):
            if int(s[i:j])%2019 == 0:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s=list(input())[::-1]
    ans,tot,x,m=0,0,1,2019
    cnt=[0]*m
    n=len(s)
    for i in range(n):
        cnt[tot] += 1
        tot += int(s[i])*x
        tot %= m
        ans += cnt[tot]
        x = x*10%m
    print(ans)

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

def main():
    K = int(input())

    lunlun_number_memo = {}

    # def is_lunlun(str_n):
    #     while True:
    #         if lunlun_number_memo.get(str_n):
    #             return True
    #         elif len(str_n) == 1:
    #             return True
    #         else:
    #             if abs(int(str_n[0]) - int(str_n[1])) <= 1:
    #                 str_n = str_n[1:]
    #             else:
    #                 return False


    lunlun_number_count = 0
    i = 0
    while lunlun_number_count < K:
        i += 1
        # if is_lunlun(str(i)):
        str_i = str(i)
        while True:
            if lunlun_number_memo.get(str_i) or len(str_i) == 1:
                lunlun_number_memo[str(i)] = True
                lunlun_number_count += 1
            else:
                if abs(int(str_i[0]) - int(str_i[1])) <= 1:
                    str_i = str_i[1:]
                else:
                    break

            # print(i)
            # print(lunlun_number_count)
            # print("running")

    print(i)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import queue

def main():
    K = int(input())
    q = queue.Queue()
    for i in range(1, 10):
        q.put(i)

    i = 0
    while True:
        i += 1

        n = q.get()
        center_num = (10 * n) + (n % 10)
        
        if n % 10 != 0:
            q.put(center_num - 1)
        
        q.put(center_num)

        if n % 10 != 9:
            q.put(center_num + 1)

        if i >= K:
            # print(q.queue)
            print(n)
            sys.exit()

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

import sys
#return arr
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

if not 2 in cf_list:
  print(1)
  sys.exit()
ans = [2]
for i in range(1, len(cf_list)):
  flg = True
  for a in ans:
    if cf_list[i] % a == 0:
      flg = False
      break
  if flg:
    ans.append(cf_list[i])
print(len(ans)+1)

### FIXED CODE ###

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
a, b = map(int, input().split())
a_list = prime_factorize(a)
b_list = prime_factorize(b)
a_set = set(a_list)
b_set = set(b_list)

ans_set = a_set & b_set
ans_set.add(1)
print(len(ans_set))
### BUGGY CODE ###

from collections import deque

def main():
    K = int(input())
    if K <= 9:
        print(K)

    que = deque(range(1,10))
    # print(que)
    cnt = 9
    while True:
        x = que.popleft()
        mod = x % 10

        if mod != 0:
            que.append(10 * x + mod - 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

        que.append(10 * x + mod)
        # print(que)
        cnt += 1
        if cnt == K:
            print(que[-1])
            return

        if mod != 9:
            que.append(10 * x + mod + 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

main()


### FIXED CODE ###

from collections import deque

def main():
    K = int(input())
    if K <= 9:
        print(K)
        return

    que = deque(range(1,10))
    # print(que)
    cnt = 9
    while True:
        x = que.popleft()
        mod = x % 10

        if mod != 0:
            que.append(10 * x + mod - 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

        que.append(10 * x + mod)
        # print(que)
        cnt += 1
        if cnt == K:
            print(que[-1])
            return

        if mod != 9:
            que.append(10 * x + mod + 1)
            # print(que)
            cnt += 1
            if cnt == K:
                print(que[-1])
                return

main()
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
for f in range(k):
    a1=[0]*(n+1)
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if a==[n]*n:
        break
for i in range(n):
    print(a[i])

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

n, m, k = input().split()
a = input().split()
b = input().split()

n = int(n)
m = int(m)
k = int(k)
a = list(map(int, a))
b = list(map(int, b))

ans = 0
temp_a = {}
temp_b = {}

for i_a in range(n+1):
  temp_a[i_a] = sum(a[0:i_a])
for i_b in range(m+1):
  temp_b[i_b] = sum(b[0:i_b])
  
temp_a = sorted(temp_a.items(), key=lambda x:x[1], reverse=True)
temp_b = sorted(temp_b.items(), key=lambda x:x[1], reverse=True)
ans = {}

for item_a in temp_a:
  for item_b in temp_b:
    if item_a[1] + item_b[1] > k:
      continue
    else:
      ans[len(ans)] = item_a[0] + item_b[0]
      break

ans = max(ans.values())
print(ans)


### FIXED CODE ###

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, j = 0, m

for i in range(n+1):
  if a[i] > k:
    break
  while a[i] + b[j] > k:
    j -= 1
  ans = max(ans, i+j)

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

import math
from functools import reduce
K = int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)
count = 0
for i in range(K):
  for j in range(K):
    for k in range(K):
      count += gcd(i+1,j+1,k+1)
      
print(count)

### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(K):
  for j in range(K):
    x = math.gcd(i+1,j+1)
    for k in range(K):
      count += math.gcd(x,k+1)    
print(count)
### BUGGY CODE ###

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


if X != Y:       
    for i in range(X, 10**18,X):
        if (i != X) and (i % Y != 0):
            print(i)
            break
else:
    print(-1)

### FIXED CODE ###

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


if X % Y != 0:
    print(X)
else:
    print(-1)
### BUGGY CODE ###

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

ways = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                ways += 1

print(ways)

### FIXED CODE ###

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

ways = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i - j
        if k >= 0 and k <= K:
            ways += 1

print(ways)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353
# Combination under a prime modulo: nCk % p
def combmod(n, k, p):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


def solve():
    ans = 0
    for i in range(K + 1):
        ans += (combmod(N - 1, i, MOD) * M) % MOD * pow(M - 1, N - 1 - i, MOD)
        ans %= MOD
    return ans


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) * pow(i + 1, MOD - 2, MOD)
        cs %= MOD
    return ans


if __name__ == "__main__":
    print(solve())