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

MAX = 10**9 + 7

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i)
        low *= (i + 1)
    ret = up /low
    if ret >= MAX:
        ret %= MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()


### FIXED CODE ###

MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = (M*N* ((M*(N+1)*(N-1))%MAX + (N*(M+1)*(M-1)) % MAX)) % MAX
    disSum *= mod_inv(6, MAX) % MAX
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

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

N = int(input())
list_a = [int(x) for x in input().split()]

ans = 0

for i in range(N) :
    X = list_a[i]
    ans1 = list_a.count(X) + list_a.count(X+1) + list_a.count(X-1)
    ans2 = list_a.count(X) + list_a.count(X+1) + list_a.count(X+2)
    ans3 = list_a.count(X) + list_a.count(X-1) + list_a.count(X-2)
    ans = max(ans,ans1,ans2,ans3)

print(ans)


### FIXED CODE ###

N = int(input())
list_a = [int(x) for x in input().split()]

list_X = []

for X in list_a :
    list_X.append(X)
    list_X.append(X+1)
    list_X.append(X-1)

from collections import Counter
print(max(Counter(list_X).values()))
### BUGGY CODE ###

S = input()
S2 = ""
Q = int(input())
reverse = 1
for i in range(Q):
    list = input()
    if list[0] == "1":
        reverse *= -1
    else:
        if reverse == 1:
            if list[2] == "2":
                S += list[4]
            else:
                S2 += list[4]
        else:
            if list[2] == "2":
                S2 += list[4]
            else:
                S += list[4]
if reverse == 1:
    print(S2[::-1] + S)
else:
    print(S[::-1] + S2)


### FIXED CODE ###

S = input()
S2 = ""
Q = int(input())
reverse = 1
for i in range(Q):
    list = input()
    if list[0] == "1":
        reverse *= -1
    else:
        if reverse == 1:
            if list[2] == "2":
                S += list[4]
            else:
                S2 += list[4]
        else:
            if list[2] == "2":
                S2 += list[4]
            else:
                S += list[4]
if reverse == 1:
    print(S2[::-1] + S)
else:
    print(S[::-1] + S2)
### BUGGY CODE ###

h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

stack = MyStack()
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            stack.push(i+1,j+1)
while stack.stack:
    y,x = stack.pop()
    route_num = route[y-1][x-1] + 1
    if y != h:
        if maze[y][x-1] == '.' and route[y][x-1] == 0:
            stack.push(y+1,x)
            route[y][x-1] = route_num
            
    if y != 1:
        if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
            stack.push(y-1,x)
            route[y-2][x-1] = route_num
            
    if x != w:
        if maze[y-1][x] == '.' and route[y-1][x] == 0:
            stack.push(y,x+1)
            route[y-1][x] = route_num
 
    if x != 1:
        if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
            stack.push(y,x-1)
            route[y-1][x-2] = route_num
            
print(route_num - 1)

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

dp = [0] * (N+10)
dp[0] = 1

for i in range(N):
    if i in A:
        continue

    dp[i+1] = ((dp[i] % MOD) + (dp[i+1] % MOD)) % MOD
    dp[i+2] = ((dp[i] % MOD) + (dp[i+2] % MOD)) % MOD

print(dp[N])


### FIXED CODE ###

# coding: utf-8

import sys
def input(): return sys.stdin.readline().strip()

MOD = 10**9 + 7
# N = int(input())
# L = [int(x) for x in input().split()]
N, M = map(int, input().split())
# S = input()

dp = [0] * (N + 5)
dp[0] = 1

for _ in range(M):
    dp[int(input())] = -1

for i in range(N):
    if dp[i] == -1:
        continue
    if dp[i + 1] != -1:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
    if dp[i + 2] != -1:
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD

print(dp[N])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

ans = 0
for a in A:
    for b in B[(np.where(B > a))]:
        ans += len(B[(np.where(b < C))])

print(ans)




### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))
A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    AB = A.searchsorted(b, side='left')
    CB = len(B) - C.searchsorted(b, side='right')
    ans += AB * CB

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

n=int(input())
s=input()
import itertools
print(len(set(itertools.combinations(list(s),3))))

### FIXED CODE ###

n=int(input())
s=input()
numbers=[str(i).zfill(3) for i in range(1000)]

count=0
for num in numbers:
	j=0
	for i in range(n):
		if num[j]==s[i]:
			j+=1
		if j==3:
			break
	if j==3:
		count+=1
print(count)
### BUGGY CODE ###

def main():
    N, Q = list(map(int, input().split()))
    S = input()
    L, R = [], []
    for i in range(Q):
        l, r = list(map(int, input().split()))
        L.append(l)
        R.append(r)

    for l, r in zip(L, R):
        print(S[l-1:r].count("AC"))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()

    t = [0] * (N + 1)
    for i in range(N):
        t[i + 1] = t[i] + (1 if S[i:i + 2] == "AC" else 0)
    for i in range(Q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])


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

import bisect

N = int(input())
find = [int(input())]

for i in range(N-1):
    A = int(input())

    if find[0] >= A:
        find.insert(0, A)
    else:
        idx = bisect.bisect_left(find, A)
        x = find.pop(idx-1)
        bisect.insort_left(find, A)

print(len(find))

### FIXED CODE ###

from bisect import bisect_right

def main():    
    N = int(input())
    A = [int(input()) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print(len(n))

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

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

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

MOD = 10**9 + 7

N = read()

NN = N + 1
fact = [1] * NN
for i in range(1, NN):
  fact[i] = (fact[i-1] * i) % MOD

def inv(n):
  return pow(n, MOD-2, MOD)

invfact = [inv(fact[i]) for i in range(NN)]

def comb(n, k):
  return fact[n] * invfact[n-k] % MOD * invfact[k] % MOD

S = [0] * N
for k in range((N+1) // 2, N):
  S[k] = comb(k-1, N-1-k) * fact[k] % MOD * fact[N-1-k] % MOD

ans = 0
for k in range((N+1) // 2, N):
  ans = (ans + k * (S[k] - S[k-1]) % MOD) % MOD
print(ans)


### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
MOD = 10**9 + 7
 
N = read()
 
NN = N + 1
fact = [1] * NN
for i in range(1, NN):
  fact[i] = (fact[i-1] * i) % MOD
 
def inv(n):
  return pow(n, MOD-2, MOD)
 
invfact = [0] * NN
invfact[-1] = inv(fact[-1])
for i in range(NN-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD
 
def comb(n, k):
  return fact[n] * invfact[n-k] % MOD * invfact[k] % MOD
 
S = [0] * N
for k in range((N+1) // 2, N):
  S[k] = comb(k-1, N-1-k) * fact[k] % MOD * fact[N-1-k] % MOD
 
ans = 0
for k in range((N+1) // 2, N):
  ans = (ans + k * (S[k] - S[k-1]) % MOD) % MOD
print(ans)
### BUGGY CODE ###

import numpy as np

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

ans = 0
for i in a:
    if np.count_nonzero(i % a == 0) == 1:
        ans += 1
print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    ans = 0
    mx = max(a) + 1
    dp = [0] * mx
    for i in a:
        for j in range(i, mx, i):
            dp[j] += 1
    for i in a:
        if dp[i] == 1:
            ans += 1

    print(ans)


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

import copy
n,m=map(int,input().split())

a=list(map(int,input().split()))
aorg=a[:]
waribiki=[0]*n

for i in range(m):
  maxindex=a.index(max(a))
  a[maxindex]=a[maxindex]/2
  waribiki[maxindex]+=1

total=0
for i in range(n):
  if waribiki[i]!=0:
    aorg[i]=aorg[i]//(2**waribiki[i])
  total+=aorg[i]
print (total)



### FIXED CODE ###

import copy
import heapq
import math
n,m=map(int,input().split())
a=[0]*n
atmp=list(map(int,input().split()))
for i in range(n):
  a[i]=-atmp[i]

heapq.heapify(a)
for i in range(m):
  tmp=heapq.heappop(a)
  heapq.heappush(a,tmp/2)

total=0  
for i in range(n):
  total+=math.ceil(a[i])
print (-total)
### BUGGY CODE ###

import heapq as hp
N = int(input())
d = [-1]*N
arr = []
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    arr.append([u,v,w])
e_list = [set() for i in range(N)]
e_graph = [[0]*N for i in range(N)]
for u,v,w in arr:
    e_list[u].add(v)
    e_list[v].add(u)
    e_graph[u][v] = w
    e_graph[v][u] = w

stack = [[0,0]]
d[0] = 0
for w in range(N):
    if stack == []:
        break
    cost,cur_pos = hp.heappop(stack)
    cost *= -1
    for des in e_list[cur_pos]:
        if d[des] < 0:
            d[des] = d[cur_pos] + e_graph[cur_pos][des]
            hp.heappush(stack,[-d[des],des])

for i in d:
    print(i%2)


### FIXED CODE ###

import heapq as hp
N = int(input())
ans = [-1]*N
arr = []
for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    arr.append([u,v,w])
e_list = [[] for i in range(N)]
for u,v,w in arr:
    e_list[u].append([v,w])
    e_list[v].append([u,w])

stack = [0]
ans[0] = 0
while(stack):
    cur_pos = stack.pop()
    for des,cost in e_list[cur_pos]:
        if ans[des] >=  0:
            continue
        ans[des] = (ans[cur_pos] + cost)%2
        stack.append(des)
for i in ans:
    print(i)
### BUGGY CODE ###

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

N = int(input())
if N == 1:
    print(0)
    exit();

S = factorization(N)
ans = 0

for i in S:
    cnt = 1
    while i[1] > 0:
        if  i[1] >= cnt:
            i[1] -= cnt
            cnt += 1
            ans += 1
        else:
            continue;

print(ans)

### FIXED CODE ###

def factorization(n):
    ans = 0
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            ch_point = 1
            while temp%i==0:
                cnt+=1
                if cnt == ch_point:
                    cnt = 0
                    ans += 1
                    ch_point += 1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])
        ans += 1

    if arr==[]:
        arr.append([n, 1])
        ans += 1

    return ans

N = int(input())
if N == 1:
    print(0)
    exit();


print(factorization(N))
### BUGGY CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
#if 5<n<13:
t=n//3
#elif n<3000:
  #  t=n//9
#else:
  #  t=n//17
while G[0]<t:
    G.insert(0,G[0]*2+1)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])

### FIXED CODE ###

#shellSort(A, n)
n=int(input())
A=[int(input()) for i in range(n)]
cnt = 0
G=[1]
S=str(G[0])
#if 5<n<13:
t=n//5
#elif n<3000:
  #  t=n//9
#else:
  #  t=n//17
#Gt=[4, 9, 20, 46, 103, 233, 525, 1182,2660, 5985, 13467]
f=1.0
while f<t:
    f*=2.2
    f=int(f)
    G.insert(0,f)
  #  print (i)
    S=str(G[0])+" "+S
m=len(G)
print (m)
print(S)
for i in range(m):
    g=G[i]
    for j in range(g,n):
        v = A[j]
        k = j - g
        while k >= 0 and A[k] > v:
              A[k+g] = A[k]
              k = k - g
              cnt+=1
        A[k+g] = v 
print(cnt)
for i in range(n):
    print(A[i])
### BUGGY CODE ###

from operator import mul
print reduce(mul,range(1,int(raw_input())+1),1)%(10**9+7)

### FIXED CODE ###

from operator import mul
print reduce(lambda a,b:a*b%(10**9+7),range(1,int(raw_input())+1),1)
### BUGGY CODE ###

from collections import defaultdict
from itertools import accumulate
import heapq
n,m,s,t=map(int, input().split())
s-=1
t-=1
yen=[[0 for _ in range(n)] for _ in range(n)]
snk=[[0 for _ in range(n)] for _ in range(n)]
adj=defaultdict(list)
for _ in range(m):
    u,v,a,b=map(int, input().split())
    u-=1    
    v-=1    
    adj[u].append(v)
    adj[v].append(u)
    yen[u][v]=a
    yen[v][u]=a
    snk[u][v]=b
    snk[v][u]=b

def dijkstra(s, t, cost):
    q=[]
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(q, (d[s], s))
    while q!=[]:
        du, u=heapq.heappop(q)
        if du>d[u]:
            continue
        for v in adj[u]:
            tmp=du+cost[u][v]
            if d[v]>tmp:
                d[v]=tmp
                heapq.heappush(q, (d[v], v))
    return d

d1=dijkstra(s, t, yen)
d2=dijkstra(t, s, snk)
snuke=[]
for d1i, d2i in zip(d1,d2):
    snuke.append(d1i+d2i)
ans=list(accumulate(reversed([y+s for y,s in zip(d1, d2)]), min))
for ai in reversed(ans):
    print(10**15-ai)


### FIXED CODE ###

from collections import defaultdict
import heapq
n,m,s,t=map(int, input().split())
s-=1
t-=1
yen={}
snk={}
adj=defaultdict(list)
for _ in range(m):
    u,v,a,b=map(int, input().split())
    u-=1    
    v-=1    
    adj[u].append(v)
    adj[v].append(u)
    yen[(u,v)]=a
    yen[(v,u)]=a
    snk[(u,v)]=b
    snk[(v,u)]=b

def dijkstra(s, t, cost):
    q=[]
    d=[float('inf')]*n
    d[s]=0
    heapq.heappush(q, (d[s], s))
    prev={}
    while q!=[]:
        du, u=heapq.heappop(q)
        for v in adj[u]:
            if d[v]>du+cost[(u,v)]:
                d[v]=du+cost[(u,v)]
                prev[v]=u
                
                heapq.heappush(q, (d[v], v))
    return d

d1=dijkstra(s, t, yen)
d2=dijkstra(t, s, snk)
snuke=[]
for d1i, d2i in zip(d1,d2):
    snuke.append(d1i+d2i)
ans=[]
mins=float('inf')
for si in reversed(snuke):
    if si<mins:
        ans.append(si)
        mins=si
    else:
        ans.append(mins)
ans.reverse()
for ai in ans:
    print(10**15-ai)
### BUGGY CODE ###

def main():
    HP,n = map(int,input().split())
    s = [tuple(map(int,input().split())) for i in range(n)]
    max_s = max(s)

    #dp[damage] := モンスターにdamageを与える最小コスト
    dp = [float('inf')]*(HP+1) #0~HP
    dp[0] = 0
    for hp in range(HP):
        for damage, cost in s:
            next_idx = min(hp+damage, HP)
            dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

HP,n = map(int,input().split())
s = [tuple(map(int,input().split())) for i in range(n)]

#dp[damage] := モンスターにdamageを与える最小コスト
dp = [float('inf')]*(HP+1) #0~HP
dp[0] = 0
for damage, cost in s:
    for hp in range(HP):
        next_idx = min(hp+damage, HP)
        dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
print(dp[-1])
### BUGGY CODE ###

N,Q = map(int,input().split(" "))
s=list(input())
ju = []
for i in range(Q):
    ju.append(input().split(" "))

def isdead(xp):
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0 or xp > N-1:
            return True
    return False

def mid(x1,x2):
    return int((x1+x2)/2)

p1 = 0
p3 = N-1
p2 = int((p1+p3) / 2)
ap = -1
#left
while p1 != p2:
    if isdead(p2):
        p2,p3 = int((p1+p2)/2),p2
    else:
        ap = p2
        break
#right
if ap == -1:
    while p2 != p3:
        if isdead(p2):
            p2,p1 = int((p2+p3)/2),p2
        else:
            ap = p2
            break
if ap == -1:
    print(0)
    exit()

#left
p1 = 0
p3 = ap
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdead(p2):
        p1,p2 = p2,mid(p2,p3)
    else:
        p2,p3 = mid(p1,p2),p2
if isdead(p1):
    p = p3
else:
    p = p1
#right
p1 = ap
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdead(p2):
        p2,p3 = mid(p1,p2),p2
    else:
        p1,p2 = p2,mid(p2,p3)
if isdead(p3):
    q = p1
else:
    q = p3


if p > q:
    print(0)
else:
    print(q-p+1)


### FIXED CODE ###

input = raw_input

N,Q = map(int,input().split(" "))
s=list(input())
ju = []
for i in range(Q):
    ju.append(input().split(" "))

def isdeadleft(xp):
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0:
            return True
        if xp > N-1:
            xp = N-1
    return False

def isdeadright(xp):
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0:
            xp = 0
        if xp > N-1:
            return True
    return False

def mid(x1,x2):
    return int((x1+x2)/2)

if isdeadleft(N-1) or isdeadright(0):
    print(0)
    exit()

#left
p1 = 0
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdeadleft(p2):
        p1,p2 = p2,mid(p2,p3)
    else:
        p2,p3 = mid(p1,p2),p2
if isdeadleft(p1):
    p = p3
else:
    p = p1
#right
p1 = 0
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdeadright(p2):
        p2,p3 = mid(p1,p2),p2
    else:
        p1,p2 = p2,mid(p2,p3)
if isdeadright(p3):
    q = p1
else:
    q = p3

if p > q:
    print(0)
else:
    print(q-p+1)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    balls = {}

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1

    while len(balls.keys()) > k:
        
        minValue = 200000
        maxValue = 0

        for key, value in balls.items():
            if value < minValue and value > 0:
                minValue = value
                minKey = key
        
            if value > maxValue:
                maxValue = value
                maxKey = key
        
        balls[maxKey] += minValue
        balls.pop(minKey)

        res += minValue
    
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    balls = {}
    bucket = [[] for _ in range(n+1)]

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    for key, value in balls.items():
        bucket[value].append(key)

    for i in range(len(bucket)):
        for j in range(len(bucket[i])):
            if bucket[i] != [] and len(balls) > k:
                res += i
                balls.pop(bucket[i][j])

    print(res)

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

import numpy as np

N, M = map(int, input().split(" "))
X = [int(n) for n in input().split(" ")]

X = sorted(X)
l = []

if len(X) <= N:
	print(0)

else:
	for n in range(len(X)):
		if n != 0:
			l.append(abs(X[n - 1] - X[n]))

	ans = 0
	for i in range(M - N):
		ans += l.pop(np.argmin(l))

	print(ans)

### FIXED CODE ###

N, M = map(int, input().split(" "))
X = [int(n) for n in input().split(" ")]

X = sorted(X)

if len(X) <= N:
	print(0)

else:
	l = []
	for n in range(len(X)):
		if n != 0:
			l.append(abs(X[n - 1] - X[n]))

	ans = 0
	l = sorted(l, reverse=False)
	for i in range(M - N):
		ans += l.pop(0)

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

r,g,b,n=map(int, input().split())

r_max=n//r
g_max=n//g
b_max=n//b

sum=0

for i in range(r_max+1):
    for j in range(g_max+1):
        if (n-(i*r)-(j*g))%b==0 and (n-(i*r)-(j*g))//b>=0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)


### FIXED CODE ###

r,g,b,n=map(int, input().split())

sum=0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)