Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
import math
mod =10**9+7
import sys
sys.setrecursionlimit(10000000)

l = []
for i in range(K):
  a = math.factorial(N-K+1)/(math.factorial(N-K-i)*math.factorial(i+1))
  b = math.factorial(K-1)/(math.factorial(K-1-i)*math.factorial(i))
  ans = int(a)*int(b)
  l.append(int(ans))

for j in l:
  print(j%mod)


### FIXED CODE ###

N, K = map(int, input().split())
import math
mod =10**9+7

l = []
l.append(N-K+1)
for i in range(1, K):
  a = l[i-1] * (N-K-i+1) * (K-i) // ((i+1)*i)
  l.append(int(a))

for j in l:
  print(j%mod)
10 587586158 185430194
894597290 708587790
680395892 306946994
590262034 785368612
922328576 106880540
847058850 326169610
936315062 193149191
702035777 223363392
11672949 146832978
779291680 334178158
615808191 701464268

### FIXED CODE ###

N, H, W = map(int, input().split(" "))
count = 0
for i in range(N):
        A, B = map(int, input().split(" "))
        if A // H > 0 and B // W > 0:
                count += 1

print(count)
N = int(input())
ans = set()
for i in range(N):
    tmp = set()
    x, y, h = map(int, input().split())
    for cx in range(0,101):
        for cy in range(0, 101):
            ch = abs(x-cx) + abs(y-cy) + h
            if ch < 1 or (ch < 1 and h == 0):
                continue
            tmp.add((cx, cy, ch))
    if tmp == set():
        continue
    elif ans == set():
        ans = tmp
        continue
    ans = ans & tmp
ans = list(ans)[0]
print(ans[0], ans[1], ans[2])


### FIXED CODE ###

N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
ansx = 0
ansy = 0
ansh = 0
for x in range(101):
  for y in range(101):
    hset = set()
    for i in range(N):
      xyhi = xyh[i]
      if xyhi[2] == 0:
        continue
      hset.add(abs(xyhi[0]-x) + abs(xyhi[1]-y) + xyhi[2])

    if len(hset) == 1 and list(hset)[0] != 0:
      flag = True
      for i in range(N):
        xyhi = xyh[i]
        if xyhi[2] != 0:
          continue
        elif xyhi[2] == 0 and max(list(hset)[0] - abs(xyhi[0]-x) - abs(xyhi[1]-y), 0) == 0:
          continue
        flag = False
        break
      if flag:
        ansx = x
        ansy = y
        ansh = list(hset)[0]

print(ansx, ansy, ansh)
a = list(map(int,input().split()))
plint(a)

### FIXED CODE ###

a = list(map(int,input().split()))
b = [0, 0, 0, 0]

b[0] = a[0]*a[2]
b[1] = a[0]*a[3]
b[2] = a[1]*a[2]
b[3] = a[1]*a[3]

b.sort()

print(b[3])
l, r = map(int, input().split())

numbers = list(range(l, r+1))

if r-l>2019:
    print(0)
    exit()


amari = list(set([x%2019 for x in numbers]))


cnt = 2019
for i in range(len(amari)):
    for j in range(len(amari)):
        if i == j:
            continue
        if amari[i]*amari[j]%2019 < cnt:
            cnt = amari[i]*amari[j]%2019


print(cnt)

### FIXED CODE ###

l, r = map(int, input().split())

if r-l>2019:
    print(0)
    exit()

numbers = list(range(l, r+1))


amari = list(set([x%2019 for x in numbers]))
#print(amari)


cnt = 2019
for i in range(len(amari)):
    for j in range(len(amari)):
        if i == j:
            continue
        if amari[i]*amari[j]%2019 < cnt:
            cnt = amari[i]*amari[j]%2019


print(cnt)
import math
a,b,c,d = map(int, input().split())
cnt=0
num_c = b//c - (a-1)//c
num_d = b//d - (a-1)//d
num_c_d = b//((c*d)//math.gcd(c,d))- (a-1)//((c*d)//math.gcd(c,d))
total = num_c + num_d - num_c_d
print(int((b-a+1) - total))

### FIXED CODE ###

import fractions
a,b,c,d = map(int, input().split())
cnt=0
num_c = b//c - (a-1)//c
num_d = b//d - (a-1)//d
num_c_d = b//((c*d)//fractions.gcd(c,d))- (a-1)//((c*d)//fractions.gcd(c,d))
total = num_c + num_d - num_c_d
print(int((b-a+1) - total))
n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
dxdy = {}
for i in range(n-1):
    for j in range(i+1, n):
        dx = xy[i][0] - xy[j][0]
        dy = xy[i][1] - xy[j][1]
        if dx<0:
            dx, dy = -dx, -dy
        if (dx, dy) in dxdy:
            dxdy[(dx, dy)] += 1
        else:
            dxdy[(dx, dy)] = 1
print(n-max(dxdy.values()))

### FIXED CODE ###

n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
dxdy = {}
if n==1:
    print(1)
    exit()
for i in range(n-1):
    for j in range(i+1, n):
        dx = xy[i][0] - xy[j][0]
        dy = xy[i][1] - xy[j][1]
        if dx<0:
            dx, dy = -dx, -dy
        elif dx==0:
            dx, dy = dx, abs(dy)
        if (dx, dy) in dxdy:
            dxdy[(dx, dy)] += 1
        else:
            dxdy[(dx, dy)] = 1
print(n-max(dxdy.values()))
n,k=map(int,input().split())

a=list(map(int,input().split()))
sowa=[]
for i in range(1,n+1):
    sowa.append(sum(a[:i]))
ans=0
for i in range(n):
    if sowa[i]>=k:
        ans+=1
        for j in reversed(range(i)):
            bubun=sowa[i]-sowa[j]
            if bubun>=k:
                ans+=j+1
                break
print(ans)

### FIXED CODE ###

W,H,x,y=map(int,input().split())

max_menseki=W*H/2
if W%2==0 and W//2==x and H//2==y and H%2==0:
    print(max_menseki,"1")
else:
    print(max_menseki,"0")
case_num = 0

N = int(input())

for num in range(N - 1):
  num += 1
  
  case_num += ( math.ceil(N / num) - 1 )


print(case_num)


### FIXED CODE ###

import math

case_num = 0

N = int(input())

for num in range(N - 1):
  num += 1
  
  case_num += ( math.ceil(N / num) - 1 )


print(case_num)
a,b = map(int,input().split())
print(max[a+b,a-b,a*b])

### FIXED CODE ###

a,b = map(int,input().split())
print(max(a+b,a-b,a*b))
while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break
    count = 0
    for s in range(1, n???+ 1):
       for m in range(s + 1, n):
          for e in range(m + 1, n + 1):
            if x == sum([s, m, e]):
                     count += 1

    print(count)

### FIXED CODE ###

while True:
    n, x = [int(i) for i in input().split()]

    if n == x == 0:
        break

    count = 0
    for s in range(1, n+1):
        for m in range(s+1, n):
            for e in range(m+1, n+1):
                if x == sum([s, m, e]):
                    count += 1

    print(count)
def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1) % mod


mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
fact = factorial(N-1)

ans = 0
for k in range(2, N):
    ans = (ans + x[k] * (1 - mod_inverse(k)))

for k in range(1, N-1):
    ans = (ans - x[k] * (1 - mod_inverse(N-k))) % mod

ans = ans * fact % mod

ans = (ans + fact * sum((x[N] - x[k]) * mod_inverse(N-k) for k in range(1, N))) % mod

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)


def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1) % mod


mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
fact = factorial(N-1)

ans = 0
for k in range(2, N):
    ans = (ans + x[k] * (1 - mod_inverse(k)))

for k in range(1, N-1):
    ans = (ans - x[k] * (1 - mod_inverse(N-k))) % mod

ans = ans * fact % mod

ans = (ans + fact * sum((x[N] - x[k]) * mod_inverse(N-k) for k in range(1, N))) % mod

print(ans)
N,A =map(int,input().split())
M = N//500
if M >= A:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
a = int(input())
 
if n % 500  <=a:
  print("Yes")
else:
  print("No")
s = input()
K = int(input())


sub_string = []
for i in range(len(s)):
    for j in range(0, len(s) + 1 - i):
        sub_string.append(s[i:i+j])

#重複の排除
sub_string = set(sub_string)
#辞書順にソートする
sub_string = sorted(sub_string)
#空白を削除
sub_string.remove('')
print(sub_string[K - 1])

### FIXED CODE ###

s = input()
K = int(input())


sub_string = []
for i in range(len(s)):
    for j in range(0, len(s) + 1 - i):
        if j > K:
            break
        sub_string.append(s[i:i+j])

#重複の排除
sub_string = set(sub_string)
#辞書順にソートする
sub_string = sorted(sub_string)
#空白を削除
sub_string.remove('')
print(sub_string[K - 1])
"""
1,2,3,4,5,6,7,8,9
2,5,5,4,5,6,3,7,6

"""

v=[None,2,5,5,4,5,6,3,7,6]

N,M=map(int, input().split())
A=sorted(map(int, input().split()), reverse=True)

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

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))


### FIXED CODE ###

v=[-1,2,5,5,4,5,6,3,7,6]

N,M=map(int, input().split())
A=sorted(map(int, input().split()), reverse=True)

dp=[0]*(N+999)
mp=[[] for _ in range(N+999)]

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))
N,X = [int(i) for i in input().split()]
xa = [int(i) for i in input().split()]
from math import gcd
lia = [0]*N
for i in range(N):
    lia[i] = abs(X-xa[i])
ans = lia[0]
for i in range(1,N):
    ans = gcd(ans,lia[i])
print(ans)

### FIXED CODE ###

import fractions
N,X = map(int,input().split())
x = list(map(int,input().split()))
distance = []
for i in range(N) :
    d = abs(x[i] - X)
    distance.append(d)
s = 1000000001
if N == 1 :
    s = distance[0]
else :
    for i in range(0,N-1) :
        s = min(fractions.gcd(distance[i],distance[i+1]),s)
print(s)
a,b = input(),input()

if a*b%2:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

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

if a*b % 2 ==0:
  print("Even")
else:
  print("Odd")
"""
A高橋体力
B高橋攻撃力
C青木体力
D青木攻撃力
"""
 
a,b,c,d=map(int, input().split())
 
while(true):
	c=c-b
  	if c<=0:
  		print("Yes")
  		break
	a=a-d
  	if a<=0:
  		print("No")
  		break

### FIXED CODE ###


a, b, c, d = map( int, input().split() )
#print( a, b, c, d )
 
for i in range( 200 ):
    c = c - b
    if c <= 0:
        print( "Yes" )
        exit()
 
    a = a - d
    if a <= 0:
        print( "No" )
        exit()
DEBUG = True

import time

N, K = map(int, input().split())
A = [int(i)-1 for i in input().split()]

visited = [False] * N
next = A[0]
visited[0] = True
K -= 1
while not visited[next]:
    if DEBUG:
        print("K: {}, next: {}".format(K, next))
        print("visited: {}".format(visited))
        time.sleep(0.1)
    if K == 0:
        print(next+1)
        exit()
    visited[next] = True
    next = A[next]
    K -= 1

K -= 1
now = next
count = 1
next = A[next]
while now != next:
    next = A[next]
    count += 1
if DEBUG:
    print("count: {}".format(count))

K %= count

if DEBUG:
    print("now: {}, count: {}, K: {}".format(now, count, K))

while K > 0:
    if DEBUG:
        print("now: {}".format(now))
    now = A[now]
    K -= 1

print(A[now]+1)


### FIXED CODE ###

DEBUG = False

N, M, X = map(int, input().split())
A = []
C = []
for _ in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    A.append(CA[1::])

if DEBUG:
    print(A)
    print(C)

max_money = 10**5 * N + 1
ans_money = max_money
# ans_algorythm = None
for i in range(2**N):
    bit = bin(i)[2::]
    bit = bit.zfill(N)
    if DEBUG:
        print("i: {}, bit: {}".format(i, bit))
    tmp_money = 0
    tmp_algorythm = [0] * M
    for j, b in enumerate(bit):
        if b == '1':
            tmp_money += C[j]
            for k, c in enumerate(A[j]):
                tmp_algorythm[k] += c
    if DEBUG:
        print("tmp_money: {}, tmp_algorythm: {}".format(tmp_money, tmp_algorythm))
    if len(list(filter(lambda x: x < X, tmp_algorythm))) == 0:
        ans_money = min(tmp_money, ans_money)
        if DEBUG:
            print("ans_money: {}".format(ans_money))
        # break

if ans_money == max_money:
    print(-1)
else:
    print(ans_money)
import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
d=[]
for i in range(m):
  b,c=map(int,input().split())
  d.append([b,c])
d=sorted(d, key=lambda x: x[1], reverse=True)
i=0
j=d[0][1]
k=0
while a[i]<j and i<n:
  a[i]=j
  d[k][0]-=1
  if d[k][0]==0:
    k+=1
    j=d[k][1]
  i+=1
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
d=[]
for i in range(m):
  b,c=map(int,input().split())
  d.append([b,c])
d=sorted(d, key=lambda x: x[1], reverse=True)
i=0
j=d[0][1]
k=0
while a[i]<j:
  a[i]=j
  d[k][0]-=1
  if d[k][0]==0:
    k+=1
    if k==m:
      break
    else:
      j=d[k][1]
  i+=1
  if i==n:
    break
print(sum(a))
# -*- coding: utf-8 -*-
def check(a, time):
  ret, mod = divmod(time, a)
  value = False if mod > 0 else check(a, ret) if ret >= a else True
  return value


a, b, t, biscuit = map(int, input().split() + ["0"])
for i in range(1, t + 1):
  if check(a, i):
    biscuit = biscuit + b

print(biscuit)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def check(a, time):
  ret, mod = divmod(time, a)
  value = True if mod == 0 else check(a, ret) if ret > a else False
  return value


a, b, t, biscuit = map(int, input().split() + ["0"])
for i in range(1, t + 1):
  if check(a, i):
    biscuit = biscuit + b

print(biscuit)
from collections import deque

n = int(input())
ops = [tuple(input().split()) for i in range(n)]

ary = deque([])


def insert(ary, x):
    ary.appendleft(x)


def delete(ary, x):
    if x in ary:
        ind = ary.index(x)
        ary = ary[:ind] + ary[ind + 1:]


def delete_first(ary):
    ary.popleft()


def delete_last(ary):
    ary.pop()


def operate(ary, op):
    cmd = op[0]

    if cmd == 'insert':
        x = int(op[1])
        insert(ary, x)
    elif cmd == 'delete':
        x = int(op[1])
        delete(ary, x)
    elif cmd == 'deleteFirst':
        delete_first(ary)
    elif cmd == 'deleteLast':
        delete_last(ary)


[operate(ary, op) for op in ops]
print(' '.join([str(_) for _ in ary]))



### FIXED CODE ###

import sys
from collections import deque

n = int(input())
ary = deque([])

for line in sys.stdin:
    op = line.strip().split()
    cmd = op[0]

    if cmd == 'insert':
        x = op[1]
        ary.appendleft(x)

    elif cmd == 'delete':
        x = op[1]
        if x in ary:
            ary.remove(x)

    elif cmd == 'deleteLast':
        ary.pop()

    else:
        ary.popleft()

print(*ary)
n, m = (int(x) for x in input().split())
if m == 1: print(0)
else:
    x = [int(x) for x in input().split()]
    x.sort()
    dis = [abs(x[i+1] - x[i]) for i in range(m-1)]
    dis.sort()
    ans = dis[::-1]
    for _ in range(n-1): ans.pop(0)
    print(sum(ans))

### FIXED CODE ###

n, m = (int(x) for x in input().split())
x = [int(x) for x in input().split()]
if n >= m:
    print(0)
else:
    x.sort()
    dis = [abs(x[i+1] - x[i]) for i in range(m-1)]
    dis.sort()
    ans = dis[::-1]
    for _ in range(n-1): ans.pop(0)
    print(sum(ans))
import math
A,B,C,D = map(int,input().split())

icm = C*D / math.gcd(C,D)
ans = (B - A + 1)
if A % C == 0:
    ans -= (B // C - A // C) - 1
else:
    ans -= (B // C - A // C)
if A % D == 0:
    ans -= (B // D - A // D) - 1
else:
    ans -= (B // D - A // D)

if A % icm == 0:
    ans += (B // icm - A // icm) - 1
else:
    ans += (B // icm - A // icm)

print(int(ans))

### FIXED CODE ###

import fractions
A,B,C,D = map(int,input().split())

lcm = int(C*D / fractions.gcd(C,D))
ans_b = B - (B // C) - (B // D) + (B // lcm)
ans_a = A - 1 - ((A - 1)// C) - ((A - 1)// D) + ((A - 1) // lcm)

print(int(ans_b - ans_a))
import fractions
N = int(input())
A = [int(i) for i in input().split()]

def gcd(a,b):
    

def mygcd(A):
    if len(A) == 1:
        return A[0]
    else:
        return fractions.gcd(A[0],mygcd(A[1:]))
        
ans = []
for i in range(N):
    ans.append(mygcd(A[:i]+A[i+1:]))

print(max(ans))

### FIXED CODE ###

from fractions import gcd
#input
N = int(input())
A = [int(i) for i in input().split()]
#cluc left and right gcd 
left = [0]*N
right = [0]*N
count = 0
left[0] = A[0]
right[-1] = A[-1]
Ans = []

for i in A[1:]:
    left[count+1] = gcd(left[count],i)
    count += 1

for i in reversed(A[:-1]):
    right[count-1] = gcd(right[count],i)
    count -= 1
# make ans
Ans.append(right[1])
Ans.append(left[-2])
for i in range(N-2):
    Ans.append(gcd(left[i],right[i+2]))
print(max(Ans))
MOD = 10_0000_0007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

    for i in range(2,n+1):
        if not al[i]:
            dp[i] = dp[i-2] + dp[i-1]

    print(dp[n] % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

MOD = 1000000007

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

a = [0 for i in range(n+1)]
for i in range(m):
    a[int(input())] = 1

count = [0 for i in range(n+1)]
for i in range(1,n+1):
    if a[i] == 1:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])
import numpy as np

n = int(input())
a = np.zeros(n, dtype=np.int64)
for i in range(n):
    a[i] = int(input())
for i in range(n):
    max1 = 0
    max2 = 0
    if len(a[:i]) != 0:
        max1 = np.max(a[:i])
    if len(a[i+1:]) != 0:
        max2 = np.max(a[i+1:])
    print(max(max1, max2))


### FIXED CODE ###

n = int(input())
max1 = 0
max2 = 0
index = 0
for i in range(n):
    a = int(input())
    new_max = max(a, max1)
    if (a == new_max and max2 <= max1) or (a == new_max and max2 <= max1 and a == max1):
        max2 = max1
        index = i
    elif (a != new_max and max2 <= a) or (a != new_max and max2 <= a and a == max1):
        max2 = a
    max1 = new_max

for i in range(n):
    if i != index:
        print(max1)
    else:
        print(max2)
n,m = map(int,input().split())
A = list(map(int,input(),split()))
a = sum(A)

if n>=a:
  print(n-a)
else:
  print(-1)

### FIXED CODE ###

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

if N>=a:
  print(N-a)
else:
  print(-1)
n= int(input())
lis = list(map(int,input().split())
cou = 0
num = sum(lis)/n
for i in range(n):
  lis[i] -= num
  cou = min(cou,abs(lis[i]))
for i in range(n):
  if cou == lis[i]:
    print(i)
    exit()

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
li = []
num = sum(lis)/n
for i in range(n):li.append(abs(lis[i]-num))
print(li.index(min(li)))
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, m = (int(xi) for xi in input().split())

a = []
diff = 0
a0 = 0
a1 = 0
for xi in range(m):
    a0 = a1
    a1 = int(input())
    a.append(a1)
    if a1-a0>diff :
        diff=a1-a0

print(comb(n,diff))
print(diff)
print(a)

p = [1]
for xi in range(1,diff+1):
    p[xi] = 1
    for j in range(1, int(xi/2)):
        p[xi] += comb(xi-j,j)


### FIXED CODE ###

n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
if m>0:
    a1 = int(input())
    a.append(a1)
    diff.append(a1+1)

    if m>1:
        for xi in range(m-1):
            a0 = a1
            a1 = int(input())
            a.append(a1)
            diff.append(a1-a0)

    if a1==n-1:
        diff.append(n-a1+1)
    else:
        diff.append(n-a1+1)


else:
    if n==1: diff.append(n+1)
    diff.append(n+2)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)+2):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )
import bisect
def count_generate(h,w,a):
    count = [[0]*w for j in range(h)]
    count[0][0] = a[0][0]
    for i in range(1,w):
        count[0][i] = count[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            count[i][j] = count[i-1][j]+cnt_w
    return count

def da_calc(p,q,x,y, da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

N, K = map(int, input().split())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    
a_sorted = sorted(set(a))
b_sorted = sorted(set(b))
h = len(a_sorted)
w = len(b_sorted)

Map = [[0]*w for _ in range(h)]

for i in range(N):
    ai = bisect.bisect_left(a_sorted, a[i])
    bi = bisect.bisect_left(b_sorted, b[i])
    Map[ai][bi]+=1

count = count_generate(h, w, Map)
ans = float('inf')
for i in range(h):
    for j in range(i+1, h):
        for k in range(w):
            for l in range(k+1, w):
                #print(i, j, k, l, da_calc(i, k, j, l, count))
                if da_calc(i, k, j, l, count)>=K:
                    #print(i, j, k, l)
                    ans = min(ans, (a_sorted[j]-a_sorted[i])
                              *(b_sorted[l]-b_sorted[k]))
print(ans)

### FIXED CODE ###

import bisect
def count_generate(h,w,a):
    count = [[0]*w for j in range(h)]
    count[0][0] = a[0][0]
    for i in range(1,w):
        count[0][i] = count[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            count[i][j] = count[i-1][j]+cnt_w
    return count

def da_calc(p,q,x,y, da):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

N, K = map(int, input().split())
a = []
b = []
for i in range(N):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    
a_sorted = sorted(set(a))
b_sorted = sorted(set(b))
h = len(a_sorted)
w = len(b_sorted)

Map = [[0]*w for _ in range(h)]

for i in range(N):
    ai = bisect.bisect_left(a_sorted, a[i])
    bi = bisect.bisect_left(b_sorted, b[i])
    Map[ai][bi]+=1

count = count_generate(h, w, Map)
ans = float('inf')
for i in range(h):
    for j in range(i+1, h):
        for k in range(w):
            for l in range(k+1, w):
                #print(i, j, k, l, da_calc(i, k, j, l, count))
                if da_calc(i, k, j, l, count)>=K:
                    #print(i, j, k, l)
                    ans = min(ans, (a_sorted[j]-a_sorted[i])
                              *(b_sorted[l]-b_sorted[k]))
print(ans)
import math
N,K=map(int,input().split())

def combinations_count(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

for i in range(1,K+1):
    print(combinations_count(N-K+1,i)*combinations_count(K-1,i-1))

### FIXED CODE ###

import math
N,K=map(int,input().split())

def combinations_count(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

for i in range(1,K+1):
    if N-K+1>=i:
        print((combinations_count(N-K+1,i)*combinations_count(K-1,i-1))%(10**9+7))
    else:
        print(0)
S = input()
N = input()
N = int(N/2)
S1 = S[:N]
S2 = S[N:]

if S1 == S2:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = int(input())
S = input()

n = int(N/2)
s1 = S[:n]
s2 = S[n:]

if s1 == s2:
    print('Yes')
else:
    print('No')
n=int(input())
s=[input() for i in range(1,n+1)]
dic={}
l=list()
cnt=0
for i in range(n):
  s[i].sort()
  s=''.join(s[i])
  l.append(s)
  if l[i] in dic:
    cnt+=1
  else:
    dict[l[i]]=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=[input() for i in range(n)]
dic={}
l=list()
cnt=0
for i in range(n):
  k=sorted(s[i])
  t=''.join(k)
  l.append(t)
  if l[i] in dic:
    dic[l[i]]+=1
  else:
    dic[l[i]]=0
c=list(dic.values())
for i in range(len(c)):
   cnt+=c[i]*(c[i]+1)//2
print(cnt)