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

import math
n = int(input())
a = list(map(int,input().split()))
list_S = [0]
S = 0
ans = 0
for i in range(n):
    S += a[i]
    list_S.append(S)
S_set = list(set(list_S))
for i in range(len(S_set)):
    I = list_S.count(S_set[i])
    if 3 <= I:
        ans += math.factorial(I) // (math.factorial(I-2)*2)
    elif I == 2:
        ans += 1
    else:
        pass
print(ans)


### FIXED CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
dic_S = {0:[0]}
S = 0
ans = 0
for i in range(n):
    S += a[i]
    if S not in dic_S:
        dic_S[S] = []
    else:
        pass
    dic_S[S].append(a[i])
    

for k in dic_S.keys():
    I = len(dic_S[k])
    if 3 <= I:
        ans += math.factorial(I) // (math.factorial(I-2)*2)
    elif I == 2:
        ans += 1
    else:
        pass
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

#print(bin(dpm[-1]))
r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
#    print(bin(dpm[N-i-1]))
    tmp = dpm[N-i-1]
    for j in range(1, a):
        tmp |= tmp>>1
#    print(bin(tmp), bin(dp2), len(bin(tmp)))
    if not dp2&tmp:
#        print("aa")
        r += 1
#    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
#        if dp2&(1<<j) and dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
            # K-j > x >= K-j-a
#            break
#    else:
#        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    for j in range(a):
        if dp2 & dpm[N-i-1]:
            break
        dpm[N-i-1] >>= 1
    else:
        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)
### BUGGY CODE ###

n, m = map(int, input().split())
count = [0]*(n+1)
for i in range(m):
    l, r = map(int, input().split())
    for j in range(l, r+1):
        count[j] += 1
        
print(count.count(m))

### FIXED CODE ###

N, M = map(int, input().split())
l, r = -1, N+1
for _ in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
ans = max(0, r-l+1)
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline

N = int(input())
INF = float('inf')
graph = [[INF] * N for _ in range(N)]

for i in range(N):
    graph[i][i] = 0

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    graph[u][v] = w
    graph[v][u] = w

distance = floyd_warshall(graph, directed=False)

print(0)
for i in range(1, N):
    if int(distance[0][i]) % 2 == 0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
read = sys.stdin.read


N = int(readline())
graph = [[] for _ in range(N + 1)]

for i in readlines():
    u, v, w = map(int, i.split())
    graph[u].append((v, w))
    graph[v].append((u, w))

stack = [1]
parent = [0] * (N + 1)
color = [0] * (N + 1)

while stack:
    here = stack.pop()
    for x, w in graph[here]:
        if x == parent[here]:
            continue
        parent[x] = here
        color[x] = color[here] ^ (w % 2)
        stack.append(x)

for i in color[1:]:
    print(i)
### BUGGY CODE ###

import bisect
N=int(input())

que=[-1]
for i in range(N):
    a=int(input())
    i=bisect.bisect_left(que, a)
    if i!=0:
        que[i-1]=a
    else:
        que=[a]+que

print(len(que))


### FIXED CODE ###

import bisect
from collections import deque
N=int(input())

que=deque([-1])
for i in range(N):
    a=int(input())
    
    if que[0]<a:
        i=bisect.bisect_left(que, a)
        que[i-1]=a
    else:
        que.appendleft(a)

print(len(que))
#print(que)
### BUGGY CODE ###

ignore = input()
num = map(int,input().split())
count = 0
while True:
    if(sum([0 if i%2 == 0 else 1 for i in num]) == 0):
        num = [i/2 for i in num]
        count += 1
    else:
        print(count)
        break

### FIXED CODE ###

import math

ignore = input()
num = map(int,input().split())
score = []
for i in num:
    temp = i
    while i%2 == 0:
        i = i/2
    score.append(temp/i)
print(int(math.log(min(score),2)))
### BUGGY CODE ###

s = input()
Q = int(input())
flag = True  # flagがTrueのとき、偶数回数の反転が行われている
cnt = 0
for _ in range(Q):
    query = list(map(str, input().split()))
    # tmp.append(query)
    if len(query) == 1:  # 1のqueryのとき
        cnt += 1
        if flag:
            flag = False
        else:
            flag = True
    else:
        f, c = query[1], query[2]
        if f == "1":  # 先頭に追加するもの
            if flag:
                s = c + s  # 偶数回の反転なら素直に先頭に追加する
            else:
                s += c  # 奇数会の反転なら後ろに追加する
        else:  # 末尾に追加する
            if flag:
                s += c
            else:
                s = c + s

if cnt % 2 == 1 and cnt != 0:
    s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
Q = int(input())
flag = True  # flagがTrueのとき、偶数回数の反転が行われている
cnt = 0
query = [list(map(str, input().split())) for _ in range(Q)]
before = []  # 先頭に追加する時
after = []  # 末尾に追加する時
for i in range(Q):
    a = query[i]
    if len(a) == 1:  # 1のqueryのとき
        cnt += 1
        if flag:
            flag = False
        else:
            flag = True
    else:
        f, c = a[1], a[2]
        if f == "1":  # 先頭に追加するもの
            if flag:
                # s = c + s  # 偶数回の反転なら素直に先頭に追加する
                before.append(c)
            else:
                # s += c  # 奇数会の反転なら後ろに追加する
                after.append(c)
        else:  # 末尾に追加する
            if flag:
                # s += c  # 末尾に追加
                after.append(c)
            else:
                # s = c + s  # 先頭に追加
                before.append(c)
before.reverse()
# print(before)
# print(s)
# print(after)
s = "".join(before) + s + "".join(after)
if cnt % 2 == 1 and cnt != 0:
    s = s[::-1]
print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    ans=1
    for i in range(1,N):
        if P[i]<=min(P[:i]):
            ans+=1
    print(ans)
    return


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

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    ans=1
    mi=P[0]
    for i in range(1,N):
        if P[i]<=mi:
            ans+=1
            mi=P[i]
            
    print(ans)
    return


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

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

import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        tmp = 4*h*n-N*(n+h)
        if tmp == 0:
            continue
        d,m = divmod(N*h*n, tmp)
        if m == 0 and d > 0:
            print(h,n,d)
            sys.exit()

### FIXED CODE ###

import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        tmp = 4*h*n-N*(n+h)
        if tmp == 0:
            continue
        d,m = divmod(N*h*n, tmp)
        if m == 0 and d > 0:
            print(h,n,d)
            sys.exit()
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
ans=1
for i in range(n):
    ans*=a[i]
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

import math


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return math.floor(math.factorial(n) / math.factorial(n - 2) / 2)


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

d = {}

for ai in aL:
    if ai in d:
        d[ai] += 1
    else:
        d[ai] = 1

for ai in aL:
    sm = 0
    for dk, di in d.items():
        if dk == ai:
            sm += kumiawase(di - 1)
        else:
            sm += kumiawase(di)
    print(sm)

### FIXED CODE ###

import math
import collections


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return (n**2 - n) // 2


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

d = collections.Counter(aL)

s = 0
for i in d.values():
    s += kumiawase(i)

for a in aL:
    print(s - d[a] + 1)
### BUGGY CODE ###

N = int(input())
biki = []
bise = {}
for i in range(N):
    S = input()
    biki.append(S)
    bise=set(biki)
print(len(bise))

### FIXED CODE ###

N = int(input())
biki = []
bise = {}
for i in range(N):
    S = input()
    biki.append(S)
bise=set(biki)
print(len(bise))
### BUGGY CODE ###

import bisect

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
for i in range(M):
    x = A.pop()
    bisect.insort(A, x/2)
print(sum(map(int, A)))

### FIXED CODE ###

import bisect

N, M = list(map(int, input().split()))
A = list(map(lambda x: int(x) * -1, input().split()))
A.sort()

cnt = 1
while cnt <= M:
    x = bisect.bisect(A, A[0]/2)
    for i in range(x):
        A[i] /= 2
        cnt += 1
        if cnt > M:
            break
    if x != 0 or x != len(A):
        A.sort()
print(sum(map(lambda x: int(-x), A)))
### BUGGY CODE ###

import bisect

n = int(input())

A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

ans = 0

for a in A:
  i = bisect.bisect_right(B, a)
  for b in B[i:]:
    j = bisect.bisect_right(C, b)
    ans += n-j
    
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0

for b_i in B:
  top_n = bisect.bisect_left(A, b_i)
  bottom_n = n-bisect.bisect_right(C, b_i)
  ans += top_n*bottom_n
  
print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
# print('N=', N, 'K=', K, 'Q=', Q)

participant_list = [K] * N
# for i in range(N):
#     participant_list.append(K)
# print(participant_list)

def calc_decre(n):
    return n - 1

for i in range(Q):
#     print('num=', i)
    participant_list = list(map(calc_decre, participant_list))
#     print(participant_list)

#     for i in range(N):
#         participant_list[i] -= 1 
    answer = int(input()) - 1
    participant_list[answer] += 1
#     print(participant_list)

for i in participant_list:
    if i <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N, K, Q = map(int, input().split())
# print('N=', N, 'K=', K, 'Q=', Q)

participant_list = [K-Q] * N
# print(participant_list)

for i in range(Q):
    participant_list[int(input())-1] += 1
    
for i in participant_list:
    if i <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n = int(input())
ab = [list(map(int, input().split())) for i in range(n)][::-1]

ans = 0
for a, b in ab:
    tmp = a
    while tmp % b != 0:
        tmp += 1
    for i in range(n):
        ab[i][0] += tmp - a
    ans += tmp - a
print(ans)

### FIXED CODE ###

n = int(input())
ab = [list(map(int, input().split())) for i in range(n)][::-1]

ans = 0
for a, b in ab:
    a += ans
    # 負の剰余。
    ans += -a % b
print(ans)
### BUGGY CODE ###

N = int(input())
my_list = [None] * N
for i in range(N):
    s_i = sorted(list(input()))
    my_list[i] = s_i
sum = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if my_list[i] == my_list[j]:
            sum += 1
print(sum)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = str(sorted(input()))
    if s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1
print(ans)
### BUGGY CODE ###

import copy
S = input()

Sr = S.split('L')
R_max = len(max(Sr,key=len))
Sl = S.split('R')
L_max = len(max(Sl,key=len))
Slen = len(S)
Sc = [1] * Slen
Sc_ = [0] * Slen

S_try = max(L_max,R_max)
if S_try % 2 == 1:
    S_try += 1

for _ in range(S_try):
    for i in range(Slen):
        if S[i] == 'L':
            Sc_[i - 1] += Sc[i]
        elif S[i] == 'R':
            Sc_[i + 1] += Sc[i]
    Sc = copy.deepcopy(Sc_)
    Sc_ = [0] * Slen

print(" ".join(map(str,Sc)))



### FIXED CODE ###

import copy
S = input()
Slen = len(S)

Sc=[0]*Slen
for i in range(Slen):
    if S[i:i+2] == 'RL':
        for j in range(i,-1,-1):
            if S[j]=='R':
                Sc[(i-j)%2 + i] += 1
            else:
                break
        for j in range(i+1,Slen):
            if S[j] == 'L':
                Sc[(j-i)%2 +i] += 1
            else:
                break    

print(" ".join(map(str,Sc)))
### BUGGY CODE ###

#import numpy as np

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

#print(A)

S = [0 for i in range(n)]
#F = [[0 for i in range(n)] for j in range(2*n*n)]

n1n = n*(n-1)
nm2 = n - 2
nm1 = n - 1
maxga = n//2

d = 0
for ii in range(n*n*2):
    F = [0 for i in range(n)]
    co = 0
    i = 0
    ga = 0
    for jj in range(n*n*2):
        si = S[i]
        if F[i] == 0 and si <= nm2:
            aite = A[i][si]
            #print(S)
            #print("aite",aite)
            if aite < n and A[aite][S[aite]] == i and F[aite] == 0:
                #print("g", i, aite)
                S[i] += 1
                S[aite] += 1
                F[i] = 1
                F[aite] = 1
                co = 0
                ga += 1
        i = (i+1) % n
        co += 1
        if co == nm1 or ga == maxga:
            break
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == n1n:
            print(d-1)
        else:
            print(-1)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

#@profile
def extract(A):
    out = A[1]
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    return out

_input = sys.stdin.readlines()
A = [0]
out=[]

#@profile
def main():
    for l in _input:
        if l[0] == "i":
            #insert k
            k = int(l.split()[1])
            A.append(k)
            #build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(*out, sep = "\n")
            return
        else:
            build_max_heap(A)
            #print(A)
            out.append(extract(A))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

#@profile
def max_heapify(A, i):
    j = i
    largest = i
    H = len(A) -1
    while True:
        l = j * 2
        r = l + 1
        if l <= H and A[l] > A[j]:
            largest = l
        if r <= H and A[r] > A[largest]:
            largest = r
        if largest != j:
            A[j], A[largest] = A[largest], A[j]
            #max_heapify(A, largest)
            j = largest
            
        else:
            break
        

#@profile
def build_max_heap(A):
    i = len(A)-1
    last = A[i]
    parent = i//2
    while  parent > 0 and A[parent] < last:
        A[i] = A[parent]
        i = parent
        parent = i //2
    A[i] = last

#@profile
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
A = [0]

#@profile
def main():
    out = ""
    for l in sys.stdin.readlines():
        if l[0] == "i":
            #insert k
            A.append(int(l[7:]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(out, end = "")
            return
        else:
            if len(A) <= 1:
                pass
            elif len(A) == 2:
                out += str(A.pop()) + "\n"
                #print(A.pop())
            #extract(A)
            else:
                out += str(A[1]) + "\n"
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import re

tmp = raw_input()

length = len(tmp)


for i in range(length/2):
    tmp = tmp.replace("01", "")
    tmp = tmp.replace("10", "")


length2 = len(tmp)

division = length - length2

print(division)

### FIXED CODE ###

import re

tmp = raw_input()

length = len(tmp)


tmp1 = tmp.replace("0", "")
tmp2 = tmp.replace("1", "")

if len(tmp1) > len(tmp2):
    tmp3 = len(tmp1) - len(tmp2)

else:
    tmp3 = len(tmp2) - len(tmp1)


division = length - tmp3

print(division)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
heapq.heapify(A)

CB = []
for i in range(M):
  b, c = map(int, input().split())
  CB.append([c, b])

CB.sort()
D = []
for c, b in CB:
  D += [c]*b

for i in range(N):
  if D:
    d = D.pop()
    g = heapq.heappushpop(A, d)
    if d == g:
      break
  else:
    break

print(sum(A))

### FIXED CODE ###

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

CB = []
for i in range(M):
  b, c = map(int, input().split())
  CB.append([c, b])

D = [[a, 1] for a in A] + CB

D.sort()

ans = 0
while N > 0:
  c, b = D.pop()
  ans += min(N, b)*c
  N -= b

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

n = input()
count = 0
for i in xrange(n):
    x = input()
    if x == 2: count += 1
    elif x % 2 != 0:
        for j in xrange(3,x,2):
            if x % j == 0: break
        else: count += 1
print count

### FIXED CODE ###

import math
def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(math.sqrt(x))+1,2):
            if x % j == 0: return False
        else:
            return True 
n = input()
count = 0
for i in xrange(n):
    if prime(input()): count += 1
print count
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for l in range(n):
    ss = s[l:]
    length = n - l
    i, j = 1, 0
    a = [0 for _ in range(length)]
    while i < length:
        while i + j < length and ss[j] == ss[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < length and k + a[k] < j:
            a[i + k] = a[k]
            k += 1
        i += k
        j -= k
    amax = max(a)
    ans = max(ans, min(n // 2, amax))
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for l in range(n):
    ss = s[l:]
    length = n - l
    i, j = 1, 0
    a = [0 for _ in range(length)]
    while i < length:
        while i + j < length and ss[j] == ss[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < length and k + a[k] < j:
            a[i + k] = a[k]
            k += 1
        i += k
        j -= k
    for ll, al in enumerate(a):
        if al <= ll:
            ans = max(ans, al)
print(ans)
### BUGGY CODE ###

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

b = []
for t in a:
    b.append(t)
    b.reverse()

print(" ".join(map(str, b)))


### FIXED CODE ###

from collections import deque

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

b = deque()
for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
if n % 2 == 1:
    b.reverse()

print(" ".join(map(str, b)))
### BUGGY CODE ###

import functools
import operator
M = 10**9 + 7
n, k = map(int, input().split())
if k == 1:
    print(0)
    __import__('sys').exit(0)
a = list(map(int, input().split()))
a.sort(reverse=True)

def mul(a, b):
    return mod(a * b)

def powmod(a, n):
    if n == 0:
        return 1
    if n % 2:
        ans = a * powmod(a, n - 1)
    else:
        ans = powmod(a, n // 2) ** 2
    return mod(ans)

def mod(a):
    if a >= M:
        a %= M
    return a
deno = functools.reduce(mul, range(n, n - (k - 1), -1))
nume = functools.reduce(mul, range(1, k))

# max_sum = 0
# min_sum = 0
result = 0
for i, left in enumerate(range(n, k - 1, -1)):
    # print(deno // left * (left - (k - 1)))
    deno = mod(mod(deno * powmod(left, M - 2)) * (left - (k - 1)))
    # print(deno // nume)
    c = mod(deno * powmod(nume, M - 2))

    result += mod(c * a[i]) - mod(c * a[-(i + 1)])
    # max_sum += c * a[i]
    # min_sum += c * a[-(i + 1)]


# print((max_sum - min_sum) % M)
print(result % M)


### FIXED CODE ###

import functools
import operator
M = 10**9 + 7
n, k = map(int, input().split())
if k == 1:
    print(0)
    __import__('sys').exit(0)
a = list(map(int, input().split()))
a.sort(reverse=True)

def mul(a, b):
    return mod(a * b)

def powmod(a, n):
    if n == 0:
        return 1
    if n % 2:
        ans = a * powmod(a, n - 1)
    else:
        ans = powmod(a, n // 2) ** 2
    return mod(ans)

def mod(a):
    if a >= M:
        a %= M
    return a
deno = functools.reduce(mul, range(n, n - (k - 1), -1))
nume = functools.reduce(mul, range(1, k))

# max_sum = 0
# min_sum = 0
result = 0
for i, left in enumerate(range(n, k - 1, -1)):
    # print(deno // left * (left - (k - 1)))
    deno = mod(mod(deno * powmod(left, M - 2)) * (left - (k - 1)))
    # print(deno // nume)
    c = mod(deno * powmod(nume, M - 2))

    result += mod(c * a[i]) - mod(c * a[-(i + 1)])
    # max_sum += c * a[i]
    # min_sum += c * a[-(i + 1)]


# print((max_sum - min_sum) % M)
print(result % M)
### BUGGY CODE ###

n=int(input())
a=list(input())
mini=float('inf')
for i in range(n):
    x=a[:i].count("W")
    y=a[i+1:].count("E")
    mini=min(mini,x+y)
print(mini)

### FIXED CODE ###

n=int(input())
a=input()
import collections 
e=a.count("E")
w=0
mini=n
for i in range(n):
    if a[i]=="E":
        e-=1
    if i!=0 and a[i-1]=="W":
        w+=1
    mini=min(mini,e+w)
print(mini)