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

ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
n = ini()
s = input()
ans = 0
for k in range(n):
    for j in range(k):
        if s[k] == s[j]:
            continue
        for i in range(j):
            if j-i == k-j:
                continue
            if s[k] == s[i]:
                continue
            if s[i] == s[j]:
                continue
            ans += 1

print(ans)

### FIXED CODE ###

ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
n = ini()
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b

for j in range(n):
    for i in range(j):
        k = 2*j-i
        if k < n:
            if (s[i] == s[j]):
                continue
            if (s[i] == s[k]):
                continue
            if (s[j] == s[k]):
                continue
            ans -= 1
print(ans)
### BUGGY CODE ###

import numpy as np
 
s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int32)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC+=np.roll(wayB,1)
		wayB+=np.roll(wayA,1)
		wayA[1]+=1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))

### FIXED CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)
dh = []
for i in range(N - K + 1):
    dh = dh + [h[i + K - 1]-h[i]]

print(min(dh))

### FIXED CODE ###

N, K = map(int, input().split())
h = sorted([int(input()) for _ in range(N)])
print(min([h[i+K-1]-h[i] for i in range(N - K + 1)]))
### BUGGY CODE ###

from itertools import permutations
import sys


input = sys.stdin.readline


N, M, R = map(int, input().split())
dest = [x-1 for x in map(int, input().split())]

inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    mat[a-1][b-1] = mat[b-1][a-1] = c


def war(mat):
    ran = range(N)
    for i in ran:
        for j in ran:
            for k in ran:
                mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])
    return mat


ans = inf
mat = war(mat)
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
        if tmp > ans:
            break
    ans = min(ans, tmp)

print(ans)


### FIXED CODE ###

from itertools import permutations
import sys


input = sys.stdin.readline


N, M, R = map(int, input().split())

dest = [x-1 for x in map(int, input().split())]


inf = float('inf')
mat = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    mat[a-1][b-1] = mat[b-1][a-1] = c


for i in range(N):
    for j in range(N):
        for k in range(N):
            mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
    ans = min(ans, tmp)

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

mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)



### FIXED CODE ###

from collections import Counter
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
l = 0
for i in range(1,n+1):
	if C[i] > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)
### BUGGY CODE ###

n,k = map(int,input().split())
point = list(map(int,input().split()))
def seki(k,b,point):
    a = 1
    score = []
    for i in range(b,b+k):
        a = a*point[i]
    return a

for j in range(n-k):
    if seki(k,j,point)< seki(k,j+1,point):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k = map(int,input().split())
point = list(map(int,input().split()))
for j in range(n-k):
    if point[j] < point[j+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
q = [A[0]]
p = A[0]
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if p >= A[i] and insert_index == 0:
        q.insert(0, A[i])
        ans += 1
    else:
        q[insert_index-1] = A[i]
    p = A[i]

print(len(q))


### FIXED CODE ###

from bisect import bisect_left
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

q = deque([A[0]])
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if insert_index == 0:
        q.appendleft(A[i])
    else:
        q[insert_index-1] = A[i]

print(len(q))
### BUGGY CODE ###

import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()

### FIXED CODE ###

import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()
### BUGGY CODE ###

#import
#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

weight = [0] * N
value = [0] * N

for i in range(N):
    w, v = map(int, input().split())
    weight[i] = w
    value[i] = v



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

for i in range(1, N + 1):
    for j in range(1, W + 1):

        if weight[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[-1][W])


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            num[max(0,j-a[j])]+=1
            num[min(n,j+a[j]+1)]-=1
        num5=0
        for j in range(n):
            num5+=num[j]
            ans[j]=num5
        a=ans
        if sum(ans)==n*n:
            break
    print(*a)


### FIXED CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)
### BUGGY CODE ###

import sys
from collections import defaultdict

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        for k, p in dp[i].items():
            dp[i + a][k + 1] += p
            dp[i + a][k + 1] %= MOD
    tmp_sum += a

ans = pow(3, n, MOD)
sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub += d2[n - k] * p * 3
    sub %= MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub -= p * 3

ans = (ans - sub) % MOD
print(ans)


### FIXED CODE ###

import sys

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

s = sum(aaa)
dp1 = [0] * (s + 1)
dp2 = [0] * (s + 1)
dp1[0] = 1
dp2[0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dp1[i + a] += dp1[i]
        dp1[i] *= 2
        dp2[i + a] += dp2[i]
    for i in range(tmp_sum, -1, -1):
        dp1[i] %= MOD
        dp2[i] %= MOD
    tmp_sum += a

h = (s + 1) // 2
ans = (pow(3, n, MOD) - sum(dp1[h:]) * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % MOD
print(ans)
### BUGGY CODE ###

s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
dp[0][0]=1
for i in range(len(s)):
    if s[i]=='?':
        c=-1
    else:
        c=int(s[i])
    
    for j in range(10):
        if c!=-1 and c!=j:
            continue
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
            dp[i+1][(k*10+j)%13]%=(10**9+7)


print(dp[len(s)][5])

### FIXED CODE ###

s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
dp[0][0]=1
for i in range(len(s)):
    
    if s[i]!='?':  
        j=int(s[i])
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
            dp[i+1][(k*10+j)%13]%=(10**9+7)
    else:
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
                dp[i+1][(k*10+j)%13]%=(10**9+7)

print(dp[len(s)][5])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
res = A[0]
for i in range(1,N): 
	res *= A[i]
if res <= 10**18:
	print(res)
else:
	print("-1")


### FIXED CODE ###

a=int(input())
b=input().split(" ")
sum1=1
 
if "0" in b:
    print("0")
else:
    for i in range(a):
        sum1=sum1*int(b[i])
        if sum1>10**18:
            sum1=-1
            break
    print(sum1)
### BUGGY CODE ###

import math
import numpy as np

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subcusum = []
        for sub_ in subcu:
            subcusum.append(np.sum(np.array(sub_),axis=0))

        subcusum = np.array(subcusum)

        cutnum = 0
        j=0
        temp = 0
        for j in range(w):
            subsum = subcusum[:,j]-temp
            if np.any(subsum>k):
                temp = subcusum[:,j-1]
                cutnum+=1
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subs = divide(s,i)

        subcusum = []

        rowsum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        for sub_ in subs:
            rowsum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))


        cutnum = 0

        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    if rowsum[l][j]>k:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
s=input()
s_list=list(s)

count=1

while count!=0:
  count=0
  for j in range(0,len(s_list)-1):
    if s_list[j] == s_list[j+1]:
      s_list.pop(j+1)
      count=1
      break
  
print(len(s_list))

### FIXED CODE ###

N=int(input())
s=input()
s_list=list(s)
import itertools as itl
list2=[k for k, v in itl.groupby(s_list)]
print(len(list2))
### BUGGY CODE ###

from copy import copy
from collections import deque
import numpy as np
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
k = np.array(L)
first = deque(L)
count = 0
for i in range(N-2):
    l = first.popleft()
    second = copy(first)
    for j in range(1,N-i-1):
        m = second.popleft()
        n = np.count_nonzero(np.array(second) > (l-m))
        if n == 0:
            break
        else:
            count += n
print(count)

### FIXED CODE ###

from copy import copy
from collections import deque
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
first = deque(L)
count = 0
for i in range(N-2):
    l = first.pop()
    second = copy(first)
    for j in range(1,N-i-1):
        m = second.pop()
        n = len(second) - bisect.bisect_right(second,l-m)
        if n > 0:
            count += n
        else:
            break
print(count)
### BUGGY CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    for i in range(K+1):
        r += c.cmb(l+i-1, i) * pow(25, i, mod) * pow(26, K-i, mod)
        r %= mod
    return r
print(main())


### FIXED CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 6) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 2 * (10 ** 6):
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())
### BUGGY CODE ###

N=int(input())
import math
n1=int(math.sqrt(N))
for i in range(1,N+1) :
  count=0
  n1 = int(math.sqrt(i))
  for x in range(1,n1+1) :
    n2 = int(math.sqrt(N-x*x))
    for y in range(1,n2+1) :
      n3 = int(math.sqrt(N - y * y))
      for z in range(1,n3) :
        if x*x+y*y+z*z+x*y+y*z+z*x==i :
          count+=1
  print(count)

### FIXED CODE ###

N=int(input())
import math
n1=int(math.sqrt(N))

list1=[0 for i in range(N)]

for x in range(1,n1) :
  for y in range(1,n1) :
    for z in range(1,n1) :
      k=x*x+y*y+z*z+x*y+y*z+z*x
      if k<=N :
        list1[k-1]+=1
for item in list1 :
  print(item)
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
from numba import jit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
point = 0

@jit
def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

col = m
for i in range(n-1,-1,-1):
    now = col
    now *= combination(n-1,i)
    if i <= k:
        point += now%mod
    col *= m-1

print(point%mod)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def prepare(n, MOD=mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs
facts, invs = prepare(n, mod)
for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod

    now *= facts[n-1]*invs[n-1-i]*invs[i]
    if i <= k:
        point += now%mod

print(point%mod)
### BUGGY CODE ###

x,y,z,k = [ int(it) for it in input().split() ]
al = [ int(it) for it in input().split() ]
bl = [ int(it) for it in input().split() ]
cl = [ int(it) for it in input().split() ]

abl = [ a + b for a in al for b in bl]
abl.sort()
abl.reverse()
abl=abl[:k]

abcl = [ ab + c for ab in abl for c in cl]
abcl.sort()
abcl.reverse()
abcl=abcl[:k]
print ( "\n".join( [ str(it) for it in abcl ]) )






### FIXED CODE ###

x,y,z,k = [ int(it) for it in input().split() ]
al = [ int(it) for it in input().split() ]
bl = [ int(it) for it in input().split() ]
cl = [ int(it) for it in input().split() ]

abl = [ a + b for a in al for b in bl]
abl.sort()
abl.reverse()
abl=abl[:k]

abcl = [ ab + c for ab in abl for c in cl]
abcl.sort()
abcl.reverse()
abcl=abcl[:k]
print ( "\n".join( [ str(it) for it in abcl ]) )
### BUGGY CODE ###

N,W = list(map(int, input().split()))
m = []
v = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

for i in range(N):
    for j in range(W):
        if j+m[i] <= W:
            dp[i+1][j+m[i]] = max(dp[i][j] + v[i], dp[i+1][j+m[i]])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])


print(max(dp[-1]))


### FIXED CODE ###

N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

sum_v = sum(v)
dp = [[10**15 for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    dp[i][0] = 0
    for j in range(sum_v+1):
        if j != 10**15:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break
### BUGGY CODE ###

n = (int)(raw_input())
s = map(int,raw_input().split())
q = (int)(raw_input())
t = map(int,raw_input().split())
count = 0
for i in range(q):
	for j in range(n):
		if t[i] == s[j]:
			count += 1
			break
print(count)

### FIXED CODE ###

n = (int)(raw_input())
s = set(map(int,raw_input().split()))
q = (int)(raw_input())
t = set(map(int,raw_input().split()))
count = 0
print(len(s.intersection(t)))