Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys

def maybe_check(n,A):
    try:
        if n <= 0 or n >= 10000:
            raise

        if len(A) <= 0 or len(A) > n:
            raise

        div = 10 ** 9 + 7
        maybe_list = []
        for i in range(1, n+1):
            left = abs(i - n)
            right = (n -1 )- left
            maybe_list.append(abs(left - right))

        pattern =  len(set([x for x in maybe_list if maybe_list.count(x) != 1]))

        for i in A:
            if i in maybe_list:
                maybe_list.remove(i)
            else:
                raise

        return (2 ** pattern) % div

    except:
        return 0


args = sys.argv
_n = int(args[1])
_A = map(int,args[2:])

print maybe_check(_n,_A)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter

def maybe_check(n,A):
    try:
        if n <= 0 or n > 100000:
            raise

        div = 1000000007
        maybe_list = [abs(abs(i - n) - ((n -1 ) - abs(i - n))) for i in range(1, n+1)]
        maybe_list.sort()
        A.sort()
        if A !=  maybe_list:
            raise

        pattern = len([num for num,count in Counter(maybe_list).items() if count != 1])
        return (2 ** pattern) % div

    except:
        return 0


_n = int(raw_input())
_A = map(int,raw_input().split())

print maybe_check(_n,_A)
import sys
 
IDX_TBL = {1:[2,3,5,4], 2:[3,1,4,6], 3:[1,2,6,5],
           4:[1,5,6,2], 5:[1,3,6,4], 6:[2,4,5,3]}
OPPSITE_TBL = {1:6, 2:5, 3:4, 4:3, 5:2, 6:1}

def is_same(l1, l2):
    if l1[1] in l2:
        idx_list = [i for i,x in enumerate(l2) if x==l1[1]]
        for idx in idx_list:
            nstr1 = "".join([l1[i] for i in IDX_TBL[1]])
            nstr2 = "".join([l2[i] for i in IDX_TBL[idx]])
            if nstr2 in nstr1*2:
                if l1[6] == l2[7-l2.index(l1[1])]:
                    return True
    return False

n=input()
nums_list = []
for _ in range(n):
    nums_list.append(["_"] + raw_input().split(" "))

for i in range(0, n):
    for j in range(i+1, n):
        if is_same(nums_list[i], nums_list[j]):
            print "No"
            sys.exit(0)
print "Yes"

### FIXED CODE ###

import sys
 
IDX_TBL = {1:[2,3,5,4], 2:[3,1,4,6], 3:[1,2,6,5],
           4:[1,5,6,2], 5:[1,3,6,4], 6:[2,4,5,3]}
OPPSITE_TBL = {1:6, 2:5, 3:4, 4:3, 5:2, 6:1}

def is_same(l1, l2):
    if l1[1] in l2:
        idx_list = [i for i,x in enumerate(l2) if x==l1[1]]
        for idx in idx_list:
            nstr1 = "".join([l1[i] for i in IDX_TBL[1]])
            nstr2 = "".join([l2[i] for i in IDX_TBL[idx]])
            if nstr2 in nstr1*2:
                if l1[6] == l2[7-l2.index(l1[1])]:
                    return True
    return False

n=input()
nums_list = []
for _ in range(n):
    nums_list.append(["_"] + raw_input().split(" "))

for i in range(0, n):
    for j in range(i+1, n):
        if is_same(nums_list[i], nums_list[j]):
            print "No"
            sys.exit(0)
print "Yes"
import sys

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


tmp1 = s[0]
count = 1
data = []
zeros = 0

for i in range(1,len(s)):
    tmp2 = s[i]
    if tmp1 != tmp2:
        data.append((tmp1, count))
        if tmp1 == '0':
            zeros += 1
        tmp1 = tmp2
        count = 1
    else:
        count += 1

data.append((tmp1,count))
if tmp1 == '0':
    zeros += 1

ans = 0

if k >= zeros:
    ans = len(s)

if data[0][0] == '0':
    data.insert(0, (1,0))

if data[-1][0] == '0':
    data.append((1,0))

anstmp = 0
for i in range(2*k + 1):
    anstmp += data[i][1]

ans = max(ans, anstmp)

for i in range(zeros - k):
    anstmp -= data[2*i][1]
    anstmp -= data[2*i + 1][1]
    anstmp += data[2*k + 2*i + 1][1]
    anstmp += data[2*k + 2*i + 2][1]

    ans = max(ans, anstmp)


print(ans)

### FIXED CODE ###

import sys

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


tmp1 = s[0]
count = 1
data = []
zeros = 0

for i in range(1,len(s)):
    tmp2 = s[i]
    if tmp1 != tmp2:
        data.append((tmp1, count))
        if tmp1 == '0':
            zeros += 1
        tmp1 = tmp2
        count = 1
    else:
        count += 1

data.append((tmp1,count))
if tmp1 == '0':
    zeros += 1

ans = 0

if k >= zeros:
    print(len(s))
    sys.exit()    

if data[0][0] == '0':
    data.insert(0, (1,0))

if data[-1][0] == '0':
    data.append((1,0))

anstmp = 0
for i in range(2*k + 1):
    anstmp += data[i][1]

ans = max(ans, anstmp)

for i in range(zeros - k):
    anstmp -= data[2*i][1]
    anstmp -= data[2*i + 1][1]
    anstmp += data[2*k + 2*i + 1][1]
    anstmp += data[2*k + 2*i + 2][1]

    ans = max(ans, anstmp)


print(ans)
import sys

def main():
    for input_line in sys.stdin:
        num1 = int(input_line.split(' ')[0])
        num2 = int(input_line.split(' ')[1])
        
        if num1 <= num2:
            dividend(num1, num2, num1)
        elif num1 > num2:
            dividend(num1, num2, num2)
            
        result.sort(reverse=True)
        greatest_common_divisor = result[0]
        least_common_multiple = num1 * num2 / greatest_common_divisor
        
        print('%s %s' % (greatest_common_divisor, least_common_multiple))
        
def dividend(num1, num2, num):
    for i in range(num).sort(reverse=True):
        divisor = i+1
        if num1 % divisor == 0 and num2 % divisor == 0:
            result.append(divisor)
            break
        
if __name__ == '__main__':
    result = []
    main()

### FIXED CODE ###

import sys

def dividend(num, Q):
    a = Q
    b = (num / Q) * Q
    Q = num - (num / Q) * Q
    if num  == b:
        aaa(a)
        return
    dividend(a, Q)
    
def aaa(greatest_common_divisor):
    least_common_multiple = num1 * num2 / greatest_common_divisor
    print('%s %s' % (greatest_common_divisor, least_common_multiple))
    return

for input_line in sys.stdin:
    num1 = int(input_line.split(' ')[0])
    num2 = int(input_line.split(' ')[1])
    
    if num1 <= num2:
        dividend(num2, num1)
    elif num1 > num2:
        dividend(num1, num2)
n = int(input())
alist=list(map(int,input().split()))

mod = (10**9 + 7)
ans = 0

import numpy
alistsum = numpy.cumsum(alist)

for i in range(n-1):
    ans += alist[i]*(alistsum[-1]-alistsum[i])
    ans = ans%mod

print(ans)

### FIXED CODE ###

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

mod = (10**9 + 7)
ans = 0

import numpy
alistsum = numpy.cumsum(alist)
asum = sum(alist)

for i in range(n-1):
    ans += alist[i]*(asum - alist[i])
    asum -= alist[i]
    ans = ans%mod
print(ans)
n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(n)
for i in range(m):
    x = xy[i][0]
    y = xy[i][1]
    u.union(x, y)

idxs = []
for i in range(1, n+1):
    idxs.append(u.find(i))

idx_dict = dict()
keys = []
for i in range(n):
    if idxs[i] not in keys:
        idx_dict[idxs[i]] = [i]
        keys.append(idx[i])
    else:
        idx_dict[idxs[i]].append(i)

counter = 0
for k in keys:
    l = idx_dict[k]
    template = []
    for i in range(len(l)):
        template.append(p[l[i]] - 1)

    counter += len(set(l) & set(template))

print(counter)


### FIXED CODE ###

n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]

from collections import defaultdict
g = defaultdict(list)
for x, y in xy:
    x, y = x - 1, y - 1
    g[x].append(y)
    g[y].append(x)

visited = [0] * n
ans = 0

for i in range(n):
    if visited[i] == 0:
        q = [i]
        visited[i] = 1
        s = set([i])
        while q:
            cur = q.pop()
            for target in g[cur]:
                if visited[target] == 0:
                    visited[target] = 1
                    q.append(target)
                    s.add(target)

        ps = set()
        for j in s:
            ps.add(p[j] - 1)

        intersect = s & ps
        ans += len(list(intersect))
print(ans)
from math import sqrt
n=input()
for i in range(n):
	x1,y1,x2,y2,x3,y3=map(float,raw_input().split())
	A1=2*(x2-x1)
	B1=2*(y2-y1)
	C1=x2**2+y2**2-x1**2-y1**2
	x=((C1*B2)-(C2*B1))/((A1*B2)-(A2*B1))
	y=((A1*C2)-(A2*C1))/((A1*B2)-(A2*B1))

### FIXED CODE ###

from math import sqrt
n=input()
for i in range(n):
	x1,y1,x2,y2,x3,y3=map(float,raw_input().split())
	A1=2*(x2-x1)
	B1=2*(y2-y1)
	C1=x2**2+y2**2-x1**2-y1**2
	A2=2*(x3-x2)
	B2=2*(y3-y2)
	C2=x3**2+y3**2-x2**2-y2**2
	x=(C1*B2-C2*B1)/(A1*B2-A2*B1)
	y=(A1*C2-A2*C1)/(A1*B2-A2*B1)
	R=sqrt((x1-x)**2+(y1-y)**2)
	print"%.3f %.3f %.3f"%(x,y,R)
S = int(input())
h = (S / 3600)
t = (S / 60)
s = (S - h - t)
print(h:t:s)

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format(h,m,s))
def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        if dp_table[i] < 0:
            continue
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = [a for a in As if dp_table[life - d_cost[a]] == dp_table[life] - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)
    





### FIXED CODE ###

def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        if dp_table[i] < 0:
            continue
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = []
        for a in As:
            if life - d_cost[a] < 0:
                continue
            if dp_table[life - d_cost[a]] == dp_table[life] - 1:
                oks.append(a)
        # oks = [a for a in As if dp_table[life - d_cost[a]] == dp_table[life] - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)
N = int(input())
p = list(map(int, input().split()))

ans = 0
flag = False
for i in range(N):
    if flag:
        n = p[i+1]
    else:
        n = p[i]
    if n == i+1:
        ans += 1
        flag = True
    else:
        flag = False
print(ans)

### FIXED CODE ###

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

ans = 0
flag = False
for i in range(N - 1):
    if flag:
        n = p[i+1]
    else:
        n = p[i]
    if n == i+1:
        ans += 1
        flag = True
    else:
        flag = False
if flag:
    n = p[-2]
else:
    n = p[-1]
if n == N:
    ans += 1
print(ans)
x = input()
print(x ** 3 + '\n')

### FIXED CODE ###

x = int(input())
print(x ** 3)
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

def permutation(a, aa=[]):
  if len(a)<=1:
    return [aa+a]

  res = []
  for x in a:
    b = a.copy()
    b.remove(x)
    res.extend(permutation(b, aa+[x]))

  return res


N = readi()
P = [ints() for i in range(N)]

s = 0.0
ps = permutation(list(range(N)))
pn = len(ps)

for p in ps:
  for i in range(N-1):
    q = p[i]
    r = p[i+1]
    s += ((P[q][0]-P[r][0])**2+(P[q][1]-P[r][1])**2)**(0.5)/pn
print(s)


### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

def permutation(a, aa=[]):
  if len(a)<=1:
    return [aa+a]

  res = []
  for x in a:
    b = a.copy()
    b.remove(x)
    res.extend(permutation(b, aa+[x]))

  return res

N = readi()
P = [ints() for i in range(N)]

s = 0.0
ps = permutation(list(range(N)))
pn = len(ps)

for p in ps:
  for i in range(N-1):
    q = p[i]
    r = p[i+1]
    s += ((P[q][0]-P[r][0])**2+(P[q][1]-P[r][1])**2)**(0.5)/pn
print(s)
n = int(input())

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

l = min(xs)
r = max(xs)

costs = []
for i in range(l, r):
    cost = 0
    for j in xs:
        cost += (j - i) ** 2
    costs.append(cost)

print(min(costs))



### FIXED CODE ###

n = int(input())

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

l = min(xs)
r = max(xs)

costs = []
for i in range(1, 100):
    cost = 0
    for j in xs:
        cost += (j - i) * (j - i)
    costs.append(cost)

print(min(costs))
import import re

s = str(input())
find_s = 'ABC'
count = 0
while True:
    s_n = re.sub(r"ABC", "BCA", s)
    l_find = len(re.findall(r"ABC", s))
    count += l_find

    if l_find == 0:
        print(count)
        break
    else:
        s = s_n

### FIXED CODE ###

import re

s = input()
s = s.replace('BC', 'D')

count = 0
count_a = 0
for string in s:
    if string == 'A':
        count_a += 1
    elif string == 'D':
        count += count_a
    else:
        count_a = 0

print(count)
def 解():
    iN = int(input())
    iD = 10**9 + 7


    if iN < 3:
        print(iN)
        exit()

    d素={2:1}
    for i in range(2,iN + 1):
        b素 = 1
        for j in range(2,int(i**0.5)+2):
            if i % j == 0:
                b素 = 0
                break
        if b素 :
            d素[i]=1
    for i in range(2,iN+1):
        for i素 in d素:
            while i % i素 == 0:
                d素[i素]+=1
                i //= i素
           if i == 0:
                break
    iAns = 1
    for i素,num in d素.items():
        iAns *= num
        iAns %= iD
    print(iAns)
解()


### FIXED CODE ###


def 解():
    iN = int(input())
    iD = 10**9 + 7


    if iN < 3:
        print(iN)
        exit()

    d素={2:1}
    for i in range(2,iN + 1):
        b素 = 1
        for j in range(2,int(i**0.5)+2):
            if i % j == 0:
                b素 = 0
                break
        if b素 :
            d素[i]=1
    for i in range(2,iN+1):
        for i素 in d素:
            while i % i素 == 0:
                d素[i素]+=1
                i //= i素
    iAns = 1
    for i素,num in d素.items():
        iAns *= num
        iAns %= iD
    print(iAns)
解()
n = int(input())
    sols = []
    for i in range(n):
        sols.append([int(i) for i in input().split()])
    if len(sols) == 1:
        print(*sols[0])
 
    for cx in range(0, 101):
        for cy in range(0, 101):
            lastH = None
            for x, y, h in sols:
                H = h + abs(x - cx) + abs(y - cy)
                if H < 1:
                    continue
                if lastH:
                    if H != lastH:
                        break
                lastH = H
            else:
                print(cx, cy, H)
                break

### FIXED CODE ###

n = int(input())
s_list = []
ans = 0
zero_list = []
for _ in range(n):
    x, y, s = map(int, input().split())
    if s > 0:
        s_list.append([x, y, s])
    else:
        zero_list.append([x, y, s])
for x in range(101):
    for y in range(101):
        t = []
        for i in range(len(s_list)):
            x_, y_, h = s_list[i]
            if h > 0:
                t.append(h + abs(x_ - x) + abs(y_ - y))
        if (len(set(t)) == 1):
            if len(zero_list) > 0:
                zero_p = max([list(t)[0] - abs(x - x_zero) - abs(y - y_zero) for (x_zero, y_zero, s_zero) in zero_list])
                if zero_p <= 0:
                    ttt = h + abs(x_ - x) + abs(y_ - y)
                    ans = str(x) + " " + str(y) + " " + str(ttt)
                    break
            else:
                ttt = h + abs(x_ - x) + abs(y_ - y)
                ans = str(x) + " " + str(y) + " " + str(ttt)
                break
                
print(ans)
n,m = map(int,input().split())
a = [int(s) for s in input().split()]
a.sort()
b_c = [[int(s) for s in input().split()] for i in range(m)]
cnt = 0
for k in range(m):
    while cnt < b_c[k][0]:
        if a[cnt] <= b_c[k][1]:
            a[cnt] = b_c[k][1]
        cnt += 1
    a.sort()
print(sum(a))        
    
        

### FIXED CODE ###

a,b =map(int,input().split())
if a >= 13:
    print(b)
elif 6<= a <= 12:
    print(int(b/2))
elif  a <= 5:
    print(0)
a=input()
if int(a/2)*2==a:
  print(a)
#else:
  #print(a*2)


### FIXED CODE ###

a=int(input())
b=int(a/2)
if b*2==a:
  print(a)
else:
  print(a*2)
n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
for i in set(s):
    result=s.count(i)-t.count(i)
print(max(o,result))


### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
result=0
for i in set(s):
    result=max(result,s.count(i)-t.count(i))
print(result)
n,l = map(int,input().split())
mylist=sotrted([input() for i in range(n)])
print("".join(mylist))

### FIXED CODE ###

n,l = map(int,input().split())
mylist=sorted([input() for i in range(n)])
print("".join(mylist))
S,T=map(chr, input(),split())
A,B map(int, input(),split())
U = chr(input())
if S==U:
  A=A-1
elif T==U:
  B=B-1
print(A,B)

### FIXED CODE ###

S, T = input().split()
A, B= map(int, input().split())
U = input()
if S == U:
    print(A - 1, B)
else:
    print(A, B - 1)
n = int(input())
l = [[0, 0, 0]]
for _ in range(n):
	data = list(map(int, input().split()))
	l.append(data)

message = "Yes"
for i in range(len(l)):
	t_delta = abs(l[i][0] - l[i + 1][0])
	x_delta = abs(l[i][1] - l[i + 1][1])
	y_delta = abs(l[i][2] - l[i + 1][2])
	t_minus_d = t_delta - x_delta - y_delta
	if (t_minus_d < 0) or (t_minus_d % 2 != 0):
		message = "No"
		break
print(message)


### FIXED CODE ###

n = int(input())
l = [[0, 0, 0]]
for _ in range(n):
	data = list(map(int, input().split()))
	l.append(data)

message = "Yes"
for i in range(len(l) - 1):
	t_delta = abs(l[i][0] - l[i + 1][0])
	x_delta = abs(l[i][1] - l[i + 1][1])
	y_delta = abs(l[i][2] - l[i + 1][2])
	t_minus_d = t_delta - x_delta - y_delta
	if (t_minus_d < 0) or (t_minus_d % 2 != 0):
		message = "No"
		break
print(message)
#!/opt/local/bin/python
from math import pi
a = raw_input()
print"%.6f %.6f" %(pi*int(a)**2.0,2.0*pi*int(a))

### FIXED CODE ###

#!/opt/local/bin/python
import math
a = raw_input()
print"%f %f" %(math.pi*float(a)**2.0,2.0*math.pi*float(a))
b = list(map(int, input().split()))
a = str(b)
ans = 0
if (a[1] == '1'):
    ans = ans+1
if (a[2] == '1'):
    ans = ans+1
if (a[3] == '1'):
    ans = ans+1
print(ans)

### FIXED CODE ###

a= input()
ans = 0
if (a[0] == '1'):
    ans = ans+1
if (a[1] == '1'):
    ans = ans+1
if (a[2] == '1'):
    ans = ans+1
print(ans)
N = int(input())

if N % 111 == 0:
  print (N)
else:
  print((math.floor(N / 111) + 1) * 111 )

### FIXED CODE ###

import math
N = int(input())

if N % 111 == 0:
  print (N)
else:
  print((math.floor(N / 111) + 1) * 111 )
FizzBuzz = int(input())

Sum = []
for i in range(FizzBizz):
    if FizzBuzz[i] % 3 == 0 and FizzBuzz[i] % 5 == 0:
        Sum.append(i)
    else:
        Sum.append(0)
print(sum(Sum))


### FIXED CODE ###

FizzBizz = int(input())

Sum = []
for i in range(1, FizzBizz+1):
    if i % 3 != 0 and i % 5 != 0:
        Sum.append(i)
    else:
        Sum.append(0)
print(sum(Sum))
n = int(input())
aa = list(map(int, input().split()))
bb = set()
cc = set()

for a in aa:
  if aa.count(a) > 1:
    bb.add(a)
  if aa.count(a) >3:
    cc.add(a)
    
m1 = max(bb)
bb.remove(m1)
m2 = max(bb)

if len(cc) > 0:
  y = max(cc)
else:
  y = 0

if len(bb) >= 2:
  ans = max(m1*m2, y*y)
else:
  ans = max(0, y*y)
print(ans)

### FIXED CODE ###

import collections
n = int(input())
aa = list(map(int, input().split()))
ca = collections.Counter(aa)
la = sorted([a for a in ca.items()], key = lambda x:x[0], reverse=True)

list1 = []
list2 = []

for a in la:
  if a[1] > 1:
    list1.append(a)
  if a[1] >3:
    list2.append(a)
    
if len(list1) > 1:    
    xr = list1[0][0] * list1[1][0]
else:
  xr = 0
    
if len(list2) > 0:
  xs = list2[0][0] * list2[0][0]
else:
  xs = 0
  
ans = max(xr, xs)

print(ans)
# import sys
# sys.setrecursionlimit
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % mod

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

if M == 1:
    print(0 if K < N - 1 else 1)
    exit()

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % mod

print(ans)
import math
from functools import reduce

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

def dist(n):
    return abs(int(n)-x)

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

def gcds(*s):
    return reduce(math.gcd, s)

print(gcds(*a))

### FIXED CODE ###

import fractions

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

def dist(n):
    return abs(int(n)-x)

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

ans = a[n-1]

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

print(ans)
# -*- coding: utf-8 -*-
a, b, c = map(int, input().split())
print(int(b * ((t+0.5)//a)))

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b, t = map(int, input().split())
print(int(b * ((t+0.5)//a)))