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

n = int(input())
l = list(map(int, input().split()))
ans = 0
for a in range(n-2):
    for b in range(a+1, n-1):
        for c in range(b+1, n):
            if l[a]<l[b]+l[c] and l[b]<l[c]+l[a] and l[c]<l[a]+l[b]: ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n-2):
  for j in range(i+1, n-1):
    ab = l[i] + l[j]
    idx = bisect_left(l, ab)
    ans += max(idx-j-1, 0)
print(ans)
### BUGGY CODE ###

def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    ans = 0
    for i in range(n+1):
        ans_ = 0
        cost = sum(a[0:i])
        k_ = k-cost
        if k_<0:
            break
        ans_ = i
        for j in range(m):
            k_ = k_-b[j]
            if k_<0:
                break
            ans_ += 1
        if ans_ > ans:
            ans = ans_
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import bisect
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    A,B = [0],[0]
    for i in range(n):
        A.append(A[i]+a[i])
    for i in range(m):
        B.append(B[i]+b[i])
    ans = 0
    for i in range(n+1):
        cost = A[i]
        c = i
        if cost > k:
            continue
        cost = k-cost
        c += bisect.bisect_right(B,cost)-1
        if c>ans:
            ans = c
    print(ans)

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

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

res = 0
for i in range(n):
    for j in range(1, n-i):
        res = res + (a[i] * a[i+j]) % (10**9 + 7)
        res %= (10**9 + 7)
print(res)

### FIXED CODE ###

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

sum = 0
for i in range(n):
    sum += a[i]

res = 0
s = sum
for i in range(n):
    s -= a[i]
    res = (res + s*a[i])%(10**9+7)
print(res)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int, input().split()))
f=list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
time=[]
for i in range(n):
	time.append(a[i]*f[i])
while k>=1:
	i=np.argmax(time)
	a[i]-=1
	time[i]-=f[i]
	k-=1
print(max(time))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int, input().split()))
f=list(map(int, input().split()))
a.sort()
f.sort(reverse=True)

maxaf=a[0]*f[0]
for i in range(n):
	if a[i]*f[i]>maxaf:
		maxaf=a[i]*f[i]

def solve(x):
	total=0
	for i in range(n):
		total+=max(0,a[i]-x//f[i]) #負になりうる懸念ができていなかった、とほほ
	return total<=k

#xの範囲 ngは実現が難しい方
ok=maxaf
ng=-1

while ok-ng>1:
	mid=(ok+ng)//2
	if solve(mid):
		ok=mid
	else:
		ng=mid
print(ok)
### BUGGY CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

n,m = map(int,input().split())
if (is_prime(m)):
  print(1)
  exit(0)

a = int(m /n)


for i in range(a,0,-1):
  if m % i == 0:
    print(i)
    break

### FIXED CODE ###

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

a = int(m /n)
for i in range(a,0,-1):
  if m % i == 0:
    print(i)
    break
### BUGGY CODE ###

import numpy as np

n,m,q = map(int, input().split())
qz = [list(map(int, input().split())) for i in range(q)]

qx = []

for i in range(q):
    ma = 0
    index = 0
    for j in range(len(qz)):
        if (qz[j][2] > ma):
            ma = qz[j][2]
            index = j
    qx.append(qz[index])
    qz.pop(index)

su = [0]

def checker(af, bf):
    lt = max(af) - max(bf) + 1
    rt =[]
    for h in range(0,lt):
        amax = 0
        bf = np.array(bf)+h
        for i in range(n):
            if (af[i] != 0 and bf[i] != 0 and af[i] != bf[i]):
                break
            elif (amax > max(af[i], bf[i]) and (af[i] != 0 or bf[i] != 0)):
                break
            amax = max(amax,af[i],bf[i])
        else:
            rt.append(h)
    return rt

def adder(af, bf):
    rt = [0]*n
    for i in range(n):
        rt[i] = max(af[i], bf[i])
    return rt

ans = [[0] * n]
ans[0][qx[0][0]-1] = 1
ans[0][qx[0][1] - 1] = qx[0][2]+1
su = [qx[0][3]]

for i in range(1,q):
    a, b, c, d = map(int, qx[i])
    t = [0] * n
    t[a-1] = 1
    t[b - 1 ] = c + 1
    #print(t)
    ll = len(ans)
    for j in range(ll):
        ct = checker(ans[j], t)
        if (len(ct) != 0):
            for k in ct:
                ans.append(adder(ans[j], np.array(t)+k))
                su.append(su[j] + d)
        else:
            ans.append(t)
            su.append(d)
print(max(su))



### FIXED CODE ###

from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
qx = [list(map(int, input().split())) for i in range(q)]

ans = 0

for i in combinations_with_replacement(range(1, m + 1), n):
    s = 0
    for a, b, c, d in qx:
        s += d if (i[b-1] - i[a-1] == c) else 0
    ans = max(ans, s)

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

import math
import numpy

def is_prime(n):
    if (n==1):
        return 0
    for i in range(2,int(math.sqrt(n))+1):
        if (n % i == 0):
            return 0
    return 1

prime = [0]*(10**5+1)
for i in range(1,10**5+1):
    prime[i] = is_prime(i)

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (prime[i] and prime[int((i+1)/2)]):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])

### FIXED CODE ###

import math
import numpy

def is_prime(n):
    if (n==1):
        return 0
    if (n==2):
        return 1
    for i in range(3,int(math.sqrt(n))+1,2):
        if (n % i == 0):
            return 0
    return 1

prime = [0]*(10**5+1)
for i in range(1,10**5+1,2):
    prime[i] = is_prime(i)
prime[2] = 1

q = int(input())
li = [0]*(10**5+1)
for i in range(1,10**5+1):
    if (i%2 == 1):
        if (prime[i] and prime[int((i+1)/2)]):
            li[i] = 1

com = numpy.cumsum(li)
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(com[r]-com[l-1])
### BUGGY CODE ###

def main():
  n = int(input())
  words = []
  scores = []
  for _ in range(n):
    word, score = input().split()
    words.append(word)
    scores.append(int(score))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  values = []
  weights = []
  for word, score in zip(words, scores):
    cnt = search(word)
    for _ in range(cnt):
      values.append(score)
      weights.append(len(word))
  
  dp = [0] * (t + 1)
  for v, w in zip(values, weights):
    for x in range(max(-1, t - w), -1, -1):
      dp[x + w] = max(dp[x + w], dp[x] + v)
  print(max(dp)) 

main()


### FIXED CODE ###

def main():
  n = int(input())
  lst = []
  for _ in range(n):
    word, score = input().split()
    lst.append((word, int(score)))
  mp = ["#" * 6] + ["#" + input() + "#" for _ in range(4)] + ["#" * 6]
  t = int(input())
  
  def search(word):
    used = [[False] * 6 for _ in range(6)]
    vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
    
    def _search(word, pos, x, y):
      if pos == len(word) - 1:return 1
      used[y][x] = True
      ret = 0
      for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if not used[ny][nx] and mp[ny][nx] == word[pos + 1]:
          ret += _search(word, pos + 1, nx, ny)
      used[y][x] = False
      return ret
    
    ret = 0
    for y in range(1, 5):
      for x in range(1, 5):
        if mp[y][x] == word[0]:ret += _search(word, 0, x, y)  
    return ret
  
  items = []
  for word, score in lst:
    cnt = search(word)
    acc = 1
    weight = len(word)
    while cnt >= acc:
      cnt -= acc
      items.append((score * acc, weight * acc))
      acc *= 2
    if cnt:
      items.append((score * cnt, weight * cnt))
  
  dp = [0] * (t + 1)
  for v, w in items:
    for x in range(t - w, -1, -1):
      if dp[x + w] < dp[x] + v:dp[x + w] = dp[x] + v
  print(max(dp)) 

main()
### BUGGY CODE ###

from math import ceil
n = int(input())
ans = 0
for i in range(1, n):
    for j in range(1, n // i + 1):
        if i * j != n:
            #print(i, j, n - i * j)
            ans += 1
print(ans)

### FIXED CODE ###

from math import ceil
n = int(input())
ans = 0
for i in range(1, n):
    for j in range(1, n // i + 1):
        if i * j != n:
            #print(i, j, n - i * j)
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
import bisect

N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

G.sort(key = lambda x : -x[2])
T.sort()

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [None] * (4 * n + 5)

    def update(self, i, l, r, ll, rr, val) :
        if r <= ll or rr <= l :
            return
        if ll <= l and r <= rr :
            self.A[i] = val
            return

        if self.A[i] != None :
            self.A[i * 2] = self.A[i * 2 + 1] = self.A[i]
            self.A[i] = None

        m = (l + r) // 2
        self.update(i * 2, l, m, ll, rr, val)
        self.update(i * 2 + 1, m, r, ll, rr, val)

    def get(self, i, l, r, p) :
        if self.A[i] != None or l + 1 == r :
            return self.A[i]
        m = (l+r) // 2
        if p < m :
            return self.get(i * 2, l, m, p)
        else :
            return self.get(i * 2 + 1, m, r, p)

ST = SegTree(Q)
for g in G :
    s = max(0, g[0] - g[2])
    e = g[1] - g[2]
    if e <= 0 :
        continue

    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)

    if ll == rr :
        continue

    ST.update(1, 0, Q, ll, rr, g[2])

for i in range(Q) :
    ans = ST.get(1, 0, Q, i)
    if ans == None :
        print(-1)
    else :
        print(ans)


### FIXED CODE ###

import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [10**15] * (2 << (n + 1).bit_length())
 
    def update(self, l, r, val) :
      l += len(self.A) // 2
      r += len(self.A) // 2
      while l < r:
          if l & 1 :
              self.A[l] = min(self.A[l], val)
              l += 1
          if r & 1:
              self.A[r-1] = min(self.A[r-1], val)
              r -= 1
          l //= 2
          r //= 2

    def get(self, i) :
      i += len(self.A) // 2
      ret = self.A[i]
      while i > 0 :
          i //= 2
          ret = min(ret, self.A[i])
      return ret if ret < 10**15 else -1

ST = SegTree(Q)
for g in G :
    s = g[0] - g[2]
    e = g[1] - g[2]
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(i)
    print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])


### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

K, S = map(int, input().split())

li = []
for x in range(0, S+1):
    if x <= K:
        for y in range(0, S+1-x):
            if y <= K:
                for z in range(0, S+1-x-y):
                    if x + y + z == S and z <= K:
                        li.append([x, y, z])
print(len(li))

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        if S-x-y >= 0 and S-x-y <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
ans = 1
 
for i in range(n):
  ans *= nums[i]
  
if ans > 10**18:
  ans = -1
 
print(ans)

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
ans = 1

if nums.count(0) > 0:
  ans = 0
else:
  for i in range(n):
    ans *= nums[i]
    if ans > 10**18:
      ans = -1
      break

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

H, W = map(int, input().split())
count = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if (i + j) % 2 == 0:
            count += 1
print(count)


### FIXED CODE ###

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

if H !=1 and W !=1:
    answer = H * W // 2
    if H * W % 2 != 0:
        answer += 1
    print(answer)
else:
    print(1)
### BUGGY CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===

def main():
    h, w = ns()
    table = [list(input()) for _ in range(h)]
    not_visited = [[True for _ in range(w)] for __ in range(h)]
    dist = [[INF for _ in range(w)] for __ in range(h)]

    que = collections.deque()
    for hi in range(h):
        for wi in range(w):
            if table[hi][wi] == "#":
                not_visited[hi][wi] = False
                dist[hi][wi] = 0
                que.append([hi, wi])

    nxt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    cnt = -1
    ans = 0
    while len(que):
        cnt += 1
        for i in range(len(que)):
            hi, wi = que.popleft()
            for yi, xi in nxt:
                th = hi + yi
                tw = wi + xi
                if -1 < th < h and -1 < tw < w:
                    if not_visited[th][tw]:
                        not_visited[th][tw] = False
                        dist[th][tw] = min(dist[th][tw], dist[hi][wi] + 1)
                        que.append([th, tw])

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===

def main():
    h, w = ns()
    table = [list(input()) for _ in range(h)]
    not_visited = [[True for _ in range(w)] for __ in range(h)]
    dist = [[INF for _ in range(w)] for __ in range(h)]

    que = collections.deque()
    for hi in range(h):
        for wi in range(w):
            if table[hi][wi] == "#":
                not_visited[hi][wi] = False
                dist[hi][wi] = 0
                que.append([hi, wi])

    nxt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    cnt = -1
    ans = 0
    while len(que):
        cnt += 1
        for i in range(len(que)):
            hi, wi = que.popleft()
            for yi, xi in nxt:
                th = hi + yi
                tw = wi + xi
                if -1 < th < h and -1 < tw < w:
                    if not_visited[th][tw]:
                        not_visited[th][tw] = False
                        dist[th][tw] = min(dist[th][tw], dist[hi][wi] + 1)
                        que.append([th, tw])

    print(cnt)


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

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

H, W = list(map(int, input().split()))
all_count = H * W
L = [j == "#" for i in range(H) for j in input()]
blacks = [i for i in range(all_count) if L[i]]
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
def calc_next():
  global black_count, all_count, blacks, L, H, W, cands_H, cands_W
  next_steps = [black+cand for black in blacks for cand in cands_H]
  next_steps.extend([black-1 for black in blacks if black%W != 0])
  next_steps.extend([black+1 for black in blacks if black%W != W-1])
  next_steps = set(next_steps)
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  return (blacks, black_count+len(blacks))

def main():
  global black_count, all_count, blacks, L, H, W, cands_H, cands_W
  result = 0
  while black_count < all_count:
    blacks, black_count = calc_next()
    result += 1
    if black_count >= all_count:
      break
    for i in blacks:
      L[i] = True

  print(result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

n, w = map(int, (input().split()))
lst = [list(map(int, input().split())) for i in range(n)]

dp = [0] * (w + 1)

for i in range(n):
    for j in range(w, lst[i][0] - 1, -1):
        dp[j] = max(dp[j - lst[i][0]] + lst[i][1], dp[j])

print(dp[w])


### FIXED CODE ###

n, w = map(int, (input().split()))
lst = [list(map(int, input().split())) for i in range(n)]

dp = [0] * (w + 1)

for i in range(n):
    for j in range(w, lst[i][0] - 1, -1):
        dp[j] = max(dp[j - lst[i][0]] + lst[i][1], dp[j])

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

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

#print(a)
di = 10**9+7

s = 0
for i in range(N):
    for j in range(i+1,N):
        #print(a[i],a[j])
        s = (s + (a[i]*a[j])%di)%di
print(s)


### FIXED CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

#print(a)
di = 10**9+7
cum = [0]*(N+1)
for i in range(N)[::-1]:
    cum[i] = (cum[i+1] + a[i])%di

s = 0
for i in range(N):
    s = (s + (a[i]*cum[i+1])%di)%di
    # for j in range(i+1,N):
    #     #print(a[i],a[j])
    #     s = (s + (a[i]*a[j])%di)%di
print(s)

# import sys,collections
# sys.setrecursionlimit(1000000)
# INF = float("inf")

# Q = int(sys.stdin.readline())
# ab = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param
# N = 1000001

# cum=[0]*(N+1)

# for l,r in ab:
#     cum[l] += 1
#     if r+1 < N+1: cum[r+1] -= 1

# ret = cum[0]
# for i in range(N):
#     cum[i+1] += cum[i]
#     ret = max(ret,cum[i+1])

# print(ret)
### BUGGY CODE ###

import time

# success
# https://atcoder.jp/contests/abc151/tasks/abc151_e
# https://blogarithms.github.io/articles/2019-01/fermats-theorem


MOD =  1000000007


def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0

	if k<n-k:
		k = n-k
	r = 1
	for i in range(k+1, n+1):
		r *= i
	for i in range(2, n-k+1):
		r = r//i
	return r


def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return int(score%MOD)
	
	
print(main())


### FIXED CODE ###

import time
MOD =  1000000007
MOD2 = 1000000005
MAX = 100001

facs = [1 for _ in range(MAX)]
inv = [1 for _ in range(MAX)]


for i in range(1, MAX):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, MAX):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return score%MOD
	
	
print(main())