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

import sys
readline = sys.stdin.readline
N = int(readline())
L = list(map(int, readline().split()))

ans = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                continue
            if (L[i] < L[j] + L[k]) and (L[j] < L[k] + L[i]) and (L[k] < L[i] + L[j]):
                ans += 1

print(ans//6)

### FIXED CODE ###

import sys
import bisect
readline = sys.stdin.readline
N = int(readline())
L = list(map(int, readline().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(i, N):
        if i == j: continue
        ab = L[i] + L[j]
        to = bisect.bisect_left(L, ab, j, N)
        ans += to - 1 - j
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
treat = list(map(int, input().split()))

print(len([(n, m) for n in range(N) \
        for m in range(n, N) if sum(treat[n:m+1]) % M == 0]))


### FIXED CODE ###

from collections import Counter
N, M = map(int, input().split())
A = list(map(lambda x:int(x)%M, input().split()))
B = A[:]
for i in range(N-1):
    B[i+1] += B[i]
    B[i+1] %= M
c = Counter(B)


ans = 0
for k, v in c.items():
    if k == 0:
        ans += v
    if v >= 2:
        ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

l,r=map(int,input().split())
t=[]
for i in range(l,r):
    for j in range(i+1,r+1):
        t.append((i*j)%2019)
        if 0 in t:
            print(0)
            exit()
print(min(t))

### FIXED CODE ###

l,r=map(int,input().split())
minimum=2019
for i in range(l,r):
    for j in range(i+1,r+1):
        tmp=(i*j)%2019
        if minimum>tmp:
            minimum=tmp
        if minimum==0:
            print(0)
            exit()
print(minimum)
### BUGGY CODE ###

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

num_r, num_g = S.count('R'), S.count('G')
num_b = N - num_r - num_g
max_ans = num_r * num_g * num_b
count_not_ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2 * j - i
        if (0 <= k <= N-1) and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            count_not_ans += 1

print(max_ans - count_not_ans)


### FIXED CODE ###

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

num_r, num_g = S.count('R'), S.count('G')
num_b = N - num_r - num_g
max_ans = num_r * num_g * num_b
count_not_ans = 0
S = list(S)

for i in range(N):
    for j in range(i+1, N):
        k = 2 * j - i
        if (0 <= k <= N-1) and len(set([S[i], S[j], S[k]])) == 3:
            count_not_ans += 1

print(max_ans - count_not_ans)
### BUGGY CODE ###

import math

def getPrimeFactorsList(num):
  pn = 2 #素数は2から
  pflist = [] #素因数のリスト
  while pn * pn <= num: #√numまで調べる
    while num % pn == 0: #現在の素数で割り切れる範囲でループ
      num = num / pn
      pflist.append(pn)
    pn += 1 #割り切れなくなったら次の素数へ
  if num > 1:
    pflist.append(int(num))
    
  return pflist
mod = (10 ** 9 + 7)
N = int(input())
ans = 0
num = math.factorial(N)
#print(num)
for i in range(1, num+1):
  count = 1
  pflist = getPrimeFactorsList(i)
  pfset = set(pflist)
  for j in pfset:
    count *= (pflist.count(j) + 1)
  #print("-----")
  #print(count)
  #print("-----")
  ans += count
  
print(count % mod) 

### FIXED CODE ###

def getPrimeFactorsList(num):
  pn = 2 #素数は2から
  pflist = [] #素因数のリスト
  while pn * pn <= num: #√numまで調べる
    while num % pn == 0: #現在の素数で割り切れる範囲でループ
      num = num / pn
      pflist.append(pn)
    pn += 1 #割り切れなくなったら次の素数へ
  if num > 1:
    pflist.append(int(num))
  return pflist

mod = (10 ** 9 + 7)
N = int(input())
ans = 0


pf_dict = {}
#素因数がキー、割れる回数を値として用意し、最後に約数の個数を求める
for i in range(2, N+1):

  pflist = getPrimeFactorsList(i)
  pfset = set(pflist)
  for j in pfset:
    if j in pf_dict:
      pf_dict[j] += pflist.count(j)
    else:
      pf_dict[j] = pflist.count(j)
    #count *= (pflist.count(j) + 1)
  
count = 1
for v in pf_dict.values():
  count *= (v + 1)
print(count % mod)
### BUGGY CODE ###

K, S = [int(n) for n in input().split(" ")]
 
cnt = 0
 
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        cnt +=1
 
print(cnt)

### FIXED CODE ###

K, S = [int(n) for n in input().split(" ")]
 
cnt = 0
 
for x in range(K+1):
  for y in range(K+1):
      if S-x-y <= K and S-x-y >= 0:
            
        cnt +=1
 
print(cnt)
### BUGGY CODE ###

n = int(input())

def make_charcount(word):
    charcount = {}
    for c in word:
        if c not in charcount:
            charcount[c] = 1
        else:
            charcount[c] += 1
    return charcount

charcount_list_index = 0
charcount_list = {}
same_log = {}

for i in range(n):
    word = input()
    this_charcount = make_charcount(word)
    index = -1
    for i in charcount_list:
        if charcount_list[i] == this_charcount:
            index = i
            break
    if index != -1:
        if index not in same_log:
            same_log[index] = 1
        else:
            same_log[index] += 1
    else:
        charcount_list[charcount_list_index] = this_charcount
        charcount_list_index += 1

result = 0
for index in same_log:
    cnt = same_log[index]
    result += int(cnt*(cnt+1)/2)
print(result)

### FIXED CODE ###

n = int(input())

result = 0
word_list = {}

for i in range(n):
    input_word = "".join(sorted(input()))
    flag = 1
    if input_word in word_list:
        word_list[input_word] += 1
        result += word_list[input_word]
        flag = 0
    else:
        word_list[input_word] = 0

print(result)
### BUGGY CODE ###

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

ans = 1
for i in alist:
    ans *= i
    
if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in alist:
    ans = 0
else:
    for i in alist:
        ans *= i
        if ans > 10**18:
            ans = -1
            break

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

import queue
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, V):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    q = queue.Queue()
    q.put(s)

    while not q.empty():
        u = q.get()
        color[u] = BLACK

        for v in V[u]:
            if color[v] != BLACK and d[v] == INFTY:
                d[v] = d[u] + 1
                color[v] = GRAY
                q.put(v)

    return d

def rec(s, i, depth):
    if depth == 3:
        if is_visited[i]:
            return
        kkpgraph[s].append(i)
        is_visited[i] = True
        return
    if not graph[i]:
        return
    for node in graph[i]:
        rec(s, node, depth+1)
    return

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
kkpgraph = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
S, T = map(int, input().split())
for i in range(1, N+1):
    is_visited = [False for i in range(N+1)]
    rec(i, i, 0)
d = dijkstra(S, kkpgraph)
if d[T] == INFTY:
    print(-1)
else:
    print(d[T])


### FIXED CODE ###

import queue
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def bfs(s, V):
    color = [[WHITE for i in range(N+1)] for j in range(3)]
    d = [[INFTY for i in range(N+1)] for j in range(3)]
    d[0][s] = 0
    q = queue.Queue()
    q.put((0, s))
    
    while not q.empty():
        dv, u = q.get()
        color[dv%3][u] = BLACK

        for v in V[u]:
            if color[(dv+1)%3][v] != BLACK and d[(dv+1)%3][v] == INFTY:
                d[(dv+1)%3][v] = d[dv%3][u] + 1
                q.put((d[(dv+1)%3][v], v))

    return d

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
S, T = map(int, input().split())
d = bfs(S, graph)
if d[0][T] == INFTY:
    print(-1)
else:
    print(d[0][T]//3)
### BUGGY CODE ###

# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b(= k) を維持して計算していく
memo = {}
for i in range(N):
    for j in range(i, N):
        # k = N を条件判定するコストが無駄なので事前計算
        memo[i, j, N] = +(r_min[N] <= i <= r_max[N] and g_min[N] <= j <= g_max[N])
def dfs(*key):
    r, g, k = key
    if key in memo:
        return memo[key]
    if not (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k]):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(g, k, k+1) + dfs(r, k, k+1) + dfs(r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0))


### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

X,Y,Z,K=[int(s) for s in input().split()]
xls=sorted([int(s) for s in input().split()],reverse=True)
yls=sorted([int(s) for s in input().split()],reverse=True)
zls=sorted([int(s) for s in input().split()],reverse=True)
xyls=[]
for x in xls[:K]:
  for y in yls[:K]:
    xyls.append(x+y)
xyls=sorted(xyls,reverse=True)
cake=[]
for xy in xyls[:K]:
  for z in zls[:K]:
    cake.append(xy+z)
cake=sorted(cake,reverse=True)
for i in range(K):
  print(cake[i])

### FIXED CODE ###

X,Y,Z,K=[int(s) for s in input().split()]
xls=sorted([int(s) for s in input().split()],reverse=True)
yls=sorted([int(s) for s in input().split()],reverse=True)
zls=sorted([int(s) for s in input().split()],reverse=True)
xyls=[]
for x in xls[:K]:
  for y in yls[:K]:
    xyls.append(x+y)
xyls=sorted(xyls,reverse=True)
cake=[]
for xy in xyls[:K]:
  for z in zls[:K]:
    cake.append(xy+z)
cake=sorted(cake,reverse=True)
for i in range(K):
  print(cake[i])
### BUGGY CODE ###

li = list(map(int,input().split()))
N = li[0]
K = li[1]
Q = li[2]
score = [K] * N
for i in range(Q):
    A_i = int(input())
    A_i -= 1
    score = map (lambda x: x - 1, score)
    score = list(score)
    score[A_i] += 1
index_num = 0
for i in range(N):
    if score[index_num] <= 0:
        print("No")
    else:
        print("Yes")
    index_num += 1

### FIXED CODE ###

li = list(map(int,input().split()))
N = li[0]
K = li[1]
Q = li[2]
score = [K] * N
for i in range(Q):
    A_i = int(input())
    A_i -= 1
    score[A_i] += 1
score = map(lambda x: x - Q, score)
score = list(score)
index_num = 0
for i in range(N):
    if score[index_num] <= 0:
        print("No")
    else:
        print("Yes")
    index_num += 1
### BUGGY CODE ###

# coding: utf-8
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = list(map(lambda x: x * (x + 1) / (2 * x), p))

ans = 0
for i in range(n - k + 1):
    tmp = sum(p[i: i + k])
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

# coding: utf-8
n, k = map(int, input().split())
p = list(map(int, input().split()))
res = [0]
ra = res.append
for i in range(n):
    ra(p[i] + res[i])

ans = 0
for i in range(n - k + 1):
    tmp = res[i + k] - res[i]
    if ans < tmp:
        ans = tmp

print((ans + k) / 2)
### BUGGY CODE ###

from collections import Counter

S = input()
ans = 0
# i + 1文字目以降の数字列を2019で割った余りをdp[i]とするとdp[i - 1] == dp[j](mod 2019)の時(i, j)が条件を満たす
N = len(S)
mod = 2019
dp = [0] * (N + 1)
for i in range(N, -1, -1):
    if i == N:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + (10 ** (N - i - 1)) * int(S[i])) % mod

count = Counter(dp).most_common()
for k, v in count:
    if v > 1:
        ans += v * (v - 1) // 2
print(ans)

### FIXED CODE ###

from collections import defaultdict


def solve(input_s: str):
    ans = 0
    n = len(input_s)
    mod = 2019
    dp = defaultdict(int)
    cur = 0
    for i in range(n, -1, -1):
        if i == n:
            dp[0] += 1
        else:
            # cur += ((10 ** (n - i - 1)) * int(input_s[i])) % mod これはnがでかくなるとめちゃめちゃ遅い
            cur += pow(10, n - i - 1, 2019) * int(input_s[i]) % mod
            cur %= mod
            dp[cur] += 1
    for v in dp.values():
        if v > 1:
            ans += v * (v - 1) // 2
    return ans


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

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

for _ in range(M):
  A[-1] = int(A[-1]/2)
  A.sort()
print(sum(A))

### FIXED CODE ###

import heapq

N,M = map(int,input().split())
A = []
for a in map(int,input().split()):
  heapq.heappush(A,-a)

cnt = 0
while cnt < M:
  a = heapq.heappop(A)
  heapq.heappush(A,-((-a)//2))
  cnt += 1
print(-sum(A))
### BUGGY CODE ###

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

ans=0
for i in range(1,N):
    if max(A[:i])>A[i]:
        x=A[i-1]-A[i]
        A[i]+=x
        ans+=x
print(ans)

### FIXED CODE ###

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

for i in range(1,N):
    if A[i-1] > A[i]:
        A[i]=A[i-1]

print(sum(A)-ans)
### BUGGY CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
for x in range(1,n+1):
    ans = 0
    m = ceil(sqrt(x))+1
    for i in range(1, m):
        for j in range(i, m):
            for k in range(j, m):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == x:
                    if i == j == k:
                        ans += 1
                    elif i == j or j == k or k == i:
                        ans += 3
                    else:
                        ans += 6
    print(ans)

### FIXED CODE ###

from math import *
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
for x in range(1,n+1):
    ans = 0
    m = ceil(sqrt(x))+1
    for i in range(1, m):
        for j in range(i, m):
            tmp = (i+j)**2 - 4*(i**2+j**2+i*j-x)
            if tmp > (i+j)**2:
                k = ( -(i+j) + sqrt(tmp) ) // 2
                if k >= j and i**2 + j**2 + k**2 + i*j + j*k + k*i == x:
                    if i == j == k:
                        ans += 1
                    elif i == j or j == k or k == i:
                        ans += 3
                    else:
                        ans += 6
    print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
max = [0]*N

for i in range(N):
    for j in range(N):
        if i != j:    
            if max[i] < A[j]:
                max[i] = A[j]

for i in range(N):
    print(max[i])

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
B = sorted(A, reverse=True)

for i in range(N):
    if B[0] == A[i]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

from fractions import gcd

n, m = [int(i) for i in input().split()]
S = input()
T = input()

g = n * m // gcd(n, m)

try:

    L = ['' for i in range(g)]

except:
    print(-1)
    exit()

if S[0] != T[0]:
    print(-1)
    exit()

for i, s in zip(range(0, g, g//n), S):
    L[i] = s

for i, t in zip(range(0, g, g//m), T):
    L[i] = t
    
A = []
B = []

for i in range(0, g, g//n):
    A.append(L[i])

for i in range(0, g, g//m):
    B.append(L[i])

if ''.join(A) == S and ''.join(B) == T:
    print(g)
else:
    print(-1)



### FIXED CODE ###

from fractions import gcd

n, m = [int(i) for i in input().split()]
S = input()
T = input()

g = n * m // gcd(n, m)

SA = set()
SB = set()

for i in range(0, g, g//n):
    SA.add(i)

for i in range(0, g, g//m):
    SB.add(i)

SC = SA & SB

for s in SC:
    if S[s//(g//n)] != T[s//(g//m)]:
        print(-1)
        exit()

print(g)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
h.extend([10**9]*1000)
dp = [10**9] * (N+1000)

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
h.extend([10**9]*1000)
dp = [10**9] * (N+1000)
 
dp[0] = 0
 
for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
 
print(dp[N-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)

N = int(input())
A = [(int(a), i) for i, a in enumerate(input().split())]
A = sorted(A, reverse=True)

memo = {}

def solve(i, l, r):
    if i==N: return 0
    a, loc = A[i]
    score_l = a*abs(l-loc) + solve(i+1, l+1, r)
    score_r = a*abs(r-loc) + solve(i+1, l, r-1)
    retval = max(score_l, score_r)
    key = (i,l,r)
    if key not in memo: memo[key]=retval
    return retval
    
print(solve(0, 0, N-1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(5000)

N = int(input())
A = [(int(a), i) for i, a in enumerate(input().split())]
A = sorted(A, reverse=True)

memo = {}

def solve(i, l, r):
    if i==N: return 0

    key = l*N+r
    if key in memo: return memo[key]
    
    a, loc = A[i]
    score_l = a*abs(l-loc) + solve(i+1, l+1, r)
    score_r = a*abs(r-loc) + solve(i+1, l, r-1)
    retval = max(score_l, score_r)
    memo[key]=retval
    
    return retval
    
print(solve(0, 0, N-1))
### BUGGY CODE ###

#nCr % mod
def comb_mod(n, r, mod):
  x = 1
  y = 1
  for i in range(r):
    x = (x * (n - i)) % mod
    y = (y * (i + 1)) % mod
    
  ans = x * pow_k(y, mod-2, mod)
  
  return ans % mod
  
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  dic = {}
  
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:
      if (i,k-1) in dic:
        tmp = dic[(i,k-1)]
      else:
        tmp = comb_mod(i,k-1,MOD)
        dic[(i,k-1)] = tmp
        
      ans += comb_mod(i,k-1,MOD) * a[i]
      
    if n-i-k >= 0:
      if (n-i-1,k-1) in dic:
        tmp = dic[(n-i-1,k-1)]
        
      else:
        tmp = comb_mod(n-i-1,k-1,MOD)
        dic[(n-i-1,k-1)] = tmp
        
      ans -= comb_mod(n-i-1,k-1,MOD) * a[i]
      
    ans %= MOD
      
  print(ans)

main()

### FIXED CODE ###

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  g_k = 1
  for i in range(1,k):
    g_k *= i
    g_k %= MOD
    
  gyakugen = pow_k(g_k,MOD-2,MOD)
  array = [0] * (n+1)
  array[k-1] = g_k
  
  for i in range(k, n+1):
    array[i] = array[i-1] * i * pow_k(i-k+1,MOD-2,MOD)
    array[i] %= MOD
    
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:        
      ans += array[i] * gyakugen * a[i]
      
    if n-i-k >= 0:
      ans -= array[n-i-1] * gyakugen * a[i]
      
    ans %= MOD
      
  print(ans)

main()
### BUGGY CODE ###

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

def main():
    def _create_trio(_list):
        ret = []
        _list.pop()
        _list.pop(0)
        return _list.pop()

    n = int(raw_input())
    a = map(int,raw_input().split())

    if n <= 0 or n > 10 ** 5:
        return
    for i in a:
        if i <= 0 or i > 10 ** 9:
            return

    a.sort()
    trio_sum = 0

    for i in range(n):
        trio_sum += _create_trio(a)

    return trio_sum

print main()


### FIXED CODE ###

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

def main():

    n = int(raw_input())
    a = map(int,raw_input().split())

    if n <= 0 or n > 10 ** 5:
        return
    for i in a:
        if i <= 0 or i > 10 ** 9:
            return

    a.sort(reverse=True)
    trio_sum = 0

    for i in range(n):
        index = (i * 2) + 1
        trio_sum += a[index]

    return trio_sum

print main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0 for i in range(N)]
SUM = []
for i in range(N):
    tmp = 0
    for j in range(i+1,i+N-1,2):
        tmp+=2*A[j%N]
    SUM.append(tmp)
for i in range(N):
    ans[i] = sum(A)-SUM[i]
print(*ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0 for i in range(N)]

for i in range(N):
    if i%2 == 0:
        B[0] += A[i]
    else:
        B[0] -= A[i]

for i in range(N-1):
    B[i+1] = 2 * A[i] - B[i]

print(*B)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [(p+1)/2 for p in P]
def s(i):
    A = []
    for j in range(i):
        A.append((P[j]))
    return sum(A)

S = []
for i in range(N+1):
    S.append(s(i))
B = []
for j in range(N-K+1):
    B.append(S[j+K]-S[j])
ans = max(B)
print(ans)
    



### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [0]+[(p+1)/2 for p in P]
S = list(accumulate(P))
B = []
for j in range(N-K+1):
    B.append(S[j+K]-S[j])
ans = max(B)
print(ans)
### BUGGY CODE ###

def counter(k):
  count = 1
  n = 0
  if k % 2 == 0 or k % 5 == 0:
    print(-1)
  while 1:
    n = (n * 10 + 7) % k  
    if n == 0:
      break 
    count += 1
  print(count)
      
if __name__ == '__main__':
  k = int(input())
  counter(k)
 

### FIXED CODE ###

k = int(input())
count = 1
n = 0
if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
  while 1:
      n = (n * 10 + 7) % k  
      if n == 0:
        break 
      count += 1
  print(count)
### BUGGY CODE ###

n = int(input())
p = list(map(lambda x: int(x),input().split()))

count = 1
frag = 0
for i in range(1,n) :
    frag = 0
    for j in range(i) :
        if p[i] > p[j] :
            frag = 1
    if frag == 0 :
        count += 1

print(count)


### FIXED CODE ###

n = int(input())
p = list(map(lambda x: int(x),input().split()))

min_list = [p[0]]
count = 1
for i in range(1,n) :
    if p[i] < min_list[i - 1] :
        min_list.append(p[i])
    else :
        min_list.append(min_list[i - 1])

for j in range(1,n) :
    if p[j] <= min_list[j - 1] :
        count += 1

print(count)