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

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

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

def find_group(groups, a):
    for i in range(0, len(groups)):
        g = groups[i]
        if a in g:
            return i
    return -1

bridge = bridge[1:]
bridge = reversed(bridge)
result = []
groups = []
for i in range(0, n):
    groups.append(i)

result.append(n * (n - 1) // 2)

for b in bridge:
    a1 = groups[b[0]]
    a2 = groups[b[1]]
    if a1 == a2:
        pass
    elif a1 < a2:
        groups[b[0]] = a1
        groups[b[1]] = a1
        for i, g in enumerate(groups):
            if g == a2:
                groups[i] = a1
    else:
        groups[b[0]] = a2
        groups[b[1]] = a2
        for i, g in enumerate(groups):
            if g == a1:
                groups[i] = a2
    counts = list()
    for i in range(0, len(groups)):
        counts.append(0)
    for g in groups:
        counts[g] += 1
    
    count = 0
    for i in range(0, len(counts) - 1):
        for j in range(i + 1, len(counts)):
            count += counts[i] * counts[j]
    result.append(count)

result = reversed(result)
for r in result:
    print(r)


### FIXED CODE ###

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

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

bridge = bridge[1:]
bridge = reversed(bridge)
result = []


parent = [-1] * n
size = [1] * n
def root(v):
    p = parent[v]
    if p >= 0:
        return root(p)
    return v

value = n * (n - 1) // 2
result.append(value)

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    p0 = root(b[0])
    p1 = root(b[1])
    if p0 == p1:
        result.append(value)
        continue
    s0 = size[p0]
    s1 = size[p1]
    if p0 < p1:
        parent[p1] = p0
        size[p0] += size[p1]
    else:
        parent[p0] = p1
        size[p1] += size[p0]
    value -= s0 * s1
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)
### BUGGY CODE ###

n,m,q= map(int,input().split())
lrList=[list(map(int,input().split()))for i in range(m)]
pqList=[list(map(int,input().split()))for i in range(q)]
for pq in pqList:
    ans = 0
    for lr in lrList:
        ans +=(pq[0] <= lr[0] and pq[1] >= lr[1])
    print(ans)

### FIXED CODE ###

n,m,q= map(int,input().split())
dataList = [[0 for xIndex in range(n+1)]for yIndex in range(n+1)]

for i in range(m):
    xTemp,yTemp = map(int,input().split())
    dataList[yTemp][xTemp]+=1
pqList=[list(map(lambda x:int(x),input().split()))for i in range(q)]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex][xIndex-1]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex-1][xIndex]

for pq in pqList:
    p = pq[0]-1
    q = pq[1]
    print(dataList[q][q]+dataList[p][p]-dataList[p][q]-dataList[q][p])
### BUGGY CODE ###

N,K=map(int,input().split())
x=[int(i) for i in input().split()]

cost=10**13

for i in range(N-K+1):
    x2=x[i:i+K]
    c=x2[-1]-x2[0]+min(abs(x2[0]),abs(x2[-1]))
    cost=min(cost,c)

print(cost)


### FIXED CODE ###

N,K=map(int,input().split())
x=[int(i) for i in input().split()]

cost=10**13

for i in range(N-K+1):
    c=x[i+K-1]-x[i]+min(abs(x[i]),abs(x[i+K-1]))
    cost=min(cost,c)

print(cost)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-A.count(A[i]))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-c[A[i]])
### BUGGY CODE ###

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

A = list(map(int, input().split()))
A.sort()
X = []
for i in range(m):
    b, c = map(int, input().split())
    X += [c]*b
X.sort(reverse=True)

for i in range(min(len(A), len(X))):
    if A[i] < X[i]:
        A[i] = X[i]
    else:
        break

print(sum(A))

### FIXED CODE ###

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

A = list(map(int, input().split()))
A.sort()
bc = []
for i in range(m):
    b, c = map(int, input().split())
    bc.append([b, c])
bc.sort(key=lambda x:x[1], reverse=True)

X = []
for b, c in bc:
    X += [c]*b
    if len(X) >= len(A):
        break

ans = sum(A)
for i in range(min(len(A), len(X))):
    if A[i] >= X[i]:
        break
    ans += X[i] - A[i]

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

import sys
N, K = map(int, input().split())
a = list(map(int, input().split()))

seta = set(a)
cntK = len(seta)
cnta = [0] * cntK
if cntK <= K:
    print(0)
    sys.exit()

for i in range(len(seta)):
    cnta[i] = a.count(seta.pop())

cnta.sort()
cnt = 0
for i in range(cntK - K):
    cnt += cnta[i]

print(cnt)

### FIXED CODE ###

import sys
from collections import defaultdict
N, K = map(int, input().split())
a = list(map(int, input().split()))

seta = set(a)
cntK = len(seta)
cnta = [0] * cntK
if cntK <= K:
    print(0)
    sys.exit()

d = defaultdict(int)
for key in a:
    d[key] += 1

dtmp = sorted(d.items(), key=lambda x: x[1])
cnt = 0
for i in range(cntK - K):
    cnt += dtmp[i][1]
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    from bisect import bisect

    _ = int(input())
    A = sorted([int(x) for x in input().split()])
    B = sorted([int(x) for x in input().split()])
    C = sorted([int(x) for x in input().split()])

    ans = 0
    for a in A:
        can_b = B[bisect(B, a):]
        for b in can_b:
            ans += len(C[bisect(C, b):])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    from bisect import bisect

    N = int(input())
    A = sorted([int(x) for x in input().split()])
    B = sorted([int(x) for x in input().split()])
    C = sorted([int(x) for x in input().split()])

    lst = [N - bisect(C, b) for b in B]
    lst = lst[::-1]
    tmp_lst = [lst[0]]
    for i in lst[1:]:
        tmp_lst.append(i + tmp_lst[-1])
    tmp_lst = tmp_lst[::-1]

    ans = 0
    for a in A:
        res = bisect(B, a)
        ans += tmp_lst[res] if res < N else 0
    print(ans)


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

def resolve():
    N = int(input())
    strA = input()
    for i in range(1,N+1):
        print(strA.count(str(i)))
resolve()

### FIXED CODE ###

import collections
def resolve():
    N = int(input())
    strA = input().split()
    ans = collections.Counter(strA)
    for i in range(1,N+1):
        print(ans[str(i)])
resolve()
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]

dp = [[10**10, 0] for i in range(H+1)]
dp[0][0] = 0
# i 減らすのに最小で必要なMP

for i in range(1, H+1):
    if dp[i-1][1] > 0:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1] - 1
    else:
        for A, B in AB:
            if A > i:
                if dp[i][0] > B:
                    dp[i][0] = B
                    dp[i][1] = A - i
            else:
                if dp[i][0] > dp[i - A][0] + B:
                    dp[i][0] = dp[i-A][0] + B
                    dp[i][1] = dp[i-A][1] + A - i

print(dp[H][0])


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]

dp = [[10**10, 0] for i in range(H+1)]
dp[0][0] = 0
# i 減らすのに最小で必要なMP

for i in range(1, H+1):
    if dp[i-1][1] > 0:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1] - 1
    else:
        for A, B in AB:
            if A > i:
                if dp[i][0] > B:
                    dp[i][0] = B
                    dp[i][1] = A - i
            else:
                if dp[i][0] > dp[i - A][0] + B:
                    dp[i][0] = dp[i-A][0] + B
                    dp[i][1] = dp[i-A][1] + A - i

print(dp[H][0])
### BUGGY CODE ###

s = input()
index = []
for i in range(len(s)):
    if s[i] == "?":
        index.append(i)
        
mini = s
for i in index:
    if i != 0 or i!= len(s) - 1:
        mini = mini[:i] + "0" + mini[i+1:]
    elif i == 0:
        mini = "0" + mini[1:]
    elif i == len(s) - 1:
        mini = mini[:len(s)-1] + "0"
mini = int(mini)

maxi = s
for i in index:
    if i != 0 or i!= len(s) - 1:
        maxi = maxi[:i] + "9" + maxi[i+1:]
    elif i == 0:
        maxi = "9" + maxi[1:]
    elif i == len(s) - 1:
        maxi = maxi[:len(s)-1] + "9"
maxi = int(maxi)

count = 0
for i in range(mini,maxi+1):
    if i % 13 == 5:
        flag = True
        i_str = str(i)
        if len(i_str) < len(s):
            i_str = "0" * (len(s) - len(i_str)) + i_str
        for j in range(len(s)):
            if s[j] == "?" or i_str[j] == s[j]:
                continue
            else:
                flag = False
                break
        if flag == True:
            count += 1
print(count % (10**9 + 7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    start = (0, (-1,-1))
    hq = [start]
    heapify(hq)
    count = -2
    footprint = set()
    while True:
        if len(hq) == 0:
            break
        cost, (i, j) = heappop(hq)
        if cost > K:
            break
        if (i, j) in footprint:
            continue
        footprint.add((i,j))
        count = max(count, i+j)
        #print(f"cost={cost} i={i} j={j}")

        if i+1 < len(A):
            heappush(hq, (cost + A[i+1], (i+1, j)))
        if j+1 < len(B):
            heappush(hq, (cost + B[j+1], (i, j+1)))

    print(count+2)



if __name__ == '__main__':
    main()

### FIXED CODE ###

from bisect import bisect_right
import numpy as np
def main():
    N, M, K = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())), dtype=np.int64)
    B = np.array([0] + list(map(int, input().split())), dtype=np.int64)

    As = np.cumsum(A)
    Bs = np.cumsum(B)

    count = 0

    for i, a in enumerate(As):
        if a > K:
            break
        j = bisect_right(Bs, K-a)
        #print(f"i={i} j={j} Bs={Bs} cost={K-a}")
        count = max(count, (i+j-1))

    print(count)

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

import math
K = int(input())
result = 0
sum = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            result = math.gcd(a, b)
            sum += math.gcd(result, c)

print(sum)            


### FIXED CODE ###

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

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    X = np.argsort(A)
    Y = np.argsort(B)

    cmax = 0
    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))
        cmax = max(cmax, int(c))
    ret = A[X[0]]+B[Y[0]]

    for x in X:
        for y in Y:
            if ret < A[x]+B[y]-cmax:
                break
            ret = min(ret, A[x]+B[y]-XYC.get((x, y), 0))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = min(A)+min(B)
    for (x, y), c in XYC.items():
        ret = min(ret, A[x]+B[y]-c)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

""" AtCoder """

N, Q = map(int, input().split())
S = input()
S += 'A'
lr = [list(map(int, input().split())) for _ in range(Q)]

l = []
pos = 0

for i in range(N):
    if S[i] + S[i + 1] == "AC":
        l.append(1)
    else:
        l.append(0)

for i in range(Q):
    tmp = l[lr[i][0] - 1:lr[i][1]]
    ans = sum(tmp)
    if tmp[-1] == 1:
        ans -= 1
    print(ans)


### FIXED CODE ###

""" AtCoder """

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

tmp = 0
l = [0]

for i in range(1, N):
    if S[i - 1] + S[i] == "AC":
        tmp += 1
    l.append(tmp)

for i in range(Q):
    print(l[lr[i][1]-1] - l[lr[i][0]-1])
### BUGGY CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        for ndk in ndp:
            ndk %= md

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int,list(input())))
d = int(input())
f(ks, d)


### FIXED CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        ndp = [ndk % md for ndk in ndp]

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# print(A)
dis=[[-1]*w for i in range(h)]
hq=[]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
heapq.heapify(hq)
while hq:
    count,i,j=heapq.heappop(hq)
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            heapq.heappush(hq, (count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            # print(count+1)
ans=0
for Ai in dis:
    ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

    
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
acc[0] = 0
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        set_ans.add(acc[j+1] - acc[i])
        s = acc[j+1] - acc[i]
        index = 41
        while s :
            if s & 1:
                stand_bit[index].add(acc[j+1] - acc[i])
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        tmp = acc[j+1] - acc[i]
        set_ans.add(tmp)
        s = tmp
        index = 41
        while s:
            if s & 1:
                stand_bit[index].add(tmp)
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)
### BUGGY CODE ###


def muridesu():
    N,K=[int(_) for _ in input().split()]
    aA=[int(_) for _ in input().split()]
    dsA = set(aA)
    def f(i,N,aA):
        return sum(i^aA[j] for j in range(N))

    print(max(f(k,N,aA) for k in (set(range(1,K+1)) - dsA  | {0})))
muridesu()


### FIXED CODE ###

#場合分けがつらい
def 解():
    N,K=[int(_) for _ in input().split()]
    aD =[0]*40
    aA=[int(_) for _ in input().split()]
    iL = 0
    for i in range(40):
        m = 2**i
        aD[i]=sum((_ & m) for _ in aA)
        if aD[i]:
            iL = i
    iLK = len(bin(K))-3
    iML = max(iL,iLK)
    dp = [[0]*2 for _ in range(2)]
    #[x][0] Kに沿う
    #[x][0] Kに沿わない最大
    for i in range(iML,-1,-1):
        ib = i%2 #桁%2 dp
        inb = 0 if ib else 1 #次のdp
        i0 = aD[i] #反転しない
        i1 = (2**i)*N-i0 #反転する
        iM = max(i0,i1) #選べるとき
        bL = i < iLK #Kより長い
        if (K>>i)&1:
            dp[inb][1] = dp[ib][1] + i1
            dp[inb][0] = max(dp[ib][1] + i0 ,dp[ib][0]+(iM if bL else i0))
        else:
            dp[inb][1] = dp[ib][1] + i0
            dp[inb][0] = dp[ib][0] + (iM if bL else i0)
    print(max(dp[inb]))
解()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
l = {}
r = {}
for i in range(n):
    p = i+a[i]
    q = i-a[i]
    if p in l:
        l[p] = l[p]+[i]
    else:
        l[p] = [i]
    if q in r:
        r[q] = r[q]+[i]
    else:
        r[q] = [i]
ans = 0
for i in l:
    if i in r:
        ans+= len(l[i])*len(r[i])
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l = {}
r = {}
for i in range(n):
    p = i+a[i]
    q = i-a[i]
    if p < n:
        if p in l:
            l[p] = l[p]+1
        else:
            l[p] = 1
    if q > 0:
        if q in r:
            r[q] = r[q]+1
        else:
            r[q] = 1
ans = 0
for i in l:
    if i in r:
        ans+= l[i]*r[i]
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
array = []
array2 = []
for i in range(L,R+1):
    array2.append(i%2019)
array2 = list(set(array2))
for i in range(len(array2)):
    for j in range(len(array2)):
        if i < j:
            m = (array2[i]%2019)*(array2[j]%2019)
            array.append(m%2019)
print(min(array))

### FIXED CODE ###

L,R = map(int,input().split())
array = []
array2 = []
if R+1 - L <= 2019:
    for i in range(L,R+1):
        if i%2019 not in array2:
            array2.append(i%2019)

    for i in range(len(array2)):
        for j in range(len(array2)):
            if i < j:
                array.append((array2[i]*array2[j])%2019)
    print(min(array))
else:
    for i in range(1,2020):
        if i%2019 not in array2:
            array2.append(i%2019)

    for i in range(len(array2)):
        for j in range(len(array2)):
            if i < j:
                array.append((array2[i]*array2[j])%2019)
    print(min(array))
### BUGGY CODE ###

n, k = list(map(int, input().split(' ')))
aaa = sorted(list(map(int, input().split(' '))))
mmm = 1000000000 + 7
# 二項係数 mod [検索]
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    return fac[a] * (inv_fac[b] * inv_fac[a-b] % mmm) % mmm

ans = 0
init(1000000)
for st in range(n):
    for ed in range(st+1, n):
        choice_pattern = choice(ed-1 - st, k-2)  # [st + 1: ed - 1] の範囲から k-2個取るパターン数
        ans = (ans + (aaa[ed] - aaa[st]) * choice_pattern) % mmm
        # print(st, ed, ':::', ed-1 - st, k-2, "stCed=", choice_pattern, 'hoge=', (aaa[ed]-aaa[st]), ans)
print(ans)

### FIXED CODE ###

n, k = list(map(int, input().split(' ')))
aaa = sorted(list(map(int, input().split(' '))))
mmm = 1000000000 + 7
# 二項係数 mod [検索]
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    return fac[a] * (inv_fac[b] * inv_fac[a-b] % mmm) % mmm
ans = 0
init(1000000)
for target in range(n):
    p_pattern = choice(target, k-1)
    #print(target, k-1, 'p_choice', choice(target, k-1))
    n_pattern = choice(n-target-1, k-1)
    #print(n-target-1, k-1, 'n_choice', choice(n-target-1, k-1))
    ans = (ans + aaa[target] * p_pattern - aaa[target] * n_pattern) % mmm
    #print(aaa[target], target-1, n-target, k-1, p_pattern, n_pattern)
print(ans % mmm)
### BUGGY CODE ###

def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

N, M = ints()
A = ints()

H = []
for i in range(N):
  for j in range(N):
    x = A[i]+A[j]
    H.append((x, i, j))
H.sort()
H = list(reversed(H))
s = 0
for i in range(M):
  s += H[i][0]
print(s)


### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

N, M = ints()
A = ints()
A.sort()

def combinations(x):
  s = 0
  i = 0
  j = N-1
  while j>=0:
    while i<N and A[i]+A[j]<x:
      i += 1
    s += N-i

    j -= 1
    
  return s

def koufukudo(x):
  s = 0
  si = 0
  j = 0
  i = N-1
  while j<N:
    while i>=0 and A[i]+A[j]>=x:
      si += A[i]
      i -= 1
    s += si + A[j]*(N-1-i)

    j += 1
    
  return s


def bsearch(lower, upper):
  l = lower
  u = upper
  m = (l+u)//2
  c = combinations(m)
  if c<M:
    return bsearch(l, m)
  else:
    if l==m:
      return (l, c-M)
    return bsearch(m, u)

x, dm = bsearch(0, A[-1]*2+1)
print(koufukudo(x)-dm*x)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
temp=1
for i in range(k): temp*=a[i]
for i in range(k,n,1):
    temp2=temp
    temp//=a[i-k]
    temp*=a[i]
    if temp2>=temp: print("No")
    else: print("Yes")

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
temp=1
for i in range(k,n,1):
    if a[i-k]>=a[i]: print("No")
    else: print("Yes")