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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9 + 7

def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)
def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)

euler = []
def dfs(pre,now):
    euler.append(now)
    for to in G[now]:
        if to == pre:
            continue
        dfs(now,to)
    euler.append(pre)

dfs(-1,0)

data = [[] for i in range(n)]
last = [-1]*n
for i,x in enumerate(euler[:-1]):
    if last[x] == -1:
        last[x] = i
        continue
    data[x].append((i-last[x])//2)
    last[x] = i

for i in range(n):
    if sum(data[i]) == n-1:
        continue
    data[i].append(n-1-sum(data[i]))

two = [1]
now = 1
for i in range(n):
    now *= 2
    now %= mod
    two.append(now)

ans = 0
for i in range(n):
    now = 1
    for x in data[i]:
        now += two[x]-1
        now %= mod
    ans += two[n-1]-now
    ans %= mod


ans *= pow(two[n],mod-2,mod)
ans %= mod

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

for _ in range(n-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

d_to_i = [[] for _ in range(n)]

for i in range(n):
    d_to_i[depth[i]].append(i)

data = [[] for _ in range(n)]

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)
### BUGGY CODE ###

if __name__ == "__main__":
    
    n = int(input())

    for o in range(1, n+1):
        for x in range(1, 100):
            isFound = False
            for y in range(1, x+1):
                for z in range(1, y+1):
                    m = x**2+y**2+z**2+x*y+y*z+z*x
                    if m == o:
                        isFound = True
                        if x==y and y==z: print(1)
                        elif x==y or y==z or z==x: print(3)
                        else: print(6)
                        break
                    elif m > o:
                        break
                if isFound: break
            if isFound: break
        if not isFound: print(0)

### FIXED CODE ###

if __name__ == "__main__":
    
    n = int(input())

    """for o in range(1, n+1):
        s = 1
        if o > 6:
            s = -1 + int((o-2)**0.5)
        for x in range(s, 100):
            isFound = False
            for y in range(1, x+1):
                for z in range(1, y+1):
                    m = x**2+y**2+z**2+x*y+y*z+z*x
                    if m == o:
                        isFound = True
                        if x==y and y==z: print(1)
                        elif x==y or y==z or z==x: print(3)
                        else: print(6)
                        break
                    elif m > o:
                        break
                if isFound: break
            if isFound: break
        if not isFound: print(0)"""

    ans = [0 for _ in range(10001)]
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                m = x**2+y**2+z**2+x*y+y*z+z*x
                if m > 10000: break
                ans[m] += 1

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

s = input()
t = input()
a = len(s)
b = len(t)
dp = [[0]*(b+1) for _ in range(a+1)]
prev_w = [[0]*(b+1) for _ in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      if dp[i][j]+1>dp[i+1][j+1]:
        dp[i+1][j+1] = dp[i][j]+1
        prev_w[i+1][j+1] = [i,j]
    else:
      if dp[i+1][j]>dp[i][j+1]:
        dp[i+1][j+1]=dp[i+1][j]
        prev_w[i+1][j+1] = [i+1,j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
        prev_w[i+1][j+1] = [i,j+1]
#print(dp[a][b])
#print(prev_w[1][3])
ans = ''
while a!=0 and b !=0:
  l = dp[a][b]
  a,b=prev_w[a][b]
  if l>dp[a][b]:
    ans =s[a]+ans
print(ans)

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = (i,j)
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

dp=[[0]*2019 for _ in range(2)]

p=0
cnt=0
for c in sys.stdin.readline().strip():
    x=int(c)

    for i in range(2019):
        dp[(p+1)&1][(i*10+x)%2019]=dp[p][i]
    dp[(p+1)&1][x]+=1
    p=(p+1)&1
    cnt+=dp[p][0]

print(cnt)

### FIXED CODE ###

from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

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

import bisect
n=int(input())
A=list(map(int,input().split()))

X=[A[i]-(i+1) for i in range(n)]
Y=[-A[i]-(i+1) for i in range(n)]
ans=0
X.sort()

for y in Y:
    i=bisect.bisect_left(X,y)
    for j in range(i,n):
        if X[j]==y:
            ans+=1
        else:
            break
print(ans)

### FIXED CODE ###

from _collections import defaultdict
n=int(input())
A=list(map(int,input().split()))

X=[A[i]-(i+1) for i in range(n)]
Y=[-A[i]-(i+1) for i in range(n)]
ans=0

P=defaultdict(int)
Q=defaultdict(int)

for x in X:
    P[x]+=1
for y in Y:
    Q[y]+=1

p=set(P.keys())
q=set(Q.keys())

r=p&q

for key in r:
    ans+=P[key]*Q[key]
print(ans)
### BUGGY CODE ###

# encoding: "utf-8"

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    ys = {i: xs.count(i) for i in set(xs)}
    counts = [ys.get(x-1, 0) + ys.get(x, 0) + ys.get(x+1, 0) for x in ys.keys()]
    print(max(counts))

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0] * (1 << (N)) for _ in range(N + 1)]

dp[0][0] = 1
# for tmp in dp:
#     print (tmp)

for i in range(N):
    for j in range(N):
        if A[i][j] == 0: #仲良くない時
            continue
        #以下仲が良い時のみの処理
        for k in range(1 << N):
            if (1 << j) & k == 0: #まだペアになっていない女の人の時
                dp[i + 1][k + (1 << j)] = (dp[i + 1][k + (1 << j)] + dp[i][k]) % MOD
        # print (dp[i + 1])

print (dp[N][(1 << N) - 1])    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())

A = [tuple(map(int, input().split())) for _ in range(N)]

dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
    if dp[group] != -1:
        return dp[group]
    res = 0
    for i in range(N):
        if (group >> i) & 1 == 0 and A[count][i] == 1:
            res += dfs(group + (1 << i), count + 1)
    dp[group] = res % MOD
    return dp[group]

tmp = dfs(0, 0)

print (tmp)
### BUGGY CODE ###

import collections
import itertools

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

s = [0]
for i in range(1, n + 1):
    s.append(s[i-1] + a[i-1] )

print(sum([len(list(itertools.combinations(list(range(i)), 2))) for i in collections.Counter(s).values()]))


### FIXED CODE ###

import collections
import math

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

s = [0]
for i in range(1, n + 1):
    s.append(s[i-1] + a[i-1] )

ans = 0
for v in collections.Counter(s).values():
    if v >= 2:
        ans += math.factorial(v) // (math.factorial(v - 2) * math.factorial(2))
print(ans)
### BUGGY CODE ###


n=int(input())

def digsum(n):
    res = 0
    while n > 0 :
        res += n%10
 #       res +=1
        n =n// 10
    return res

nn=digsum(n)
if nn%9==0:
    print("Yes")
else:
    print("No")
    

### FIXED CODE ###

n=input()

nn=0
for i in range(len(n)):
    nn+=int(n[i])

if nn%9==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][2]
        dp[i + 1][3] = dp[i][3]
        if s == '?':
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = dp[i][2] * 3 + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))
            dp[i + 1][3] = dp[i][3] + dp[i][2] * (3 ** (total - cnt - 1))
            cnt += 1
        elif s == 'A':
            dp[i + 1][0] = dp[i][0] + 1
        elif s == 'B':
            dp[i + 1][2] = dp[i][2] + (dp[i][0] * int(3 ** cnt)) + (dp[i][1] * int(3 ** (cnt - 1)))
        elif s == 'C':
            dp[i + 1][3] = dp[i][3] + dp[i][2] * (3 ** (total - cnt))
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    total = 0
    for s in S:
        if s == '?':
            total += 1
    tri = [1]
    for i in range(1, total + 1):
        tri.append(tri[i - 1] * 3 % MOD)
    n = len(S)
    dp = [[0] * 4 for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        s = S[i]
        #dp[i + 1][0] = dp[i][0]
        #dp[i + 1][1] = dp[i][1]
        #dp[i + 1][2] = dp[i][2]
        #dp[i + 1][3] = dp[i][3]
        if s == '?':
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1] + 1
            dp[i + 1][2] = (dp[i][2] * 3 + dp[i][0] * tri[cnt] + dp[i][1] * tri[cnt - 1]) % MOD
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * tri[total - cnt - 1]) % MOD
            cnt += 1
        elif s == 'A':
            dp[i + 1][0] = dp[i][0] + 1
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = dp[i][3]
        elif s == 'B':
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = (dp[i][2] + dp[i][0] * tri[cnt] + dp[i][1] * tri[cnt - 1]) % MOD
            dp[i + 1][3] = dp[i][3]
        elif s == 'C':
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
            dp[i + 1][3] = (dp[i][3] + dp[i][2] * tri[total - cnt]) % MOD
    #print(dp)
    ret = dp[n][3] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

def main():
    s = input()
    mod = 1000000007
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1
    k = 1
    for i in range(n):
        t = 0
        for j in range(10):
            if s[n-i-1]=="?":
                for l in range(13):
                    dp[i+1][(l+t)%13]+=dp[i][l]
                    dp[i+1][(l+t)%13]%=mod
            elif int(s[n-i-1])==j:
                for l in range(13):
                    dp[i+1][(l+t)%13]+=dp[i][l]
                    dp[i+1][(l+t)%13]%=mod
            t+=k
            t%=13
        k=t
    print(dp[n][5])

if __name__ == '__main__':
    main()

### FIXED CODE ###

s = input()
mod = 1000000007
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
k = 1
for i in range(n):
    t = 0
    for j in range(10):
        if s[n-i-1]=="?":
            for l in range(13):
                dp[i+1][(l+t)%13]+=dp[i][l]
                dp[i+1][(l+t)%13]%=mod
        elif int(s[n-i-1])==j:
            for l in range(13):
                dp[i+1][(l+t)%13]+=dp[i][l]
                dp[i+1][(l+t)%13]%=mod
        t+=k
        t%=13
    k=t
print(dp[n][5])
### BUGGY CODE ###

def solve(N, Q, S, L_R):
    answers = [0] * Q
    ac_index = list()
    for i in range(len(S) - 1):
        s = S[i:i + 2]
        if s == "AC":
            for j in range(len(L_R)):
                l, r = L_R[j]
                if l <= i + 1 < r:
                    answers[j] += 1
    return answers


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

### FIXED CODE ###

def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)
### BUGGY CODE ###

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

for i in range(k):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
print(" ".join(list(map(str,ans))))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))

for i in range(min(k,500)):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
print(" ".join(list(map(str,ans))))
### BUGGY CODE ###

N = int(input())
total = 0
for i in range(1, N):
  total += i
  
print(total)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
total = sum(range(1, N))
  
print(total)
### BUGGY CODE ###

# -*- coding:utf-8 -*-

comb_dic = {}

def combination_formula_MOD(n, r, MOD):
    """nCrを O(min(n-r, r)) で高速に計算する"""
    def _inv(x, MOD):
        """xの逆元を返す"""
        return pow(x, MOD-2, MOD)
    if r > n: return 0

    if (n,r) in comb_dic:
        return comb_dic[(n,r)]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)%MOD
        bunbo = bunbo*(i+1)%MOD

    ans = (bunsi*_inv(bunbo, MOD))%MOD
    comb_dic[(n,r)] = ans
    return ans


def combination_formula(n, r):
    """nCrは、O(min(n-r, r))で実装する
    Notes:
        分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
        求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
    """
    if r > n: return 0

    if (n,r) in comb_dic:
        return comb_dic[(n,r)]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)
        bunbo = bunbo*(i+1)

    comb_dic[(n,r)] = bunsi//bunbo
    return bunsi//bunbo


def solve():
    N = int(input())
    As = list(map(int, input().split()))
    MOD = 10**9+7

    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    ans_dic = {}  # すでに答えを計算したもの
    for a in As:
        if not a in ans_dic:
            ans = 0
            for key, value in dic.items():
                if key == a:
                    value -= 1
                ans += combination_formula(value, 2)
                # ans += combination_formula_MOD(value, 2, MOD)
            ans_dic[a] = ans
            print(ans_dic[a])
        else:
            print(ans_dic[a])



if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-

comb_dic = {}


def combination_formula(n, r):
    """nCrは、O(min(n-r, r))で実装する
    Notes:
        分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
        求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
    """
    if r > n: return 0

    if n in comb_dic:
        return comb_dic[n]

    r = min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(r):
        bunsi = bunsi*(n-i)
        bunbo = bunbo*(i+1)

    comb_dic[n] = bunsi//bunbo
    return comb_dic[n]


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    # combination_formula(v, 2)はくっそ早いので、
    # しゃくとりっぽく解く
    total = 0
    for key, value in dic.items():
        total += combination_formula(value, 2)

    for a in As:
        ans = total
        ans -= combination_formula(dic[a], 2)
        ans += combination_formula(dic[a]-1, 2)
        print(ans)


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

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

ans = 1
for a in A:
    ans *= a

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

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
    exit()
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set()
    queue.add(s)
    visited = [0] * n
    visited[s] = 1
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        for f in g[i]:
            if not visited[f]:
                visited[f] = 1
                group_ids[f] = gid
                queue.add(f)


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def extgcd(a,b):
    a0,b0=a,b
    x0,y0=1,0
    x1,y1=0,1

    while b0!=0:
        q = a0 // b0
        r = a0 % b0

        a0,b0=b0,r
        x0,x1=x1,x0-q*x1
        y0,y1=y1,y0-q*y1

    return a0,x0,y0

def mo(x,mod):
    return (mod+x%mod)%mod

def inv(a,mod):
    g,x,y=extgcd(a,mod)
    ans=mo(x,mod)
    return ans

def combi_mod(n,k):
    invlist = [1]
    for i in range(1, k + 1):
        temp = inv(i, mod)
        invlist.append(temp)
    k1 = 1
    k3 = 1

    for i in range(n, 0, -1):

        if i > n - k:
            k1 *= i
        if i < k + 1:
            k3 *= invlist[i]
    ans = k1 * k3
    ans = ans % mod
    return ans

A.sort()

ans=0

if N-K<=K-1:
    for i in range(N):
        if i<=N-K:
            ans -= A[i] * combi_mod(N - i - 1, K - 1)
        elif N-K+1<=i<K-1:continue
        elif K-1<=i:
            ans += A[i] * combi_mod(i, K - 1)
else:
    for i in range(N):
        if i<K-1:
            ans -= A[i] * combi_mod(N - i - 1, K - 1)
        elif K-1<=i<=N-K:
            ans=ans+A[i] * combi_mod(i, K - 1)-A[i] * combi_mod(N - i - 1, K - 1)
        else:
            ans += A[i] * combi_mod(i, K - 1)
ans%=mod
print(ans)




### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

fac=[]
finv=[]
inv=[]
def combi_init():
    fac.append(1)
    fac.append(1)
    finv.append(1)
    finv.append(1)
    inv.append(1)
    inv.append(1)

    for i in range(2,N+1):
        fac.append(fac[i-1]*i%mod)
        inv.append(mod-mod//i*inv[mod%i]%mod)
        finv.append(finv[i-1]*inv[i]%mod)

def combi_mod(n,k):

    ret=fac[n]*finv[n-k]*finv[k]%mod
    return ret

A.sort()

ans=0
combi_init()
for i in range(N-1,K-2,-1):
    ans+=(A[i]-A[(N-1)-i])*combi_mod(i,K-1)


ans%=mod

print(ans)