Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))

hats = A[:]
d = {}
for h in hats:
    d[h] = True

h1 = hats[0]

import sys

sys.setrecursionlimit(20000)
 
def search(now1, now2, count):
    now1, now2 = now2, now1^now2
    if now2 in d:
        if now2 == h1:
            if count == N:
                return True
            if count > N:
                return False
            else:
                return search(now1, now2, count+1)
        else:
            return search(now1, now2, count+1)
    else:
        return False
    

ans = False
for h2 in hats[1:]:
    if search(h1, h2, 2):
        ans = True

if ans:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

hats = A[:]
import copy
from collections import defaultdict
d = defaultdict(lambda: 0)

for h in hats:
    d[h] += 1

def f():
    if len(d) == 3:
        xor = 0
        for key in d:
            xor ^= key
        if xor == 0:
            lsit_d = list(d.keys())
            if d[lsit_d [0]] == d[lsit_d [1]] and d[lsit_d [0]] == d[lsit_d [2]]:
                return 'Yes'
            else:
                return 'No'
        else:
            return 'No'

    if len(d) == 1:
        lsit_d = list(d.keys())
        if lsit_d [0] == 0:
            return 'Yes'
        
    if len(d) == 2:
        if d[0] * 2 == N - d[0]:
            return 'Yes'
    
    return 'No'
    
print(f())
#! env/bin/local python3
# -*- coding: utf-8 -*-

import numpy as np

a_1 = list(map(int, input().split()))
a_2 = list(map(int, input().split()))
a_3 = list(map(int, input().split()))
_ = input()
pickup_number = []
while True:
    try:
        pickup_number.append(int(input()))
    except EOFError:
        break

a = np.array([a_1, a_2, a_3])

for pn in pickup_number:
    a[a == pn] = -1

flag = False
if np.sum(a, axis=0)[0] == -3 or np.sum(a, axis=1)[0] == -3:
    flag = True
if np.sum(a.diagonal()) == -3 or a[0][2] + a[1][1] + a[2][0] == -3:
    flag = True

print('Yes' if flag else 'No')


### FIXED CODE ###

#! env/bin/local python3
# -*- coding: utf-8 -*-

n = int(input())

print(n // 2 + n % 2)
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod
a_zero = 0
b_zero = 0
AB = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod)
        ans %= mod
        n -= 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        b_zero += 1
    else:
        AB.append([a, b])
x = [a / b for a, b in AB]
y = [- b / a for a, b in AB]
j = 0
if a_zero:
    while j + 1 < b_zero:
        ans -= comb(b_zero, j + 2) * pow(2, n - (b_zero - (j+2)) - (j+2), mod)
        ans %= mod
        j += 1

lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1
for i in lst:
    j = 0
    while j + 1 < i:
        ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
        ans %= mod
        j += 1
    n -= i
print(ans)




### FIXED CODE ###

#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]

fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = defaultdict(lambda : 0)
y = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x[0] += 1
        z[0] = 1
    elif b == 0:
        y[0] += 1
        z[0] = 1
    else:
        if a * b > 0:
            g = math.gcd(a, b)
            a //= g
            b //= g
            x[(abs(a), abs(b))] += 1
            z[(abs(a), abs(b))] = 1
        else:
            g = math.gcd(a, b)
            a //= g
            b //= g
            y[(abs(b), abs(a))] += 1
            z[(abs(b), abs(a))] = 1

ans = 1
for i in z.keys():
    ans *= (2**x[i] + 2**y[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
ans %= mod
print(ans)
s = int(input())
x = 0

for i in s:
  x += int(i)

if s%x == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = int(input())
x = 0
 
for i in str(s):
  x += int(i)
 
if s%x == 0:
  print("Yes")
else:
  print("No")
a,b=map(int,input().split())
n=sorted([input() for i in range(b)])
print(*s,sep='')


### FIXED CODE ###

a,b=map(int,input().split())
n=sorted([input() for i in range(a)])
print(*n,sep='')
from numba import njit
import numpy as np
N, X, Y = map(int, input().split())
@njit
def f(N,X,Y):
    k_list = np.zeros(shape=N-1,dtype=np.int8)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            min_dst = min((j-i, abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X)))
            k_list[min_dst-1] += 1
    return k_list
ans=f(N,X,Y)
for i in ans:
    print(i)

### FIXED CODE ###

N, X, Y = map(int, input().split())
k_list = [0]*(N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        min_dst = min((j-i, abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X)))
        k_list[min_dst-1] += 1
for i in k_list:
    print(i)
#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB[0]=wayB[0]+wayA[0]
		wayB[1]=wayB[1]+wayA[1]
	if c=='C':
		wayC=wayC+wayB
		wayC[0]=wayC[0]+wayB[0]
		wayC[1]=wayC[1]+wayB[1]
		wayC[2]=wayC[2]+wayB[2]
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	wayC[i]=wayC[i]%MOD
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
ans = ans%1000000007
print(int(ans))

### FIXED CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))
# -*- coding: utf-8 -*-

n = int(input())
a = int(input())
b = int(input())
if n == 1:
    print("Hello World")
else:
    print(a+b)

### FIXED CODE ###

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

n = int(input())
if n == 1:
    print("Hello World")
else:
    a = int(input())
    b = int(input())
    print(a+b)
import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
sys.setrecursionlimit(10**7)

n, m, l = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

res = floyd_warshall(csgraph_from_dense(graph))
res = np.where(res <= l, 1, 0)

new_res = floyd_warshall(csgraph_from_dense(res))
q = int(input())
for i in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s][t] if not np.isinf(new_res[s][t]) else 0
    print(int(dis) - 1)

### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, csgraph_to_dense
from scipy.sparse import issparse
sys.setrecursionlimit(10**7)

n, m, l = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

res = floyd_warshall(csgraph_from_dense(graph))
if issparse(res):
    res = csgraph_to_dense(res)
res = np.where(res <= l, 1, 0)
new_res = floyd_warshall(res)
new_res[new_res == np.inf] = 0
q = int(input())
for j in range(q):
    s, t = [int(i) for i in sys.stdin.readline().split()]
    s -= 1
    t -= 1
    dis = new_res[s, t]
    print(int(dis) - 1)
N,Z,W=map(int,input().split())
A=[int(x) for x in input().split()]
if N==1:
  answer=abs(A[1]-W)
else:
  answer=max(abs(W-A[-1]),abs(A[-1]-A[-2]))
print(answer)

### FIXED CODE ###

N,Z,W=map(int,input().split())
A=[int(x) for x in input().split()]
if N==1:
  answer=abs(A[0]-W)
else:
  answer=max(abs(W-A[-1]),abs(A[-1]-A[-2]))
print(answer)
while True:
????????data = input()
????????if '?' in data:
????????????????break
????????print(eval(data.replace('/','//')))

### FIXED CODE ###

while True:
    data = input()
    if '?' in data:
        break
    print(eval(data.replace('/','//')))
def how_many_times(n):
  ans=0
  while n%2==0:
    n=n/2
    ans=ans+1
    return ans

n=int(input())
a=map(int,input().split())
print(min(map(how_many_times,a)))


### FIXED CODE ###

def how_many_times(n):
  ans=0
  while n%2==0:
    n=n/2
    ans=ans+1
  return ans

n=int(input())
a=map(int,input().split())
print(min(map(how_many_times,a)))
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += (cmb(i+n-1, n-1, mod) * pow(25, i, mod)%mod * pow(26, (K-i), mod)) % mod
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)
a = list(input())
a.sort()

if n[0] == n[1] and a[2]==a[3] and a[0]!=a[2]:
    print("Yes")

else:
    print("No")



### FIXED CODE ###

a = list(input())
a.sort()

if a[0] == a[1] and a[2]==a[3] and a[0]!=a[2]:
    print("Yes")

else:
    print("No")
N = int(input())
root = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int,input().split())
    root[u-1].append([v-1,w%2])
    root[v-1].append([u-1,w%2])

ans = [-1 for i in range(N)]

def dfs(index):
    ans[index] = 0
    for i in root[index]:
        if ans[i[0]] == -1:
            ans[i[0]] = (ans[index]+i[1])%2
            dfs(i[0])

for i in range(N):
    dfs(i)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

N = int(input())
root = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int,input().split())
    root[u-1].append([v-1,w%2])
    root[v-1].append([u-1,w%2])

ans = [-1 for i in range(N)]

def dfs(index):
    if ans[index]==-1:
        ans[index] = 0
    for i in root[index]:
        if ans[i[0]] == -1:
            ans[i[0]] = (ans[index]+i[1])%2
            dfs(i[0])

for i in range(N):
    dfs(i)

for i in ans:
    print(i)
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*7**6
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 1

c = deque([])
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      c.appendleft((a,n-i))
    else:
      c[ind-1] = (a,n-i)
      
print(ans)
arr = [0 for _ in range(1001)]
arr[1] = 1
for i in range(2,32):
    if arr[i]==1:
        continue
    tmp=i
    while i <=1000:
        arr[tmp]=1
        tmp*=i

for x in range(int(input()),0,-1):
    if arr[x]==1:
        print(x)
        break

### FIXED CODE ###

arr = [0 for _ in range(1001)]
arr[1] = 1
for i in range(2,32):
    if arr[i]==1:
        continue
    tmp=i*i
    while tmp <=1000:
        arr[tmp]=1
        tmp*=i

for x in range(int(input()),0,-1):
    if arr[x]==1:
        print(x)
        break
A=list(map(int,input().split()))
K=int(input())
A.sort(reverse=True)
ans=sum(A)
for i in range(K):
  ans+=A[i]
print(ans)

### FIXED CODE ###

A=list(map(int,input().split()))
K=int(input())
A.sort(reverse=True)
ans=sum(A)
for i in range(K):
  ans+=A[0]
  A[0]*=2
print(ans)
n,q=map(int,input().split())
ans=[0]*(n+1)
score=[0]*(n+1)
g=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
for j in range(q):
    p,x=map(int,input().split())
    score[p]+=x
visited=set()
visited.add(1)
def dfs(v):
    global ans
    global score
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if not g[v][i] in visited:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
ans_chr=""
for i in range(1,n+1):
    ans_chr=ans_chr+str(ans[i])+" "
print(ans_chr)


### FIXED CODE ###

import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ in range(n+1)] #グラフ
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=[0]*(n+1)
def dfs(v):
    visited[v]+=1
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if visited[g[v][i]]==0:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
print(" ".join(map(str, ans[1:])))
import numpy as np
n, max_w = map(int, input().split())

dp = [0]*(max_w+1)
dp = np.array(dp)

for _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])

print(max(dp))

### FIXED CODE ###

import numpy as np
n, W = map(int, input().split())

dp = [10**10]*(10**5)
dp = np.array(dp)

for _ in range(n):
    w, v = map(int, input().split())
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])
    np.minimum(w, dp[:v], out=dp[:v])
    
#print(dp[:101])
#print(dp[91])
value = 10**5
for i in dp[::-1]:
    if i <= W:
        print(value)
        exit()
    value -= 1
a,b = map(int,input().split())
lis = list(map(int,input().split))
c = sum(lis)
print("Yes" if a > c else "No")

### FIXED CODE ###

a,b = map(int,input().split())
lis = list(map(int,input().split()))
c = sum(lis)
print("No" if a > c else "Yes")
a=int(input())
b=int(input())
c=int(input())
print(min(b/a,c))

### FIXED CODE ###

a,b,c=map(int,input().split())
print(min(b//a,c))
N = int(input())
p = 0
minnum = 200001
counter = 0

for i in range(N):
  p = int(input())
  if p < minnum:
    counter += 1
    minnum = p

print(counter)
  

### FIXED CODE ###

N = int(input())
lst_p = list(map(int,input().split()))

counter = 0
min_num = 1000000

for i in range(N):
    if lst_p[i] <= min_num:
        counter += 1
        min_num = lst_p[i]
    else:
        continue
print(counter)
import sys


def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    skip = None
    if N % 2 == 0 and N % 4 != 0:
        center = (N // 2) // 2 + 1
        if M >= center:
            skip = center
    right = N + 1
    left = 0
    count = 0
    while count < M:
        left += 1
        right -= 1
        if skip == left:
            continue
        print(left, right)
        count += 1


if __name__ == '__main__':
    main()
import sys


def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    skip = None
    if N % 2 == 0 and N % 4 != 0:
        center = (N // 2) // 2 + 1
        if M >= center:
            skip = center
    right = N + 1
    left = 0
    count = 0
    while count < M:
        left += 1
        right -= 1
        if skip == left:
            continue
        print(left, right)
        count += 1


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    skip = (N // 2) // 2 + 1 if N % 2 == 0 else None
    count = 0
    left, right = 0, N + 1
    while count < M:
        left += 1
        if left == skip:
            continue
        right -= 1
        print(left, right)
        count += 1


if __name__ == '__main__':
    main()
N=int(input())

import itertools
r=0
lista=[input() for a in range(N)]

for lista in itertools.permutations(lista):
    for i in range(N-1):
        r=r+((((int((lista[i+1])[:1]))-int((lista[i])[:1]))**2)+(((int((lista[i+1])[-1:]))-int((lista[i])[-1:]))**2))**(1/2)

import math
print(r/math.factorial(N))


### FIXED CODE ###

N=int(input())

import itertools
li_c=list(itertools.permutations(range(N),2))

rocation=[]
for i in range(N):
    x=list(map(int,input().split()))
    rocation.append(x)

import math
distance=[]
for j in range(len(li_c)):
    distance.append(math.sqrt((rocation[li_c[j][0]][0]-rocation[li_c[j][1]][0])**2+(rocation[li_c[j][0]][1]-rocation[li_c[j][1]][1])**2))

print(sum(distance)/N)
import numpy as np
N = int(input())
X = []
Y = []
for _ in range(N):
    x,y = map(int, input().split())
    X.append(x)
    Y.append(y)
X = np.array(X)
Y = np.array(Y)
X_ = X.reshape((N,1))
Y_ = Y.reshape((N,1))
Z = np.abs(X-X_)+np.abs(Y-Y_)
z = Z.reshape((1,-1))
print(np.max(z))

### FIXED CODE ###

# ABC178D Manhattan
n = int(input())
z = []
w = []
for i in range(n):
    x,y = map(int, input().split())
    z.append(x-y)
    w.append(x+y)
    
z_ans = max(z)-min(z)
w_ans = max(w)-min(w)
print(max(z_ans,w_ans))
def ngcd(lista):
    from math import gcd
    res = lista[0]
    for i in range(1,len(lista)):
        if res != 1:
            res = gcd(lista[i],res)
    return res

def main():
    n = int(input())
    a = list(map(int,input().split()))
    print(ngcd(a))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import functools, fractions
n=input()
a=list(map(int,input().split()))
print(functools.reduce(fractions.gcd,a))
MOD = 10**9 + 7

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
A_r = list(reversed(A))
factorial = {0: 1, 1: 1}
for i in range(2, N + 1):
    factorial[i] = factorial[i - 1] * i

ans = 0
for i, j in zip(A, A_r):
    if N < K:
        break
    C = (factorial[N - 1] / factorial[K - 1]) / factorial[N - K]
    ans += (j - i) * C
    ans %= MOD
    N -= 1
ans = int(ans % MOD)
print(ans)


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
MOD = 10 ** 9 + 7


def combination(mod=MOD):
    fact = [1] * (N + 1)
    inv_fact = [1] * (N + 1)
    r = 1
    for i in range(1, N + 1):
        fact[i] = r = r * i % mod
    inv_fact[N] = r = pow(fact[N], mod - 2, mod)
    for i in range(N, 0, -1):
        inv_fact[i - 1] = r = r * i % mod

    def _wrapper(n, k):
        nonlocal fact, inv_fact, mod
        if n == 0 or k == 0:
            return 1
        return fact[n] * inv_fact[k] * inv_fact[n - k] % mod

    return _wrapper


def main():
    if K == 1:
        print(0)
        exit()
    comb = combination()
    sum_max = 0
    sum_min = 0
    for i, A_i in enumerate(A):
        if i >= K - 1:
            sum_max += comb(i, K - 1) * A_i % MOD
        if N - i >= K:
            sum_min += comb(N - i - 1, K - 1) * A_i % MOD
    ans = (sum_max - sum_min) % MOD
    print(ans)


if __name__ == '__main__':
    main()
l=int(input())-1
s=bin(l)[2:]
if s.count("0")==0:
    n=len(s)+1
    print(str(n-1)+" "+str(2*(n-1)))
    for i in range(n-1):
        print(str(i+1)+" "+str(i+2)+" 0")
        print(str(i+1)+" "+str(i+2)+" "+str(2**i))
else:
    n=len(s)
    res=""
    for i in range(n-1):
        res+=str(i+1)+" "+str(i+2)+" 0\n"
        res+=str(i+1)+" "+str(i+2)+" "+str(2**i)+"\n"
    while s.count("1")>1:
        if s[-1]=="1":
            for i in range(1,n+1):
                if s[-i]=="0":
                    break
            ss=s[:-i]+"0"*i
            nnn=int(ss,2)
            res+=str(i)+" "+str(n)+" "+str(nnn)+"\n"
            s=bin(nnn-1)[2:]
            if len(s)<n:
                break
        else:
            res+="1 "+str(n)+" "+str(l)+"\n"
            s=bin(l-1)[2:]
r=res.count("\n")
res=res[:-1]
print(str(n)+" "+str(r))
print(res)


### FIXED CODE ###

l=int(input())-1
s=bin(l)[2:]
if s.count("0")==0:
    n=len(s)+1
    print(str(n)+" "+str(2*(n-1)))
    for i in range(n-1):
        print(str(i+1)+" "+str(i+2)+" 0")
        print(str(i+1)+" "+str(i+2)+" "+str(2**i))
else:
    n=len(s)
    res=""
    for i in range(n-1):
        res+=str(i+1)+" "+str(i+2)+" 0\n"
        res+=str(i+1)+" "+str(i+2)+" "+str(2**i)+"\n"
    while True:
        if s[-1]=="1":
            for i in range(1,n+1):
                if s[-i]=="0":
                    break
            ss=s[:-i]+"0"*i
            nnn=int(ss,2)
            res+=str(i)+" "+str(n)+" "+str(nnn)+"\n"
            s=bin(nnn-1)[2:]
            if len(s)<n:
                break
        else:
            res+="1 "+str(n)+" "+str(l)+"\n"
            if s.count("1")>1:
                s=bin(l-1)[2:]
            else:
                break
    r=res.count("\n")
    res=res[:-1]
    print(str(n)+" "+str(r))
    print(res)
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N)[::-1]:
    for j in range(N)[::-1]:
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

print(max(max(min(dp[a][b], a-b) for a in range(b, N)) for b in range(N)))

### FIXED CODE ###

S = input()
if S == 'Sunny':
    print('Cloudy')
elif S== 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
import sys
e=iter(sys.stdin)
for a,b in zip(e,e):
 a,b=a.split(),b.split()
 for s,t in zip(a,b):h+=s==t
 print(h,4-len(set(a)-set(b))-h)


### FIXED CODE ###

import sys
e=iter(map(lambda a:a.split(),sys.stdin))
for a,b in zip(e,e):
 h=0
 for s,t in zip(a,b):h+=s==t
 print(h,4-len(set(a)-set(b))-h)
n=int(input())
print(0--n//500)

### FIXED CODE ###

print('YNeos'[eval(input().replace(' ','*500<'))::2])
from collections import Counter
import numpy as np

a = int(input())
a_list = []
b_list = []

for i in range(a):
  a_list.append(input())
a_list.append('null')

b = int(input())

for i in range(b):
  b_list.append(input())
a_count = Counter(a_list)
b_count = Counter(b_list)
a_list_no_overlap = set(a_list)
print(a_count)

point = []
for i in a_list_no_overlap:
    point.append(a_count[i]-b_count[i])

point_max = np.argmax(point)
print(point_max)


### FIXED CODE ###

a, b, c= map(int, input().split())
if a+b<c:
  print("No")
else :
  print("Yes")