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

N = 1000
L = list(range(2,N+1))
p = list()
while L[0]**2<=N:
    tmp = L[0]
    p.append(tmp)
    L = [e for e in L if e%tmp!=0]
p = p + L

def function(n):
    memo = set()
    r = int((n+1)**0.5)
    for i in p:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            memo.add(i)
    if n > 1:
        memo.add(n)
    return memo

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


total = set()
cnt = 0
seki = set(p)
for a in A:
    s = function(a)
    total = total | s
    seki = seki & s
    cnt += len(s)
# print(total)

if seki == set():  # 全部に共通する素因数はない
    if len(total) != cnt:  # どこかに共通あり
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from math import gcd

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

m = 10**6
D = [-1]* (m+1)
for i in range(2, m+1):
    if D[i] == -1:
      for j in range(i, m+1, i):
          if D[j] == -1:
              D[j] = i


wa_set = set()
cnt = 0
for a in A:
    a_set = set()
    while a > 1:
        a_set.add(D[a])
        a //= D[a]
    wa_set |= a_set
    cnt += len(a_set)

if cnt == len(wa_set):
    print("pairwise coprime")
else:
    t = A[0]
    for a in A:
        t = gcd(a, t)
    if t == 1:
        print("setwise coprime")
    else:
        print("not coprime")
### BUGGY CODE ###

N,K,Q=map(int, input().split())
A=[]
for i in range(0,Q):
    A.append(int(input()))
B=[0]*N
for i in range(N):
    B[i]=A.count(i+1)
for i in range(0,N):
    if K+B[i]-Q>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q=map(int, input().split())
M=K-Q
A=[M]*N
for i in range(Q):
    B=int(input())
    A[B-1]+=1
for i in range(N):
    if A[i]<1:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

MOD = 10**9 + 7
K = int(input())
S = input()

A = list(map(ord,S))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

M = K+len(S)
dp = dpinit((M+1,len(S)+1))

dp[0][0] = 1

for i in range(1,M+1):
    for j in range(len(S)+1):
        dp[i][j] += dp[i-1][j]*25
        dp[i][j] %= MOD
        if j+1 <= len(S):
            dp[i][j+1] += dp[i-1][j]
            dp[i][j+1] %= MOD
    dp[i][len(S)] += dp[i-1][len(S)]
    dp[i][len(S)] %= MOD

print(dp[M][len(S)])




### FIXED CODE ###

MOD = 10**9 + 7
K = int(input())
S = input()


N = len(S)
M = K+N
s = [pow(26,K,MOD)]

r26 = pow(26,MOD-2,MOD)
for i in range(1,K+1):
    t = s[-1]
    t *= r26
    t *= 25
    t *= N+i-1
    t *= pow(i,MOD-2,MOD)
    t %= MOD
    s.append(t)


ans = sum(s) % MOD
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
BCs = [list(map(int, input().split())) for _ in range(M)]

BCs = sorted(BCs,reverse = True, key = lambda x: x[1])
As = sorted(As, key = lambda x:x)

#%%
A_ind = 0

for BC in BCs:
    count = BC[0]
    value = BC[1]
    
    for i in range(count):
        if As[A_ind] < value:
            As[A_ind] = value
            A_ind += 1
            
            if A_ind >= len(As):
                break
    else:
        continue
    break

print(sum(As))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(int, input().split()))
BCs = [list(map(int, input().split())) for _ in range(M)]

BCs = sorted(BCs,reverse = True, key = lambda x: x[1])
As = sorted(As, key = lambda x:x)

#%%
A_ind = 0

for BC in BCs:
    count = BC[0]
    value = BC[1]
    
    for i in range(count):
        if As[A_ind] < value:
            As[A_ind] = value
            A_ind += 1
            if A_ind >= len(As):
                break
        else:
            break
        
    else:
        continue
    break

print(sum(As))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.predecessor(G, 1, cutoff=N)

    print(YES)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            print(val[0])
            # ans_list.append((key,val[0]))

    # ans_list.sort(key=lambda x: x[0])
    # for key, val in ans_list:
    #     print(val)
    return


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    dq = deque([])
    traversed = [False for _ in range(N+1)]
    ans = [None for _ in range(N+1)]

    G = {n : set([]) for n in range(1, N+1)}
    for a, b in zip(A,B):
        G[a].add(b)
        G[b].add(a)

    dq.append(1)
    traversed[1] = True

    while dq:
        s = dq.popleft()

        for node in G[s]:
            if not traversed[node]:
                dq.append(node)
                traversed[node] = True
                

                ans[node] = s

    print(YES)
    for s in ans:
        if s != None:
            print(s)
    return


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

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

import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid, flush=True)
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
            
print(0, flush=True)
start=input()
if start=='Vacant':exit()
bin(start)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
sys.stdout.flush()
start=input()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

import math

K=int(input())
ans=0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans+=math.gcd(math.gcd(i,j),k)
print(ans)

### FIXED CODE ###

import math

K=int(input())
ans=0

for i in range(1,K+1):
  for j in range(1,K+1):
    temp=math.gcd(i,j)
    for k in range(1,K+1):
      ans+=math.gcd(temp,k)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
temp=sum(a)
temp1=a[0]
ans=abs(temp-temp1*2)
for i in range(1,n-1):
  temp1=temp1+a[i]
  ans=min(ans,abs(temp-temp1*2))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline


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



res = 1
for e in a:
    res = res*e

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

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline


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

judge = False

for e in a:
    if e == 0:
        judge = True
if judge:
    print(0)
    exit()

res = 1
for e in a:
    res = res*e
    if res > 10**18:
        res = -1
        break


if res == -1:
    print(-1)
else:
    print(res)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edges=[[] for i in range(n)]
inp=sys.stdin.buffer.readlines()
for i in inp[:n-1]:
    a,s=map(int,i.split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in inp[n-1:]:
    a,s=map(int,_.split())
    add[a-1]+=s


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(' '.join(str(c) for c in cnt))

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
ordList = []
for i in range(1,N+1):
    ordList.append(str(As.index(i)+1))
print(' '.join(ordList))

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
ordList = [None] * N
noCount = 1
for i in As:
    ordList[i-1] = str(noCount)
    noCount += 1
print(' '.join(ordList))
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split(" ")]
res=1
xx=10**18
for i in a:
    res*=i
if res>xx:
    print(-1)
else:
    print(res)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split(" ")]
res=1
xx=10**18
f=0
a.sort()
for i in a:
    res*=i
    if res>xx:
        f=1
        print(-1)
        break

if f==0:
    print(res)
### BUGGY CODE ###

import sys
#入力S
S = input()

#入力T
T = input()
ran_T = range(len(T))
#print(len(T))
#print(range(len(T)))
count = 0

for i in ran_T:
    if list(S)[i] != list(T)[i]:
        count += 1

print(count)


### FIXED CODE ###

#入力S
S = input()

#入力T
T = input()
ran_T = range(len(T))
#print(len(T))
#print(range(len(T)))
count = 0

for a, b in zip(S, T):
    if a != b:
        count += 1

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

S=list(input())

B=[0]*len(S)

for i in range(len(S)):
    if S[i]=='R':
        r=i+1
        while S[r]=='R':
            r+=1
        if (r-i)%2==1:
            B[r-1]+=1
        else:
            B[r]+=1

    if S[i]=='L':
        l=i-1
        while S[l]=='L':
            l-=1
        if (l+i)%2==1:
            B[l+1]+=1
        else:
            B[l]+=1

print(' '.join(map(str,B)))


### FIXED CODE ###

S=list(input())
N=len(S)

B=[0]*len(S)

s=0
for i in range(N):
    if S[i]=='R':
        s+=1
    else:
        if s%2==1:
            B[i]+=int((s-1)/2)
            B[i-1]+=int((s-1)/2+1)
        else:
            B[i]+=int(s/2)
            B[i-1]+=int(s/2)
        s=0

s=0
for i in range(N-1,-1,-1):
    if S[i]=='L':
        s+=1
    else:
        if s%2==1:
            B[i]+=int((s-1)/2)
            B[i+1]+=int((s-1)/2+1)
        else:
            B[i]+=int(s/2)
            B[i+1]+=int(s/2)
        s=0

print(' '.join(map(str,B)))
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

c = []
for i in range(m):
  c.append([u[i]-1,v[i]-1,a[i]])
  c.append([v[i]-1,u[i]-1,a[i]])

from heapq import heappop, heappush
inf=float('inf')
d=[inf for _ in range(n)]
d[s-1]=0
p=dict()
for i,j,k in c: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d[s-1],s-1))
while q:
  du, u1 = heappop(q)
  if d[u1]<du: continue
  for v1,weight in p.get(u1,[]):
    alt=du+weight
    if d[v1]>alt:
      d[v1]=alt
      heappush(q, (alt,v1))

c2 = []
for i in range(m):
  c2.append([u[i]-1,v[i]-1,b[i]])
  c2.append([v[i]-1,u[i]-1,b[i]])

d2=[inf for _ in range(n)]
d2[t-1]=0
p=dict()
for i,j,k in c2: p[i]=p.get(i,[])+[(j,k)]

q=[]
heappush(q,(d2[t-1],t-1))
while q:
  du, u2 = heappop(q)
  if d2[u2]<du: continue
  for v2,weight in p.get(u2,[]):
    alt=du+weight
    if d2[v2]>alt:
      d2[v2]=alt
      heappush(q, (alt,v2))

ans = [d[n-1]+d2[n-1]]
for i in range(1,n):
  ans.append(min(ans[i-1],d[n-1-i]+d2[n-1-i]))

for i in range(n):
  print(10**15-ans[n-1-i])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

for i in ans[::-1]:
  print(10**15-i)
### BUGGY CODE ###

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

parent={i:-1 for i in range(1,N+1)}
depth={i:-1 for i in range(1,N+1)}
parent[1]=(0,-1)
depth[1]=0
q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for b,i in edge[x]:
            if parent[b]==-1:
                parent[b]=(x,i)
                depth[b]=depth[x]+1
                sub.add(b)

        if not q:
            q=sub
            sub=set([])
            break

M=int(input())
condition=[[] for i in range(0,M)]
for i in range(0,M):
    u,v=map(int,input().split())
    ans=set([])
    while depth[u]!=depth[v]:
        if depth[u]>depth[v]:
            U,j=parent[u]
            ans.add(j)
            u=U
        else:
            V,j=parent[v]
            ans.add(j)
            v=V

    while u!=v:
        U,j=parent[u]
        ans.add(j)
        u=U
        V,j=parent[v]
        ans.add(j)
        v=V
    condition[i]=ans

ans=2**(N-1)
ban=0
for i in range(1,2**M):
    num=bin(i).count('1')
    s=set([])
    for j in range(0,M):
        if i>>j &1==1:
            s=s|condition[j]

    n=len(s)
    if num%2==1:
        ban+=2**(N-1-n)
    else:
        ban-=2**(N-1-n)

print(ans-ban)

### FIXED CODE ###

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

parent={i:-1 for i in range(1,N+1)}
depth={i:-1 for i in range(1,N+1)}
parent[1]=(0,-1)
depth[1]=0
q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for b,i in edge[x]:
            if parent[b]==-1:
                parent[b]=(x,i)
                depth[b]=depth[x]+1
                sub.add(b)

        if not q:
            q=sub
            sub=set([])
            break

M=int(input())
condition=[[] for i in range(0,M)]
for i in range(0,M):
    u,v=map(int,input().split())
    ans=set([])
    while depth[u]!=depth[v]:
        if depth[u]>depth[v]:
            U,j=parent[u]
            ans.add(j)
            u=U
        else:
            V,j=parent[v]
            ans.add(j)
            v=V

    while u!=v:
        U,j=parent[u]
        ans.add(j)
        u=U
        V,j=parent[v]
        ans.add(j)
        v=V
    con=0
    for j in ans:
        con+=2**j
    condition[i]=con

ans=2**(N-1)
ban=0
for i in range(1,2**M):
    num=bin(i).count('1')
    s=0
    for j in range(0,M):
        if i>>j &1==1:
            s=s|condition[j]


    n=bin(s).count('1')
    if num%2==1:
        ban+=2**(N-1-n)
    else:
        ban-=2**(N-1-n)

print(ans-ban)
### BUGGY CODE ###

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

ans = 10 ** 10
for i in range(n - 1):
    x = sum(a[:i + 1])
    y = sum(a[i + 1:])
    ans = min(ans, abs(x - y))

print(ans)


### FIXED CODE ###

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

cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + a[i]

ans = 10 ** 10
for i in range(1, n):
    x = cumsum[i]
    y = cumsum[n] - x
    ans = min(ans, abs(x - y))

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

n = int(input())

a=list(map(int,input().split()))
a.sort(reverse = True)
from collections import deque
from collections import Counter as cnt
aaa = dict(cnt(a))

maa = a[0]//2
ma = maa+1


ans = []
a = deque(a)
while True:
    if len(a) <1:
        break
    i = a.pop()
    ans.append(i)

    b = deque()
    while len(a)>0:
        j = a.pop()
        if j%i !=0:
            b.appendleft(j)
    a = b.copy()

    if i >= ma:
        ans += a
        break





mans = 0
for i,v in aaa.items():
    if (i in ans) & (v == 1) :
        mans+=1

print(mans)

### FIXED CODE ###

n = int(input())

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

from collections import Counter as cnt
aaa = dict(cnt(a))

ma = max(a)
dp = [True for i in range(ma+1)]

for i in a:
    if dp[i]:
        mul = i*2
        while mul<=ma:
            dp[mul] =False
            mul += i

mans = 0
for i,v in aaa.items():
    if dp[i] & (v == 1) :
        mans+=1

print(mans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
for _ in range(n):
    ans=a
    x=ans.pop(0)
    print(max(ans))
    ans.append(x)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
ans=max(a)
if a.count(ans)>1:
    for _ in range(n):
        print(ans)
else:
    for i in range(n):
        print(ans if a[i]!=ans else sorted(a)[-2])
### BUGGY CODE ###

n = int( input() )
s = []
for i in range(n):
    s.append(sorted(list(input())))

s.sort()

cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if s[i] == s[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter

n = int( input() )
s = []
for i in range(n):
    s.append("".join(sorted(list(input()))))

cnt = 0
words = Counter(s)
for i in words.values():
    cnt += i*(i-1)//2

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

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

for i in range(1,N):
    for j in range(i, N):
        if H[j-1] >= H[j]:
            num +=1
        else:
            break
    
    if num > ans:
        ans = num
    num = 0

print(ans)

### FIXED CODE ###

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


for j in range(1, N):
    if H[j-1] >= H[j]:
        num +=1
        # print(num)
    else:
        if num > ans:
            ans = num
        num = 0
else:
    if num > ans:
        ans = num



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

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x])%2==0:
    for j, e in enumerate(grapht[x]):
      if j==len(grapht[x])-1:
        graph2[e].add(x)
        num[e] *= -1
      else:
        graph2[x].add(e)
      t.add(e)
  elif num[x]==1 and len(grapht[x])%2==1:
    for j, e in enumerate(grapht[x]):
      if j==len(grapht[x])-1:
        graph2[e].add(x)
        num[e] *= -1
      else:
        graph2[x].add(e)
      t.add(e)
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    grapht[x].remove(e)
    grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

  for i in range(n):
    for e in graph2[i]:
      print(i+1, e+1)

### FIXED CODE ###

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

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

import itertools
N, K = map(int,input().split())
A = [int(i) for i in input().split()]
ans = 0
for i in itertools.combinations(A, K):
  ans += max(i)-min(i)
print(ans%(10**9+7))

### FIXED CODE ###

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10 ** 9 + 7
N = 10 ** 6 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)  

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a = sorted(a)
ans = 0
for i in range(n-k+1):
    ans += (a[-1-i] - a[i]) * cmb(n-1-i, k-1, p)
    ans %= p
print(ans)