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

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
fs = [0] * (n**2)

## フロアフィールドを作る
for i in range(n):
    x = min(i,n-1-i)
    for j in range(n):
        y = min(j,n-1-j)
        fs[i*n+j] = min(x,y)

ans = 0
mvs = [1,-1,n,-n]
occupied = [1] * (n**2)
for p in Ps:
    p -= 1
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_+mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

print(ans)
    
    

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)

## フロアフィールドを作る
for x in range(n**2):
    i,j = divmod(x,n)
    x = min(i,n-1-i)
    y = min(j,n-1-j)
    fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

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

import numpy as np

n = int(input())
s = np.array([list(map(ord, input())) for _ in range(n)])
s = np.hstack((s, s))
s = np.vstack((s, s))
ans = 0
for i in range(n):
    for j in range(n):
        p = s[i:i + n, j:j + n]
        if (p == p.T).all():
            ans += 1

print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())
s = np.array([list(map(ord, input())) for _ in range(n)])
s = np.hstack((s, s))
s = np.vstack((s, s))
ans = 0
for i in range(n):
    p = s[0:n, i:i + n]
    if (p == p.T).all():
        ans += n

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

N = int(input())
A = sorted([(a, i) for i, a in enumerate(map(int, input().split()))], reverse=True)
dp = [[0]*(N+1) for _ in [0]*(N+1)]

for j, (a, i) in enumerate(A):
    for l in range(j+1):
        r = N-1-(j-l)
        dp[j+1][l] = max(dp[j+1][l], dp[j][l]+a*(r-i))
        dp[j+1][l+1] = max(dp[j+1][l+1], dp[j][l]+a*(i-l))

print(max(dp[N]))


### FIXED CODE ###

N = int(input())
A = sorted([(a, i) for i, a in enumerate(map(int, input().split()))], reverse=True)
dp = [[0]*(N+1) for _ in [0]*(N+1)]

for j, (a, i) in enumerate(A):
    for l in range(j+1):
        r = N-1-(j-l)
        dp[j+1][l] = max(dp[j+1][l], dp[j][l]+a*(r-i))
        dp[j+1][l+1] = max(dp[j+1][l+1], dp[j][l]+a*(i-l))

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

from sys import stdin
import numpy as np
from copy import deepcopy
import math
import fractions
from functools import reduce

def gcd_list(list):
    return reduce(fractions.gcd, list)

def power2_smaller(num):
    return len(str(bin(num))[2:])-1  
  
def power2_larger(num):
        return len(str(bin(num-1))[2:])

def gcd_each2(lst):
  if len(lst) == 1:
    return lst[0]
  new_lst = []
  for i in range(int(len(lst)/2)):
    new_lst.append(fractions.gcd(lst[2*i], lst[2*i+1]))
  if len(lst) % 2 == 1:
    new_lst.append(lst[-1])
  return gcd_each2(new_lst)


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

#import random
#N = 1000
#A = [random.randint(1,1e9) for i in range(N)]
#print(min(A))
               
solve = []
#nblock = int((len(A)-1+127)/128)
#for i in range(nblock):
  
for i in range(len(A)):
  lst = deepcopy(A)
  lst.pop(i)   
  
  #var = gcd_list(lst)
  var = gcd_each2(lst)
  solve.append(var)

ans = max(solve)
print(ans)
  
  

### FIXED CODE ###

# あまりにもTLEになるから解説見ちゃった

from sys import stdin
import numpy as np
from copy import deepcopy
from fractions import gcd

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

"""
## 入力生成用
import random
N = 1000
A = [random.randint(1,1e9) for i in range(N)]
"""

solve = []
L = np.zeros(N)
R = np.zeros(N)

for i in range(N-1):
  L[i+1] = gcd(L[i], A[i])
  R[N-2-i] = gcd(R[N-1-i], A[N-1-i])
  
for i in range(N):
  var = gcd(L[i], R[i])
  solve.append(var)

ans = int(max(solve))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [sum(a[0:i+1]) for i in range(n)]
result = 0

for i in range(n):
    if s[i] == 0:
        result += 1
    for j in range(i+1, n):
        if s[j] - s[i] == 0:
            result += 1

print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s.sort()
result = 0

count = 1
for i in range(n):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
result += count * (count - 1) // 2

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

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()

P = FLI()

cnt = 0
for i in range(n):
    chk = True
    for j in range(0, i)[::-1]:
        if P[i] > P[j]:
            chk = False
    if chk:
        cnt += 1
        
print(cnt)

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()

P = FLI()

min = 10**9
ans = 0
for i in range(n):
    if P[i] < min:
        ans += 1
        min = P[i]
        
print(ans)
### BUGGY CODE ###

L,R=map(int,input().split())
A=0
B=0
ans=float('inf')
for i in range(L,R):
  for j in range(1,R-i+1):
    A=i*(i+j)
    B=A%2019
    ans=min(ans,B)
print(ans)

### FIXED CODE ###

L,R=map(int,input().split())
if R//2019-L//2019>=1:
  print(0)
  exit()
A=0
B=0
ans=float('inf')
for i in range(L,R):
  for j in range(1,R-i+1):
    A=i*(i+j)
    B=A%2019
    ans=min(ans,B)
print(ans)
### BUGGY CODE ###

import numpy as np

def solve(_list,_k):
  start = 0
  _sum = -1
  for i in range(len(_list)-_k+1):
    s = np.sum(_list[i:i+_k])
    if _sum < s:
      _sum = s
      start = i

  ans = 0.
  for item in _list[start:start+_k]:
    #upper = np.sum(np.arange(1, item+1))
    ans += (item+1) / 2

  return ans


if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]
  _l = np.array(_l)

  result = solve(_l, _k)
  print(result)


### FIXED CODE ###

def solve(_list,_k):
  accumulate_list = [0.]
  for i in _list:
    accumulate_list.append((i+1)/2 + accumulate_list[-1])

  ans = -1.0
  for i in range(len(accumulate_list)-_k):
    ans = max(ans, accumulate_list[i+_k]-accumulate_list[i])
  return ans

if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    S = input()
    res = S[0]
    for i in range(1, N):
        if res[-1] != S[i]:
            res += S[i]
    print(len(res))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N = int(input())
    S = input()
    res = S[0]
    for i in range(1, N):
        if res[-1] != S[i]:
            res += S[i]
    print(len(res))

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

n,m = map(int, input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int, input().split())))

ans=[0]+[1]+[0]*(n-1)
tmp=[]

tansakuheya=[1]

while len(tansakuheya)>0:

	for heya in tansakuheya:

		for gyou in range(m):
			if ab[gyou][0]==heya:
				if ans[ab[gyou][1]]==0:
					ans[ab[gyou][1]]=ab[gyou][0]
					tmp.append(ab[gyou][1])

			if ab[gyou][1]==heya:
				if ans[ab[gyou][0]]==0:
					ans[ab[gyou][0]]=ab[gyou][1]
					tmp.append(ab[gyou][0])

	tansakuheya=tmp
	tmp=[]

print("Yes")
for i in range(2,n+1):
	print(ans[i])

### FIXED CODE ###

from collections import deque
n,m = map(int, input().split())
ikisaki=[[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int, input().split())
    ikisaki[a].append(b)
    ikisaki[b].append(a)
ans=[0]+[1]+[0]*(n-1)
tansakuheya=deque([1])
tmp=deque()

for _ in range(1000009):

    for bangou in tansakuheya:

        for heya in ikisaki[bangou]:
            if ans[heya]==0:
                ans[heya]=bangou
                tmp.append(heya)

    tansakuheya=tmp.copy()
    tmp=deque()


    if not tansakuheya:
        break

print("Yes")
for i in range(2,n+1):
	print(ans[i])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          ans+=An.pop(An.index(max(An))) 
print(ans)

### FIXED CODE ###

import heapq
N , M = map(int , input().split())
jobs = [list(map(int , input().split())) for _ in range(N)]
jobs.sort()

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    #print(q)
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

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

import sys
input = sys.stdin.readline

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

cnt = 0
for _ in range(a, b + 1):
    if _ % x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

print(b // x - (a - 1) // x)
### BUGGY CODE ###


import sys
input = sys.stdin.readline

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

from queue import Queue
q = Queue()
ans = Queue()

def bfs(b):
    q.put(b)
    ans.put([])

    while q.empty() == False:
        p = q.get()
        a = ans.get()

        if p == []:
            break

        if p[0] != 1:
            continue
            
        for i, pp in enumerate(p):
            if pp == i+1:
                q.put(p[:i]+p[i+1:])
                ans.put(a+[i+1])


    if p == []:
        a = a[::-1]
        for aa in a:
            print(aa)
    else:
        print(-1)


bfs(b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from queue import Queue
q = Queue()
ans = Queue()

import numpy as np
n = np.array(n)


def bfs(b):
    q.put(b)
    ans.put([])

    while q.empty() == False:
        p = q.get()
        a = ans.get()

        if p == []:
            break

        if p[0] != 1:
            continue

        m = len(p)

        for i in range(m-1, -1, -1):
            if p[i] == i+1:
                q.put(p[:i]+p[i+1:])
                ans.put(a+[i+1])
                break


    if p == []:
        a = a[::-1]
        for aa in a:
            print(aa)
    else:
        print(-1)


bfs(b)
### BUGGY CODE ###

import math

def is_prime(n):
  if n == 1: 
    return 1

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

  return 1
  
a, b = map(int, input().split())
ans = 0
for i in range(1, min(a, b) + 1):
  if a % i == 0 and b % i == 0:
    ans += is_prime(i)
    
print(ans)
    


### FIXED CODE ###

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
  
a, b = map(int, input().split())
la = prime_decomposition(a)
lb = prime_decomposition(b)
la_lb_and = list(set(la) & set(lb))
    
print(len(la_lb_and) + 1)
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
s=set()
uf=UnionFind(n+1)
for i in range(m):
  a,b=map(int,input().split())
  s.add((a,b))
  s.add((b,a))
  uf.unite(a,b)
for j in range(k):
  c,d=map(int,input().split())
  s.add((c,d))
  s.add((d,c))
ans=[]
for i in range(1,n+1):
  cnt=0
  for j in uf.members(i):
    if not((i,j) in s):
      cnt+=1
  ans.append(cnt-1)
print(*ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
cnt=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
  cnt[a]+=1
  cnt[b]+=1
for i in range(k):
  c,d=map(int,input().split())
  if uf.same(c,d):
    cnt[c]+=1
    cnt[d]+=1
ans=[]
for i in range(1,n+1):
  ans.append(uf.size(i)-cnt[i]-1)
print(*ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
p = np.array(list(map(int, input().split())))
ans = 1
for i in range(1, n):
    if p[i] <= min(p[:i]):
        ans += 1

print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
p = np.array(list(map(int, input().split())))
ans = 1
min_n = p[0]
for i in range(1, n):
    min_n = min(min_n, p[i-1])
    if p[i] <= min_n:
        ans += 1
print(ans)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]

# list top K of a+b
a_plus_b_list = []
for a in a_list:
    for b in b_list:
        a_plus_b_list.append(a+b)
a_plus_b_list.sort(reverse = True)

# list top K of a+b+c
d_list = []
for a_b in a_plus_b_list:
    for c in c_list:
        d_list.append(a_b + c)
d_list.sort(reverse = True)
for i in range(K):
    print(d_list[i])

### FIXED CODE ###

import heapq
x,y,z,k=map(int,input().split())
#heapqは小さい順にしか並べられないので、-をつければ大きい順になる
a=sorted([-int(i) for i in input().split()])
b=sorted([-int(i) for i in input().split()])
c=sorted([-int(i) for i in input().split()])
check=set()
ans=[]
heapq.heappush(ans,(a[0]+b[0]+c[0],0,0,0))
check.add((0,0,0))
for i in range(k):
    h=heapq.heappop(ans)
    print(-h[0])
    if h[1]+1<x:
        if (h[1]+1,h[2],h[3]) not in check:
            heapq.heappush(ans,(a[h[1]+1]+b[h[2]]+c[h[3]],h[1]+1,h[2],h[3]))
            check.add((h[1]+1,h[2],h[3]))
    if h[2]+1<y:
        if (h[1],h[2]+1,h[3]) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]+1]+c[h[3]],h[1],h[2]+1,h[3]))
            check.add((h[1],h[2]+1,h[3]))
    if h[3]+1<z:
        if (h[1],h[2],h[3]+1) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]]+c[h[3]+1],h[1],h[2],h[3]+1))
            check.add((h[1],h[2],h[3]+1))
'''
while len(ans)!=0:
    print(heapq.heappop(ans)[0])
'''
### BUGGY CODE ###

import sys
import fractions, math
from functools import reduce

def gcd(i, j, k):
    return fractions.gcd(i, fractions.gcd(j, k))

def solve(K: int):
    counter = 0
    for i in range(1, K+1):
        for j in range(i, K+1):
            for k in range(j, K+1):
                c = gcd(i, j, k)
                if i == j and j == k:
                    counter += c
                elif i == j or j == k:
                    counter += 3 * c
                else:
                    counter += 6 * c
    print(counter)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import fractions, math
from functools import reduce

def solve(K: int):
    counter = 0
    L = [0] * 201
    for i in range(1, K+1):
        for j in range(1, K+1):
            L[math.gcd(i, j)] += 1
    for i in range(1, K+1):
        for j in range(1, K+1):
            counter += math.gcd(i, j) * L[j]
    print(counter)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

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

N, Q = map(int, input().split())
s1 = input()
lr = [(map(int, input().split())) for _ in range(Q)]

for k in range(Q):
    l, r = lr[k]
    s2 = s1[l-1:r]
    flag = 0
    for i in range(len(s2)-1):
        if s2[i]=='A' and s2[i+1]=='C':
            flag += 1
    print(flag)

### FIXED CODE ###

N, Q = map(int, input().split())
s1 = input()
t = [0 for _ in range(N+1)]
for i in range(N):
    t[i+1] = t[i] + (1 if s1[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

def verify_anagrams(s1, s2):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(s1) == f(s2)

N = int(input())
S = [input() for _ in range(N)]
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if verify_anagrams(S[i], S[j]):
            ans += 1
print(ans)

### FIXED CODE ###

from math import factorial

def comb(n, r):
    if n == 1:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

N = int(input())
S = [input() for _ in range(N)]
str_dict = {}
for s in S:
    sorted_s = "".join(sorted(s))
    if sorted_s not in str_dict:
        str_dict[sorted_s] = 0
    str_dict[sorted_s] += 1
ans = sum([comb(v, 2) for v in str_dict.values()])
print(int(ans))
### BUGGY CODE ###

N = int(input())
lis = list(map(int,input().split()))
for i in range(1,N+1):
    print(lis.count(i))

### FIXED CODE ###

N = int(input())
lis = list(map(int,input().split()))
dic = {}
for i in range(1,N+1):
    dic[i] = 0
for j in lis:
    dic[j] += 1
for k in range(1,N+1):
    print(dic[k])
### BUGGY CODE ###

A = list(map(int, input().split()))
N = A.pop(3)
A.sort()
R = A[2]
G = A[1]
B = A[0]
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        now = N - r*R - g*G
        if  now >= 0 and now % B == 0:
            ans += 1
print(ans)


### FIXED CODE ###

R,G,B,N = list(map(int, input().split()))
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        now = N - r*R - g*G
        if  now >= 0 and now % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import math

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

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

a.sort()
a_reverse = a[::-1]

plus = 0
minus = 0
cnt = 0
ind = 0
ceil = nCr(n, k)
kaisu = nCr(n, k-1)
while cnt < ceil:
    kaisu = kaisu * ((n-ind)-(k-1)) // (n-ind)
    cnt += kaisu
    plus = (plus + (kaisu * a_reverse[ind]) % mod) % mod
    minus = (minus + (kaisu * a[ind]) % mod) % mod
    ind += 1

print((plus-minus) % mod)

### FIXED CODE ###

n,k = map(int, input().split())
a = sorted(list(map(int, input().split())))
a_reverse = a[::-1]
mod = 10**9+7
 
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))
 
def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

plus = 0
minus = 0
cnt = 0
ind = 0
for i in range(n-k+1):
    kaisu = comb(n-i-1, k-1, mod)
    plus = (plus + (kaisu * a_reverse[ind]) % mod) % mod
    minus = (minus + (kaisu * a[ind]) % mod) % mod
    ind += 1

print((plus-minus) % mod)
### BUGGY CODE ###

S = input()
T = input()
dp = [[ "" ] * (len(S) + 1 ) for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = "".join([dp[i-1][j-1],S[j-1]])
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])


### FIXED CODE ###

S = input()
T = input()
dp = [[ 0] * (len(S) + 1 ) for _ in range(len(T) + 1)]
ma = 0
for i in range(len(dp)-1):
    for j in range(len(dp[0])-1):
        if T[i ] == S[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
             dp[i + 1][j + 1]  = max(dp[i][j + 1],dp[i +1][j])
i = len(T) - 1
j = len(S) - 1 
ans = ""
while i >=0 and j >= 0:
    if dp[i][j+1] == dp[i + 1][j + 1]:
        i-=1
    elif dp[i + 1][j] == dp[i + 1][j + 1]:
        j-=1
    else:
        #print(j,i)
        ans = S[j] + ans
        i-=1
        j-=1
print(ans)