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

def gauss_jordan(A, is_extended):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_col = len(A[0])
    cnt_row = len(A)

    rank = 0
    for col in range(cnt_col):
        #  拡大係数行列の場合は最後の行は掃き出ししない
        if is_extended and col == cnt_col - 1:
            break

        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row][col]:
                pivot = row
                break

        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue

        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]

        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row][col]:
                for col2, A_rank_col2 in enumerate(A_rank):
                      A[row][col2] ^= A_rank_col2
        rank += 1

    return A


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

# 全てのxorを計算
# 全てのaを2進数に変換
max_a = max(a)
max_a = bin(max_a)[2::]
xor_sum = 0
for i in range(n):
    xor_sum ^= a[i]
xor_sum = bin(xor_sum)[2::].zfill(len(max_a))

for i in range(n):
    a[i] = bin(a[i])[2::].zfill(len(max_a))

# 行列を作る
# 興味深くないビットについては予めansに答えを足しておく
matrix = [[0] * len(max_a) for _ in range(n)]
ans = 0
for i in range(len(max_a)):
    if xor_sum[i] == "1":
        ans += 2 ** (len(max_a) - i - 1)
    else:
        for j in range(n):
            matrix[j][i] = int(a[j][i])

# ジョルダン標準形を求める
matrix = gauss_jordan(matrix, False)

# xorを取る
tmp = 0
for i in range(n):
    tmp ^= int("".join(map(str, matrix[i])), 2)

# tmpは赤玉、青玉ともに値を持つので2倍して足す
ans = ans + 2*tmp

print(ans)

### FIXED CODE ###

def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])

    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                pivot = row
                break

        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue

        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]

        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        rank += 1

    return A


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

# 全てのxorを計算

# 全てのaを2進数に変換
max_a = max(a)
max_a = bin(max_a)[2::]
len_max_a = len(max_a)

# 全てのxorを計算
# xor_sumが1のビットは興味深くない
# 興味深くないビットについては予めansに答えを足して、ビットを0にしておく
ans = 0
xor_sum = 0
for i in range(n):
    xor_sum ^= a[i]
for i in range(len_max_a):
    mask = 2**i
    tmp = mask & xor_sum
    if tmp:
        ans += tmp
        for i in range(n):
            a[i] -= tmp & a[i]

# ジョルダン標準形
a = xor_gauss_jordan(a)

tmp = 0
for i in range(n):
    tmp ^= a[i]
print(ans + 2*tmp)
### BUGGY CODE ###

S = input()
Q = int(input())
rev = False
for i in range(Q):
  query = input().split()
  if query[0] == '1':
    rev = not rev
  elif query[0] == '2':
    if query[1] == '1':
      if rev == False:
        S = query[2] + S
      else:
        S = S + query[2]
    elif query[1] == '2':
      if rev == False:
        S = S + query[2]
      else:
        S = query[2] + S
  #print('S='+S)
if rev == True:
  S = S[::-1]
print(S)

### FIXED CODE ###

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)
### BUGGY CODE ###

import sys

def exhaustiveSearch(A, m):
    for i in range(len(A)):
        if m == A[i]:
            return True
        elif m > A[i]:
            if exhaustiveSearch(A[:i] + A[i + 1:], m -  A[i]):
                return True
    return False

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    M = map(int, lines[3].split())

    for m in M:
        if exhaustiveSearch(A, m):
            print "yes"
        else:
            print "no"

### FIXED CODE ###

import sys

def exhaustiveSearch(A, m, i, s):
    if A[i] == m:
        return True
    elif i == len(A) - 1 or m < 0 or m > s:
        return False

    return exhaustiveSearch(A, m, i + 1, s) or exhaustiveSearch(A, m - A[i], i + 1, s)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    M = map(int, lines[3].split())
    s = sum(A)

    for m in M:
        if exhaustiveSearch(A, m, 0, s):
            print "yes"
        else:
            print "no"
### BUGGY CODE ###

import math
n = int(input())
a = list()
for i in range(n):
    a.append(input())
for i, youso in enumerate(a):
    b = list()
    for j in youso:
        b.append(j)
    b.sort()
    x = str()
    for j in b:
        x += j
        a[i] = x
x = 0
#TLE ver.
# for i, youso in enumerate(a):
#     for j in range(i, n-1):
#         if youso == a[j+1]:
#             x += 1
# print(x)
a.sort()
for i in range(n-1):
    if a[i] == a[i+1]:
        for j in range(i+1, n):
            if a[i] == a[j]:
                x += 1
            else:
                break
    else:
        continue

# y = 0
# for i in range(1, x+1):
#     y += i
print(x)

### FIXED CODE ###

import math
n = int(input())
a = list()
d = dict()
for i in range(n):
    b = list(input())
    b.sort()
    moji = "".join(b)
    if (moji in d):
        d[moji] += 1
    else:
        d[moji] = 1
x = 0
for i in d:
    if d[i] >=1:
        x += d[i]*(d[i]-1)/2
print(int(x))

#非最適化ソート
# for i in range(n):
#     a.append(input())
# for i, youso in enumerate(a):
#     b = list()
#     for j in youso:
#         b.append(j)
#     b.sort()
#     x = str()
#     for j in b:
#         x += j
#         a[i] = x

#TLE ver.
# for i, youso in enumerate(a):
#     for j in range(i, n-1):
#         if youso == a[j+1]:
#             x += 1
# print(x)

#TLE改良版
# a.sort()
# for i in range(n-1):
#     if a[i] == a[i+1]:
#         for j in range(i+1, n):
#             if a[i] == a[j]:
#                 x += 1
#             else:
#                 break
#     else:
#         continue



#いらない処理
# y = 0
# for i in range(1, x+1):
#     y += i
### BUGGY CODE ###

class QuickFind():
    id=[]
    count=0
    
    def __init__(self,n):
        self.count = n
        i=0
        while i<n:
            self.id.append(i)
            i+=1
            
    def connected(self,p,q):
        return self.find(p) == self.find(q)
 
    def size(self,p):
        return len(list(filter(lambda x: self.id[x] == self.id[p], self.id)))
    
    def find(self,p):    
        return self.id[p]
    
    def union(self,p,q):
        idp = self.find(p)
        if not self.connected(p,q):
            for i in range(len(self.id)):
                if self.id[i]==idp:
                    self.id[i] = self.id[q] 
            self.count -= 1 

n, m = [int(x) for x in input().split()]
b =  [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = QuickFind(n)
for q, p in b:
  r.append(t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size(pp) * ds.size(qq)
  ds.union(p, q)
for x in reversed(r):
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

#abc177 e
import sys,math,collections,itertools
input = sys.stdin.readline

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)
    return arr


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)

fact = [0]*(10**6+1)
fact[1]=1

for a in A:
    if a != 1:
        flag = 0
        temp = a
        for i in range(2, int(-(-a**0.5//1))+1):
            if temp%i==0:
                while temp%i==0:
                    temp //= i
                flag = 1
                fact[i]+=1
        if temp!=1:
            fact[temp]+=1
            flag = 1
        if flag==0:
            fact[n]+=1


        
mn= max(fact)

if mn == 1:
    print('pairwise coprime')
elif mn ==N:
    print('not coprime')
else:
    print('setwise coprime')


### FIXED CODE ###

#abc177 e
import sys,math,collections,itertools
import functools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
fact = set()
for a in A:
    if a==1:
        fact.add(1)
        continue
    if a%2 == 0 and 2 in fact:
        break
    while a%2==0:
        fact.add(2)
        a//=2
            
    i =3
    while i*i <= a:
        if a%i ==0 and i in fact:
            break
        while a%i==0:
            fact.add(i)
            a//=i
        else:
            i +=2
    else:
        if a != 1:
            if a in fact:
                break
            fact.add(a)
        continue
    break
else:
    print('pairwise coprime')
    exit()
if functools.reduce(math.gcd,A)!=1:
    print('not coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

h, w, d = map(int, input().split())
A = []
for i in range(h) :
    A.append(list(map(int, input().split())))

cost = []
for i in range(h) :
    for j in range(w) :
        cost.append([A[i][j], j+1, i+1])

cost.sort(key=lambda c:c[0])

q = int(input())
for _ in range(q) :
    ans = 0
    l, r = map(int, input().split())
    while l != r :
        x1 = cost[l-1][1]
        y1 = cost[l-1][2]
        x2 = cost[l-1+d][1]
        y2 = cost[l-1+d][2]
        ans += abs(x1-x2) + abs(y1-y2)
        l += d
    else :
        print(ans)

### FIXED CODE ###

h, w, d = map(int, input().split())
A = []
for i in range(h) :
    A.append(list(map(int, input().split())))

cost = []
for i in range(h) :
    for j in range(w) :
        cost.append([A[i][j], j+1, i+1])

cost.sort(key=lambda c:c[0])


power = [0 for _ in range(h*w)]
for i in range(d) :
    pos = i
    x1 = cost[pos][1]
    y1 = cost[pos][2]
    while pos + d < h*w :
        x2 = cost[pos+d][1]
        y2 = cost[pos+d][2]
        power[pos+d] = power[pos] + abs(x1-x2) + abs(y1-y2)
        pos += d
        x1 = x2
        y1 = y2


q = int(input())
for _ in range(q) :
    l, r = map(int, input().split())
    print(power[r-1]-power[l-1])
### BUGGY CODE ###

N = int(input())
lst = []
for _ in range(N):
    lst.append(input().split())
    
counter = []

for i in range(N):
    a = []
    for j in range(10):
        a.append(lst[i][0][j])
    counter.append(a)

for j in range(N):
    counter[j].sort()

cnt = 0

for k in range(N-1):
    for l in range(k+1, N):
        if counter[k] == counter[l]:
            cnt += 1
        else:
            continue
            
print(cnt)

### FIXED CODE ###

N = int(input())
lst = [input() for _ in range(N)]
lst = [sorted(i) for i in lst]
lst = ["".join(i) for i in lst]

cnt = 0
dic = {}

for i in lst:
    if i in dic:
        cnt += dic[i]
        dic[i] += 1
    else:
        dic[i] = 1

print(cnt)
### BUGGY CODE ###

import queue
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
q=queue.Queue()
dist=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.put((i,j))
            dist[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,1,-1]
while(not(q.empty())):
    x,y=q.get()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if not(0<=nx<H and 0<=ny<W):
            continue
        if dist[nx][ny]==-1:
            dist[nx][ny]=dist[x][y]+1
            q.put((nx,ny))
print(max([max(i) for i in dist]))


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
q=deque([])
dist=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.append((i,j))
            dist[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,1,-1]
while(len(q)>0):
    x,y=q.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if not(0<=nx<H and 0<=ny<W):
            continue
        if dist[nx][ny]==-1:
            dist[nx][ny]=dist[x][y]+1
            q.append((nx,ny))
print(max([max(i) for i in dist]))
### BUGGY CODE ###

N,M,K = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

A = [0]
B = [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(0,N+1):
    p = M
    if A[i] > K:
        break
    while B[p] > K - A[i]:
        p -= 1
    ans = max(ans,i+p)

print(ans)

### FIXED CODE ###

N,M,K = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

A = [0]
B = [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

p = M
for i in range(0,N+1):
    if A[i] > K:
        break
    while B[p] > K - A[i]:
        p -= 1
    ans = max(ans,i+p)

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

# -*- coding: utf-8 -*-
"""
Created on Mon Dec 31 14:30:45 2018

@author: Yamazaki Kenichi
"""

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

limit = int(pow(P,1/N)//1+1)

if N == 1:
    ans = P
else:
    ans = 1
    for i in range(1,limit+1):
        if P % pow(i,N) == 0:
            ans = i

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Dec 31 14:30:45 2018

@author: Yamazaki Kenichi
"""

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

limit = int(pow(P,1/N)//1)

if N == 1:
    ans = P
elif limit == 1:
    ans = 1
else:
    ans = 1
    for i in range(2,limit+2):
        if P % pow(i,N) == 0:
            ans = i
            
print(ans)
### BUGGY CODE ###

# 17:02-17:26
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

F = [0]*N
for i in range(N):
    F[i] = pow(10,i,13)
D = [[[0]*13 for j in range(10)] for i in range(N)]
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            k = (F[i]*j)%13
            if i==0:
                D[i][j][k] = 1
            else:
                for l in range(10):
                    for m in range(13):
                        D[i][j][(m+k)%13] += D[i-1][l][m]
    else:
        j = int(S[i])
        k = (F[i]*j)%13
        if i==0:
            D[i][j][k] = 1
        else:
            for l in range(10):
                for m in range(13):
                    D[i][j][(m+k)%13] += D[i-1][l][m]
    if i%1000==0:
        for j in range(10):
            for k in range(13):
                D[i][j][k] = D[i][j][k]%MOD
ans = 0
for j in range(10):
    ans += D[N-1][j][5]
print(ans%MOD)

### FIXED CODE ###

MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

DP = [[0]*13 for i in range(N)]
K = 1
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            if i==0:
                DP[0][(j*K)%13] = 1
            else:
                for k in range(13):
                    DP[i][(j*K+k)%13] += DP[i-1][k]
    else:
        j = int(S[i])*K
        if i==0:
            DP[0][(j*K)%13] = 1
        else:
            for k in range(13):
                DP[i][(j+k)%13] += DP[i-1][k]
    K = (K*10)%13
    for j in range(13):
        DP[i][j] = DP[i][j]%MOD
print(DP[N-1][5]%MOD)
### BUGGY CODE ###

n ,x, y = map(int, input().split())

sub_degree = [0]*n
for i in range(n):
    for j in range(i+1, n):
        a = min(abs(j-i), abs(x-1-i)+1+abs(j-y+1), abs(y-1-i)+1+abs(j-x+1))-1
        sub_degree[a]+=1

for i in range(n-1):
    print(sub_degree[i])


### FIXED CODE ###

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

ans = [0]*N

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

for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

#coding:utf-8

n = int(input())
a = input().split()

list_n = []
list_a = []

for i in range(n):
    list_n.append(0)

for i in a:
    aa = int(i)
    list_a.append(aa)
    list_n[aa - 1] += 1

ans = 0
for i in range(n):
    ans = 0
    lislis = list_n.copy()
    a1 = list_a[i]
    lislis[a1 - 1] -= 1
    for t in lislis:
        ans += t * (t - 1) / 2
    print("{}".format(int(ans)))

### FIXED CODE ###

#coding:utf-8

n = int(input())
a = input().split()

list_n = [0 for i in range(n)]
basic = 0

for i in a:
    aa = int(i)
    count = list_n[aa - 1]
    basic += count
    list_n[aa - 1] += 1

ans = 0
for i in range(n):
    ans = 0
    a1 = int(a[i])
    ans = basic - list_n[a1 - 1] + 1
    print("{}".format(int(ans)))
### BUGGY CODE ###

s = input()
t = input()
l = ["0"]*len(s)
if len(set(s)) != len(set(t)):
  print("No")
  exit()
for i in range(len(s)):
  if s[i] == t[i]:
    l[i] = t[i]
for i in range(len(s)):
  if s[i] != t[i] and t[i] in l:
    print("No")
    exit()
print("Yes")
    

### FIXED CODE ###

from collections import Counter
s=Counter(list(input()))
t=Counter(list(input()))
s, t=list(s.values()),list(t.values())
print("Yes" if sorted(s)==sorted(t) else "No")
### BUGGY CODE ###

from collections import Counter
N=int(input())
lis=list(input() for _ in range(N))
se=set(lis)
ans=[]
high=0

counter=Counter(lis)
high=counter.most_common()[0][1]

for  j in se:
  if lis.count(j)==high:
    ans.append(j)
ans.sort()

for k in ans:
  print(k)

### FIXED CODE ###

from collections import Counter
N=int(input())
lis=list(input() for _ in range(N))
ans=[]

counter=Counter(lis)
high=counter.most_common()[0][1]

for k,v in counter.most_common():
  if v==high:
    ans.append(k)
  else:
    break
ans.sort()
for i in ans:
  print(i)
### BUGGY CODE ###

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

j = n
k = n
t = n * a



dp = [[[0 for t in range(t + 1)] for k in range(k + 1)] for j in range(j + 1)]

dp[1][0][0] = 1
dp[0][0][0] = 1

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(1, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, t + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)

### FIXED CODE ###

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

j = n
k = n
t = n * a
maxv = max(a, max(xlist))


dp = [[[0 for t in range(n*maxv + 1)] for k in range(k + 1)] for j in range(j + 1)]

dp[1][0][0] = 1
dp[0][0][0] = 1

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, ki * maxv + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)
### BUGGY CODE ###

n=int(input())
s=[input()for _ in range(n)]
maxcount,ls=0,[]

for i in s:
  if s.count(i)==maxcount:
    ls.append(i)
    maxcount=s.count(i)
    continue
      
  elif s.count(i)>maxcount:
    ls=[i]
    maxcount=s.count(i)
    continue  
      
ls=sorted(set(ls))
for i in ls:
  print(i)

### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
s.sort()
ans,be=[],""
cnt,maxcount=1,0

for i in range(n):
  if be==s[i]:
    cnt+=1
    
  else:
    if cnt>=1:
      if cnt>maxcount:
        maxcount=cnt
        ans.clear()
        ans.append(be)
      
      elif cnt==maxcount:
        ans.append(be)
      
      cnt=1
  be=s[i]
  if i==n-1:
    if cnt>=1:
      if cnt>maxcount:
        maxcount=cnt
        ans.clear()
        ans.append(be)
      
      elif cnt==maxcount:
        ans.append(be)
    
ans.sort()
for i in ans:
  if i!="":
    print(i)
### BUGGY CODE ###

def examC(mod):
    N = I()
    A = LI()
    num = (N+1)%2
    loop = (N+1)//2
    cur = int(1)
    if num==0:
        A.append(0)
        cur = cur/2
    for i in range(loop):
        if A.count(i*2+num)!=2:
            cur = int(0)
            break
        cur = int(cur*2)%mod
    print(cur)




import sys
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC(mod)


### FIXED CODE ###

def examC(mod):
    N = I()
    A = LI()
    num = (N+1)%2
    loop = (N+1)//2
    cur = int(1)
    L = [0]*loop
    if num==0:
        L[0] +=1
    for i in range(N):
        L[A[i]//2] += 1
        if L[A[i]//2]>=3:
            cur = int(0)
            break
    for _ in range(N//2):
        cur = (cur*2)%mod
    print(cur)





import sys
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC(mod)
### BUGGY CODE ###

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

a.sort()

result = 0
mod = 10**9+7

def solve(x, y):
    if x == 0:
        return 1
    else:
        x = min(x, y-x)
        r = 1
        for i in range(y-x+1, y+1):
            r = (r*i)%mod
        for i in range(1, x+1):
            r //= i
        return r



for i in range(n-k+1):
    for j in range(i+k-1, n):
        result = (result+((a[j]-a[i])%mod)*solve(k-2, j-i-1))%mod
print(result)

### FIXED CODE ###

N, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

result = 0
mod = 10**9+7

 
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
n = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, n+1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if k==1:
    print(0)
else:
    result = 0
    for i in range(N-k+1):
        result += (a[N-i-1]-a[i])*cmb(N-1-i, k-1)
        result %= mod

    print(result%mod)