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

n = int(input())
S = [input() for i in range(n)]

P = list(set(S))
ANS1 = []
ANS2 = []
for i in range(len(P)):
  ANS1.append([S.count(P[i]), P[i]])
  ANS2.append(S.count(P[i]))
  
M = max(ANS2)
ANS = []
for i in range(len(ANS1)):
  if ANS1[i][0] == M:
    ANS.append(ANS1[i][1])
  else:
    pass
  
ANS.sort()
for i in range(len(ANS)):
  print(ANS[i])

### FIXED CODE ###

from collections import Counter
n = int(input())
S = [input() for i in range(n)]
L = Counter(S).most_common()
ans = []
for i in range(len(L)):
  if L[i][1] == L[0][1]:
    ans.append(L[i][0])
  else:
    break
ans.sort()
for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)+1):
    left = s[0:i]
    right = s[i:]
    l = 0
    r = 0
    for i in range(len(left)-1,-1,-1):
        if left[i] != "<":
            break
        else:
            l += 1
    for i in range(len(right)):
        if right[i] != ">":
            break
        else:
            r += 1
    ans += max(l,r)
print(ans)


### FIXED CODE ###

from itertools import *
s = input()
g = [[k,len(list(v))] for k,v in groupby(s)]
ans = 0
for command,length in g:
    ans += length*(length+1)//2
for i in range(len(g)-1):
    if g[i][0] == "<":
        ans -= min(g[i][1],g[i+1][1])
print(ans)
### BUGGY CODE ###

def gcd(a,b):
    r0=a
    r1=b
    while True:
        r2=r0%r1
        if r2==0:break
        r0=r1
        r1=r2
    return(r1)

K=int(input())
tot=0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp=gcd(i,j)
        for k in range(1,K+1):
            tot+=gcd(tmp,k)
            
print(tot)

### FIXED CODE ###

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

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*(max(a)+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,max(a)+1,i):
        b[j]+=1
ans=0
for i in a:
    ans+=(1 if b[i]==1 else 0)
print(ans)

### FIXED CODE ###

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
ma=max(a)
b=[0]*(ma+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,ma+1,i):
        b[j]+=1
ans=0
for i in a:
    if b[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()
S = input()

ans = 0

for i in range(1000):
    x = str(i).zfill(3)
    idx = 0
    for s in S:
        if x[idx] == s:
            idx += 1
        if idx == 3:
            break
    if idx == 3:
        ans += 1
print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()
S = input()

s = set([""])
for n in S[::-1]:
	s |= set(x+n for x in s if len(x) != 3)

print(len([x for x in s if len(x) == 3]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def dfs(v, e, visited, dp):
    if v not in visited:
        if not e[v]:
            dp[v] = 0
        for next_v in e[v]:
            yield from dfs(next_v, e, visited, dp)
        visited.add(v)
        yield v


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    e_ = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        e_[v].append(u)
    topological_sorted = []
    visited = set()
    dp = [-1]*N
    for v in range(N):
        topological_sorted += list(dfs(v, e, visited, dp))
    for v in topological_sorted:
        for other_side in e_[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    input_edges = [0]*N
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        input_edges[v] += 1
    queue = deque()
    dp = [-1] * N
    for i, input_edge in enumerate(input_edges):
        if input_edge == 0:
            queue.appendleft(i)
            dp[i] = 0
    topological_sorted = []
    while queue:
        v = queue.pop()
        topological_sorted.append(v)
        for other_side in e[v]:
            input_edges[other_side] -= 1
            if input_edges[other_side] == 0:
                queue.appendleft(other_side)
    for v in topological_sorted:
        for other_side in e[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    c = Counter(A)
    l = [0 for _ in range(2 * (10**5) + 7)]
    h = [0 for _ in range(2 * (10**5) + 7)]

    for k, v in c.items():
        l[k] = len(list(combinations(range(v-1), 2)))
        h[k] = len(list(combinations(range(v), 2)))

    for a in A:
        ans = sum(h) - h[a] + l[a]
        print(ans) 


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    C = Counter(A)

    X = 0
    for v in C.values():
        X += v * (v - 1) // 2

    for i in range(N):
        print(X - C[A[i]] + 1)


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

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7

lcm = 1
for i in range(n):
  lcm = lcm * a[i] // gcd(lcm, a[i])

sum_b = 0
for i in range(n):
  sum_b = (sum_b + lcm // a[i]) % mod
print(sum_b)

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7

lcm = 1
for i in range(n):
  lcm = lcm * a[i] // gcd(lcm, a[i])
lcm %= mod

sum_b = 0
for i in range(n):
  sum_b = (sum_b + lcm * pow(a[i], mod - 2, mod)) % mod
print(sum_b)
### BUGGY CODE ###

import sys
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = [] 

def maxHeapify(i):
    global a, h
    l = 2 * i
    r = 2 * i + 1
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print("\n".join([str(s) for s in ret]))
        # print()

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

import numpy as np
from functools import reduce

N, M, K = list(map(int, input().split()))
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

cumA = reduce(lambda x, y: x + [y + x[-1]], As, [0])
cumB = reduce(lambda x, y: x + [y + x[-1]], Bs, [0])
cumA.append(np.inf)
cumB.append(np.inf)
cumA = np.array(cumA)
cumB = np.array(cumB)

max_count = 0
a_thresh = np.where(cumA > K)[0][0]
a_count = a_thresh
b_count = 0
b_thresh = np.where(cumB > K)[0][0]
while a_count >= 0 and b_count <= b_thresh:
    while b_count <= b_thresh and cumA[a_count] + cumB[b_count] <= K:
        b_count += 1
    b_count = max(0, b_count - 1)
    if cumA[a_count] + cumB[b_count] <= K:
        max_count = max(max_count, a_count + b_count)
    a_count -= 1

print(max_count)


### FIXED CODE ###

import numpy as np
from functools import reduce

N, M, K = list(map(int, input().split()))
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))


def get_cum(arr):
    cum_arr = [0]
    for e in arr:
        tot = cum_arr[-1] + e
        if tot > K:
            return cum_arr
        cum_arr.append(tot)
    return cum_arr


cumA = get_cum(As)
cumB = get_cum(Bs)

max_count = 0
a_thresh = len(cumA) - 1
a_count = a_thresh
b_count = 0
b_thresh = len(cumB) - 1
while a_count >= 0 and b_count <= b_thresh:
    while b_count <= b_thresh and cumA[a_count] + cumB[b_count] <= K:
        b_count += 1
    b_count = max(0, b_count - 1)
    if cumA[a_count] + cumB[b_count] <= K:
        max_count = max(max_count, a_count + b_count)
    a_count -= 1

print(max_count)
### BUGGY CODE ###

import collections


def main():
    max_n = 10**18
    n = int(input())
    a = input_list()
    ans = 1
    for v in a:
        ans *= v
    if ans > max_n:
        print(-1)
    else:
        print(ans)


def input_list():
    return list(map(int, input().split()))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#import numpy
import math
import sys

def main():
    n = int(input())
    a = sorted(input_list())
    max_n = 10 ** 18
    ans = 1
    for v in a:
        ans *= v
        if ans > max_n:
            ans = -1
            break
        if ans == 0:
            break
    print(ans)


def yogen(a, b, angle):
    coss = math.cos((angle/180)*math.pi)
    return math.sqrt(a**2 + b**2 - 2*a*b*coss)


def get_angle(hour, minute):
    h = (hour * 360) / 12 + (minute * 360) / (12 * 60)
    m = (minute * 360) / 60
    angle = abs(h-m)
    return min(angle, 360-angle)

def has(v, l):
    for vl in l:
        if v == vl:
            return True
    return False

def input_list():
    return list(map(int, sys.stdin.readline().split()))


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

N = int(input())
names = list()
for i in range(N):
  names.append(input())
res_dict = dict()
for i in names:
  count = names.count(i)
  res_dict[i] = count
res_name = []
for i in res_dict.keys():
  if res_dict[i] == max(res_dict.values()):
    res_name.append(i)
res_name = sorted(res_name)
for i in res_name:
  print(i)

### FIXED CODE ###

N = int(input())
words = {}
for i in range(N):
  name = input()
  if name not in words:
    words[name] = 1
  elif name in words:
    words[name] += 1
    
res_name = []
Max = max(words.values())
for i in words.keys():
  if words[i] == Max:
    res_name.append(i)
res_name = sorted(res_name)
for i in res_name:
  print(i)
### BUGGY CODE ###

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

for i in range(max(a, b)):
	if abs(a - i) == abs(b - i):
		print(i)
		exit()

print("IMPOSSIBLE")



### FIXED CODE ###

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

if (a + b) % 2 == 0:
	print((a + b) // 2)
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

k = int(input())
ans = 0
 
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
 
for i in range(k):
  for j in range(k):
    for l in range(k):
      ans += gcd(gcd(i+1, j+1),l+1)
      
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input()) + 1
ans = 0
for i in range(1,k):
  for j in range(1,k):
    for l in range(1,k):
      ans += gcd(gcd(i, j),l)
print(ans)
### BUGGY CODE ###

MAX_A = 10**6 + 1

def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    C = [0] * MAX_A
    for a in A:
        for p, c in factorize(a): C[p] += 1
    max_c = max(C)
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')


### FIXED CODE ###

n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')
### BUGGY CODE ###

#ゴーレム判定函数
#pos=位置
#s=文字列
def survive(pos,s,spell,move,N):
    for i in range(0,len(spell)):
        if(s[pos]==spell[i]):
            pos+=move[i]
        #ゴーレムが消えたか判定
        if(pos<0 or pos>N-1):
            return False
    return True
    
N,Q=map(int,input().split())
s=str(input())
tmp1=""
tmp2=""
tmp=0
#AとかBとかそういう奴らがどのくらい動くのかをカウント
spell=[]
move=[]
for time in range(0,Q):
    tmp1,tmp2=map(str,input().split())
    spell.append(tmp1)
    if(tmp2=="L"):
        move.append(-1)
    elif(tmp2=="R"):
        move.append(1)
left=-1
right=-1
#上と下から探す
for i in range(0,N):
    if(survive(i,s,spell,move,N)):
        left=i
        break
for j in range(0,N):
    if(survive(N-1-j,s,spell,move,N)):
        right=N-1-j
        break
ans=0
if(left<0 and right<0):
    ans=0
else:
    ans=right-left+1
print(ans)

### FIXED CODE ###

#ゴーレム判定関数
#pos=位置
#s=文字列
def survive(pos,s,spell,move,N):
    for i in range(0,len(spell)):
        if(s[pos]==spell[i]):
            pos+=move[i]
        #ゴーレムが消えたか判定
        if(pos<0):
            return -1
        elif(pos>N-1):
            return 1
    return 0

N,Q=map(int,input().split())
s=str(input())
tmp1=""
tmp2=""
tmp=0
#AとかBとかそういう奴らがどのくらい動くのかをカウント
spell=[]
move=[]
for time in range(0,Q):
    tmp1,tmp2=map(str,input().split())
    spell.append(tmp1)
    if(tmp2=="L"):
        move.append(-1)
    elif(tmp2=="R"):
        move.append(1)
left_result=-1
right_result=N
#右にoutしていくやつのうちもっとも左のやつを探す
left=0
right=N-1
mid=0
judge=False
#何も右から出ていかないパターン
if(survive(N-1,s,spell,move,N)!=1):
    right_result=N
#全て右から出ていくパターン
elif(survive(0,s,spell,move,N)==1):
    right_result=0
else:
    while ((right+left)//2)!=mid:
        mid=(right+left)//2
        judge=survive(mid,s,spell,move,N)
        if(judge==1):
            right=mid
        else:
            left=mid
    right_result=right

#左にoutしていくやつのうちもっとも右のやつを探す
left=0
right=N-1
mid=0
judge=False
#何も左から出ていかないパターン
if(survive(0,s,spell,move,N)!=-1):
    left_result=-1
#全て左から出ていくパターン
elif(survive(N-1,s,spell,move,N)==-1):
    left_result=N-1
else:
    while ((right+left)//2)!=mid:
        mid=(right+left)//2
        judge=survive(mid,s,spell,move,N)
        if(judge==-1):
            left=mid
        else:
            right=mid
    left_result=left

ans=right_result-left_result-1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9) #上限を１００万回に設定

N, K = map(int, input().split())
h = list(map(int, input().split()))
f_INF = float('inf')
dp = [f_INF]*N
dp[0] = 0
for i in range(N):
    for j in range(1,min(K+1, N-i)):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
p = sorted(list(map(int, input().split())))
mid = n // 2
ans = 0
for i in range(p[mid-1], p[mid]):
  if len([j for j in p if j > i]) == (n//2):
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = sorted(list(map(int, input().split())))
mid = n // 2
print(p[mid] - p[mid-1])
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = defaultdict(list)
    len_ = defaultdict(int)
    for i, s in enumerate(S):
        rgb[s].append(i)
        len_[s] += 1

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()


### FIXED CODE ###

from bisect import bisect
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    S = input()

    rgb = {'R': [], 'G': [], 'B': []}
    for i, s in enumerate(S):
        rgb[s].append(i)

    def count_(s1, s2):
        ret = 0
        x = bisect(rgb[s1], i)
        for j in rgb[s1][x:]:
            y = bisect(rgb[s2], j)
            d = j - i
            if j + d < N and S[j+d] == s2:
                ret += len_[s2] - y - 1
            else:
                ret += len_[s2] - y
        return ret

    ans = 0
    len_ = {'R': len(rgb['R']), 'G': len(rgb['G']), 'B': len(rgb['B'])}
    for i, s in enumerate(S):
        if s == 'R':
            for s1, s2 in (('G', 'B'), ('B', 'G')):
                ans += count_(s1, s2)
        elif s == 'G':
            for s1, s2 in (('R', 'B'), ('B', 'R')):
                ans += count_(s1, s2)
        else:
            for s1, s2 in (('R', 'G'), ('G', 'R')):
                ans += count_(s1, s2)
    print(ans)


main()
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]
Z = [int(i) for i in input().split()]
X.sort(reverse=1)
Y.sort(reverse=1)
Z.sort(reverse=1)

answer = []

for i in range(min(x,k)):
    for j in range(min(y,k)):
        for l in range(min(z,k)):
            if (i+1) * (j+1) * (l+1) <= k:
                answer.append(X[i]+Y[j]+Z[l])

answer.sort(reverse=1)

for p in answer[:k]:
    print(p)

### FIXED CODE ###

x, y, z, k = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]
Z = [int(i) for i in input().split()]
X.sort(reverse=1)
Y.sort(reverse=1)
Z.sort(reverse=1)

answer = [i+j for i in X[:k] for j in Y[:k]]
answer.sort(reverse=1)

answer2 = [i+j for i in Z[:k] for j in answer[:k]]
answer2.sort(reverse=1)

for p in answer2[:k]:
    print(p)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

mod = 10**9 + 7

A.sort()
# print(A)

def cmb(n, r):
    from operator import mul
    from functools import reduce

    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


ans = 0
for i in range(N):
    if N - i - 1 >= K-1:
        num = cmb(N-i-1, K-1)
        if A[i] * num < 0:
            ans += (-A[i] * num) % mod
        else:
            ans -= (A[i] * num) % mod
        # print(f'-: {i}, {num}, {A[i]}')
    if i >= K-1:
        num = cmb(i, K-1)
        if A[i] * num < 0:
            ans -= (-A[i] * num) % mod
        else:
            ans += (A[i] * num) % mod
        # print(f'+: {i}, {num}, {A[i]}')

print(ans % mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# E

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mod = 10**9 + 7


class Cmb(object):
    def cmb_precalc(self, n, r, mod: int = 10 ** 9 + 7):
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  # 元テーブル
        self.g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

        for i in range(2, N + 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)


ans = 0
cmb = Cmb()
cmb.cmb_prep(N + 5)

for i in range(N):
    if i >= K-1:
        ans += A[i] * cmb.cmb_precalc(i, i-K+1)
    if N - i - 1 >= K-1:
        ans -= A[i] * cmb.cmb_precalc(N-i-1, K-1)

print(ans % mod)