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

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for a in range(-2, 3):
  for b in range(-2, 3):
    magic_move.append([a, b])

move_lis = [[Ch-1, Cw-1]]
already_lis = [[Ch-1, Cw-1]]
all_lis = [[Ch-1, Cw-1]]

while True:
  new_move_lis  = []
  for i,j in move_lis:
    if maze[i][0][j] == "#":
      continue
    for k,l in walk_move:
      if 0 <= i+k <= H-1 and 0 <= j+l <= W-1 and maze[i+k][0][j+l] == "." and not [i+k, j+l] in all_lis:
        dp[i+k][j+l] = min(dp[i+k][j+l], dp[i][j])
        new_move_lis.append([i+k, j+l])
        already_lis.append([i+k, j+l])
        all_lis.append([i+k, j+l])
  if not len(new_move_lis):
    new_already_lis = []
    for o,p in already_lis:
      for m,n in magic_move:
        if not m and not n:
          continue
        if 0 <= o+m <= H-1 and 0 <= p+n <= W-1 and maze[o+m][0][p+n] == "." and not [o+m, p+n] in all_lis:
          dp[o+m][p+n] = min(dp[o+m][p+n], dp[o][p]+1)
          new_move_lis.append([o+m, p+n])
          new_already_lis.append([o+m, p+n])
          all_lis.append([o+m, p+n])
    already_lis = new_already_lis
  if not len(new_move_lis) or dp[Dh-1][Dw-1] != inf:
    break
  else:
    move_lis = new_move_lis

ans = dp[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])
### BUGGY CODE ###

r,g,b,n = map(int, input().split())
rgb_list = [r,g,b]
rgb_list.sort()
r,g,b = rgb_list
max_y = n//g
max_z = n//b

count = 0
for y in range(max_y + 1):
    for z in range(max_z + 1):
        x_before = n - g*y - b*z
        if( (x_before / r) < 0 ):
            break
        if( (x_before % r == 0) ):
            count += 1
print(count)

### FIXED CODE ###

def counter(r,g,b,n):
    count = 0
    max_y = n//g
    max_z = n//b

    for y in range(max_y + 1):
        for z in range(max_z + 1):
            x_before = n - g*y - b*z
            if( (x_before / r) < 0 ):
                break
            if( (x_before % r == 0) ):
                count += 1
    return count

r,g,b,n = map(int, input().split())
print(counter(r,g,b,n))
### BUGGY CODE ###

import functools
import math
import fractions
N = int(input())
A = list(map(int, input().split()))
gcd_max = 1
for i in range(N):
    gcd = functools.reduce(fractions.gcd, A[i+1:] + A[:i])
    if gcd > gcd_max:
        gcd_max = gcd

print(gcd_max)



### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
for i in range(N-1):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[-i-1]))
MAX = 0
for i in range(N):
    MAX = max(MAX, gcd(L[i], R[-i-1]))
print(MAX)
### BUGGY CODE ###

from collections import deque

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

A = []
for i in range(H):
  A.append(input())
  
Q = deque()
visited = [[False for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Q.append([i,j,0])
      visited[i][j] = True

ans = 0
while len(Q) > 0:
  i,j,dist = Q.popleft()
  for dy, dx in [[1,0], [-1,0], [0,-1], [0,1]]:
    y = i + dy
    x = j + dx
    if y < 0 or H <= y or x < 0 or W <= x:
      continue
    if visited[y][x]:
      continue
    visited[y][x] = True
    Q.append([y,x,dist+1])
    ans = max(ans, dist+1)
    
print(ans)


### FIXED CODE ###

from collections import deque

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

A = []
for i in range(H):
  A.append(input())
  
Q = deque()
visited = [[False for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Q.append([i,j,0])
      visited[i][j] = True

ans = 0
while len(Q) > 0:
  i,j,dist = Q.popleft()
  for dy, dx in [[1,0], [-1,0], [0,-1], [0,1]]:
    y = i + dy
    x = j + dx
    if y < 0 or H <= y or x < 0 or W <= x:
      continue
    if visited[y][x]:
      continue
    visited[y][x] = True
    Q.append([y,x,dist+1])
    ans = max(ans, dist+1)
    
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
maxp = 0
for i in range(n - k + 1):
    sump = sum(p[i: i + k])
    if maxp < sump:
        maxp = sump
        j = i
e = 0
for i in range(j, j + k):
    e += (1 + p[i]) / 2
print(e)

### FIXED CODE ###

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
expp = [(i + 1) / 2 for i in p]
cumu, cumu_expp = 0, []
for i in expp:
    cumu += i
    cumu_expp.append(cumu)

max_expp = cumu_expp[k - 1]
for i in range(n - k):
    sumpk = cumu_expp[i + k] - cumu_expp[i]
    if max_expp < sumpk:
        max_expp = sumpk
print(max_expp)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
temp=[0]*n
for i in range(n):
  temp[i]=a.count(a[i])-1
ans=sum(temp)//2
for i in range(n):
  print(ans-temp[i])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
from collections import Counter
tempa=Counter(a)
temp=[0]*n
for i in range(n):
  temp[i]=tempa[a[i]]-1
ans=sum(temp)//2
for i in range(n):
  print(ans-temp[i])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n = int(input())
ans = 0
t = 0
import math
for i in range(1,n+1):
  for j in range(1,n+1):
#    t = math.gcd(i,j)
    for k in range(1,n+1):
      ans += gcd_list([i,j,k])
print(ans)


### FIXED CODE ###

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

import collections
N=int(input())
A=list(map(int,input().split()))
c = collections.Counter(A)
for i in range(N):
  if list(c.values())[i]>1:
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
li=list(collections.Counter(A).values())
for i in range(len(li)):
  if li[i]>1:
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

N = int(input())
A = [0 * x for x in range(N)]
B = [0 * x for x in range(N-1)]

for i in range(N):
  A[i] = int(input())

M = max(A)
for i in range(N):
  if A[i] == M:
    print(max(A[:i]+A[i+1:]))
  else:
    print (M)


### FIXED CODE ###

N = int(input())
A = [0 * x for x in range(N)]
B = [0 * x for x in range(N-1)]

for i in range(N):
  A[i] = int(input())

flag = False
M = max(A)
if A.count(M) > 1:
  flag = True
for i in range(N):
  if A[i] == M:
    if flag:
      print (M)
    else:
      print(max(A[:i]+A[i+1:]))
  else:
    print (M)
### BUGGY CODE ###


def main():

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

    ans = 0
    for i in range(1000):
        d1 = (i // 100) % 10
        d2 = (i // 10) % 10
        d3 = i % 10
        d1_flag = False
        d2_flag = False

        for j in S:
            now = int(j)
            if not d1_flag:
                if d1 == now:
                    d1_flag = True
            elif not d2_flag:
                if d2 == now:
                    d2_flag = True
            elif d3 == now:
                ans += 1
                break

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
s = list(input())

ans = 0


for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = 0
            flag2 = 0
            
            for l in range(n):
                if flag1 == 0 and s[l] == str(i):
                    flag1 = 1
                    continue
                
                if flag1 == 1 and flag2 == 0 and s[l] == str(j):
                    flag2 = 1
                    continue
                
                if flag1 == 1 and flag2 == 1 and s[l] == str(k):
                    ans += 1
                    break
                
print(ans)
### BUGGY CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
ec = [0] * (N - 1)


def dfs(v, pc):
    colors = set()
    colors.add(pc)

    for idx, e in [x for x in enumerate(edge) if v in x[1]]:
        if ec[idx] == 0:
            for c in range(1, N):
                if c not in colors:
                    ec[idx] = c
                    colors.add(c)
                    break

            nv = e[0] if e[1] == v else e[1]
            dfs(nv, c)


dfs(0, 0)
print(max(ec))
for c in ec:
    print(c)


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append((b - 1, i))
    edge[b - 1].append((a - 1, i))
ec = [0] * (N - 1)


def dfs(node, pc):
    color = 1

    for to, idx in edge[node]:
        if ec[idx] == 0:
            if color == pc:
                color += 1
            ec[idx] = color

            dfs(to, color)
            color += 1


dfs(0, -1)
print(max(ec))
for c in ec:
    print(c)
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for _ in range(min(K, 45)):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
for k in range(41):
    B = [0] * N
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N: B[r + 1] -= 1
    for i in range(1, N): B[i] += B[i-1]
    A = B
    if k == K - 1: break
print(*A)
### BUGGY CODE ###

def main():
    n = int(input())
    x = []
    xl = {}
    tmp = []
    tmp2 = []
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        low = max(xx-ll+1,0)
        high = xx+ll-1
        lmh = [low,xx,high]
        tmp.append(lmh)
        tmp2.append(lmh)
        x.append(xx)


    tmp.sort()

    # for i in range()
    flg = 0
    for i, a in enumerate(tmp):
        if flg == 0:

            low = a[0]
            high = a[2]
            flg = 1
        else:

            if low <= a[0] and high >= a[0]:
                 aa= tmp2.pop(tmp2.index(a))


        if i+1 < len(tmp) and high < tmp[i+1][0]:
            flg = 0
    print(len(tmp2))
    return


if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = []
    xl = {}
    tmp = []
    ans = 0
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        low = xx-ll
        high = xx+ll
        lmh = [high,xx,low]
        tmp.append(lmh)


    tmp.sort()
    high = tmp[0][0]
    ans = 1
    for i in range(1,len(tmp)):
        a = tmp[i]
        if a[2] >= high:
            high = a[0]
            ans += 1
        else:
            continue

    print(ans)
    return


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

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return None

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = tuple(map(int, input().split(' ')))

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [tuple(map(int, input().split(' '))) for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))


### FIXED CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
result = 0
tempres = 0
for i in range(0, N):
    for j in range(i, N - 1):
        if H[j] >= H[j + 1]:
            tempres += 1
        else:
            break
    result = max(result, tempres)
    tempres = 0
print(result)


### FIXED CODE ###

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

result = 0
tempres = 0
for i in range(0, N):
    if tempres != 0:
        tempres -= 1
        continue
    for j in range(i, N - 1):
        if H[j] >= H[j + 1]:
            tempres += 1
        else:
            break
    result = max(result, tempres)
    if result >= N - i - 1:
        break
print(result)
### BUGGY CODE ###

from itertools import product
x, y, z, k = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())
AB = []
for (a, b) in product(A, B):
    AB.append(a+b)
AB.sort(reverse=True)
C.sort(reverse=True)
ABC = []
for i in range(min(k+1, len(AB))):
    for j in range(len(C)):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse=True)
for i in range(min(k, len(ABC))):
    print ABC[i]


### FIXED CODE ###

from itertools import product
x, y, z, k = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())
AB = []
for (a, b) in product(A, B):
    AB.append(a+b)
AB.sort(reverse=True)
C.sort(reverse=True)
ABC = []
for i in range(min(k+1, len(AB))):
    for j in range(len(C)):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse=True)
for i in range(min(k, len(ABC))):
    print ABC[i]
### BUGGY CODE ###

n = int(input())
a = map(int, input().split())
ans = 1
for x in a:
    ans *= x

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = sorted(map(int, input().split()))
    ans = 1
    for x in a:
        ans *= x
        if ans > 10 ** 18:
            print(-1)
            exit()
    print(ans)

main()
### BUGGY CODE ###

import sys

N, X, Y = map(int, input().split())

d = [[2000 for _ in range(N)] for _ in range(N)]

for i in range(N):
  d[i][i] = 0
  if i == N-1:
    pass
  else:
    d[i][i+1] = 1
    d[i+1][i] = 1

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])



### FIXED CODE ###

import sys

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

for i in range(N):
  for j in range(N):
    d[i][j] = min(abs(j-i), abs(X-i) + 1 + abs(j-Y), abs(Y-i) + 1 + abs(j-X))

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])
### BUGGY CODE ###

H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))

if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0

for i in range (3, H+1):
	if S.count(i-2) > 0 and S.count(i-1) > 0:
		floor[i]=0
	elif S.count(i-2) > 0:
		floor[i]=floor[i-1]
	elif S.count(i-1) > 0:
		floor[i]=floor[i-2]
	else:
		floor[i]=floor[i-2]+floor[i-1]
print(floor[H]%(10**9+7))

### FIXED CODE ###

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

A = []

for i in range (0, M):
	A.append(int(input()))


if N == 1:
	print(1)
	exit()
elif N ==2:
	if len(A) ==1:
		print(1)
	else:
		print(2)
	exit()

DP = [0]*N

if A.count(1)==0:
	DP[0] = 1

if A.count(2)==0:
	if A.count(1)==0:
		DP[1] = 2
	else:
		DP[1] = 1

for i in range (0, M):
	DP[A[i]-1] = -1

for i in range (0, 2):
	if DP[i] == -1:
		DP[i] = 0

for i in range (2, N):
	if DP[i] ==-1:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[-1]%(1000000007))
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aa = [0]
for i in a:
    aa.append(aa[-1]+i)
bb = [0]
for i in b:
    bb.append(bb[-1]+i)
ans = 0
for i in range(n+1):
    if aa[i] > k:
        break
    j = m
    while aa[i] + bb[j] > k and j > 0:
        j -= 1
    ans = max(ans, i+j)
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
aa = [0]
for i in a:
    aa.append(aa[-1]+i)
bb = [0]
for i in b:
    bb.append(bb[-1]+i)
ans = 0
j = m
for i in range(n+1):
    if aa[i] > k:
        break
    while aa[i] + bb[j] > k and j > 0:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import copy
from collections import deque
import numpy as np
h, w = map(int, input().split())
s = [list(map(str, input().rstrip())) for _ in range(h)]


moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            grid = copy.deepcopy(s)
            q = deque([(i, j)])
            grid[i][j] = 1
            while q:
                curr = q.popleft()
                cx, cy = curr[0], curr[1]
                for (mx, my) in moves:
                    if 0 <= cx + mx < h and 0 <= cy + my < w and type(grid[cx + mx][cy + my]) != int:
                        if s[cx][cy] != s[cx + mx][cy + my] and grid[cx + mx][cy + my] != 0:
                            grid[cx + mx][cy + my] = grid[cx][cy] + 1
                            q.append((cx + mx, cy + my))
            grid = np.array(grid)
            grid = grid.flatten()
            grid[np.where(grid == "#")] = 1
            grid[np.where(grid == ".")] = 1
            grid[np.where(grid == "0")] = 1
            grid = grid.astype(int)
            ans += (grid % 2 == 0).sum()
        else:
            continue

print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            bcnt, wcnt = 0, 0
            q = deque([(i, j)])
            while q:
                cx, cy = q.popleft()
                if visited[cx][cy]:
                    continue
                if grid[cx][cy] == "#":
                    bcnt += 1
                else:
                    wcnt += 1
                visited[cx][cy] = 1
                for (dx, dy) in moves:
                    if 0 <= cx + dx < h and 0 <= cy + dy < w and not visited[cx + dx][cy + dy] and grid[cx + dx][cy + dy] != grid[cx][cy]:
                        q.append((cx + dx, cy + dy))
            ans += bcnt * wcnt
print(ans)
### BUGGY CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)


for i in range(N-1):
    L = len(A)
    #print(A)
    Ans = 0
    for j in range(L):
        if A[j]==i+1:
            Ans += 1
        else:
            for k in range(Ans):
                A.remove(i+1)                
            break
    print(Ans)
    

        
print("0")

### FIXED CODE ###

#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

count = 0
for i in range(N-1):
    L = len(A)
    #print(A)
    Ans = 0
    count += Ans
    for j in range(L-count):
        if A[count + j]==i+1:
            Ans += 1
        else:            
            break
    print(Ans)
    count += Ans

        
print("0")
### BUGGY CODE ###

def cmb(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

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


fac  = [0 for _ in range(n-1)]
finv = [0 for _ in range(n-1)]
inv  = [0 for _ in range(n-1)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,n-1):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

sum_ = 0
for i in range(n-k+1):
    for j in range(i+k-1, n):
        f = ascA[j]-ascA[i]
        c = cmb(j-i-1, k-2)
        #print("%d %d"%(f,c))
        sum_ = (sum_ + (f*c) % MOD) % MOD

print(sum_)


### FIXED CODE ###

def cmb(n,k, MOD):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

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

MAX_N = n
fac  = [0 for _ in range(MAX_N)]
finv = [0 for _ in range(MAX_N)]
inv  = [0 for _ in range(MAX_N)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_N):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

sum_ = 0
for i in range(n-k+1):
    f = ascA[n-i-1] - ascA[i]
    c = cmb(n-i-1, k-1, MOD)
    sum_ = (sum_ + (f*c)%MOD) % MOD
    '''
    for j in range(i+k-1, n):
        f = ascA[j]-ascA[i]
        c = cmb(j-i-1, k-2, MOD)
        #print("%d %d"%(f,c))
        sum_ = (sum_ + (f*c) % MOD) % MOD
    '''

print(sum_)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [[(j, i), (-1, -1)] for i, j in enumerate(a)]
    ans = 0
    for i in range(1, 2**n):
        (t1, t2), (t3, t4) = d[i]
        for j in range(n):
            (t5, t6), (t7, t8) = d[i & ~(1 << j)]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 not in [t2, t4]:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = [[(j, i), (-1, -1)] for i, j in enumerate(a)]
    ans = 0
    for i in range(1, 2**n):
        (t1, t2), (t3, t4) = d[i]
        for j in range(n):
            (t5, t6), (t7, t8) = d[i & ~(1 << j)]
            if t6 not in [t2, t4]:
                if t5 > t1:
                    t1, t2, t3, t4 = t5, t6, t1, t2
                elif t5 > t3:
                    t3, t4 = t5, t6
            if t8 not in [t2, t4]:
                if t7 > t3:
                    t3, t4 = t7, t8
        d[i] = [(t1, t2), (t3, t4)]
        ans = max(ans, t1+t3)
        print(ans)


main()