Harryxun/stf_run huggingface dataset:
def main():
    n, k = map(int, input().split()) 
    al = list(map(int, input().split())) 
    city_l = [1]
    city_s = set([1])
    loop_city_l = []
    curr_city = 1
    cnt = 0
    for i in range(1,k+1):
        next_c = al[curr_city-1]
        if next_c in city_s:
            cnt = i
            first_city = city_l.index(next_c)
            loop_city_l = city_l[first_city:]
            break
        else:
            city_s.add(next_c)
            city_l.append(next_c)
        curr_city = next_c
    else:
        print(curr_city)

    # print(loop_city_l)
    remained = k-cnt
    last_pos = remained%len(loop_city_l)
    print(loop_city_l[last_pos])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split()) 
    al = list(map(int, input().split())) 
    city_l = [1]
    city_s = set([1])
    loop_city_l = []
    curr_city = 1
    cnt = 0
    for i in range(1,k+1):
        next_c = al[curr_city-1]
        if next_c in city_s:
            cnt = i
            first_city = city_l.index(next_c)
            loop_city_l = city_l[first_city:]
            break
        else:
            city_s.add(next_c)
            city_l.append(next_c)
        curr_city = next_c
    else:
        print(curr_city)
        return

    # print(loop_city_l)
    remained = k-cnt
    last_pos = remained%len(loop_city_l)
    print(loop_city_l[last_pos])

if __name__ == "__main__":
    main()
for i in range(M):
    list[map(int, input().split())]=1

### FIXED CODE ###

N, M, X=map(int, input().split())
sum=sum(int(i)<X for i in input().split())
print(min(sum, M-sum))
a = input()
s = input()
 
if int(a) >= int(3200):
  print(s)
else:
  print(red)

### FIXED CODE ###

a = input()
s = input()
 
if int(a) >= int(3200):
  print(s)
else:
  print('red')
# -*- coding: utf-8 -*-
def check(a, time):
  ret, mod = divmod(time, a)
  if mod > 0:
    return False
  if ret >= a:
    return check(a, ret)
  else:
    return True


a, b, t = map(int, input().split())
biscuit = 0
for i in range(1, ((t + 1) * 2)):
  time = i / 2
  if check(a, time):
    biscuit = biscuit + b
  if time == t + 0.5:
    break

print(biscuit)


### FIXED CODE ###

# -*- coding: utf-8 -*-
def check(a, time):
  ret, mod = divmod(time, a)
  value = True if mod == 0 else check(a, ret) if ret > a else False
  return value


a, b, t, biscuit = map(int, input().split() + ["0"])
for i in range(1, t + 1):
  if check(a, i):
    biscuit = biscuit + b

print(biscuit)
import math
A,B=map(int,input().split())
x=A*B//gcd(A,B)

print(x)


### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
x=(A*B)//(gcd(A,B))

print(x)
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    xy = [list(map(int,input().split())) for i in range(N)]
    print(-1)

    xy = np.array(xy)
    # print(xy)

    diffs = xy - xy.T
    print(-1)
    md = np.sum(np.abs(diffs),axis=-1)
    res = md.max()

    # print(diffs)
    # print(md)

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    xy = [list(map(int,input().split())) for i in range(N)]

    z_max = 0
    z_min = 2 * 10 **9

    w_max = - 10 ** 9
    w_min = 10 ** 9

    for i in range(N):
        z = xy[i][0] + xy[i][1]
        w = xy[i][0] - xy[i][1]
        z_max = max(z_max,z)
        z_min = min(z_min,z)
        w_max = max(w_max,w)
        w_min = min(w_min,w)

    res = max(z_max-z_min,w_max-w_min)

    print(res)



main()
import re
regex=(r'[A|C|G|T]+')
s=input()
mo=re.search(regex,s)
print(len(mo.group()))

### FIXED CODE ###

import re
regex=(r'[A|C|G|T]+')
s=input()
mo=re.findall(regex,s)
print(len(max(mo,key=len)) if mo!=[] else 0)
n = 10
while n != 0:
 n = raw_input()
 print "Case " + str(i) + ": " +str(n)

### FIXED CODE ###

n = 10
i = 1
while n != 0:
 n = input()
 if n == 0:
     break
 print "Case " + str(i) + ": " +str(n)
 i = i + 1
N=int(int(input())/2)
a=sorted(input().split())
print(int(a[N+1])-int(a[N]))

### FIXED CODE ###

N=int(int(input())/2)
a=sorted(list(map(int,input().split())))
print(int(a[N])-int(a[N-1]))
N=int(input())

S=list(map(int,input().split()))

div1=0
div2=0
div4=0
lenS=len(S)

for i in range(N):
    if S[i]%4==0:
        div4+=1
    elif S[i]%2==0:
        div2+=1
    else:
        div1+=1

if lenS%2==0:

    if div4*2+div2>=lenS:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
else:
    
    if (div4*2+1)>=lenS:
        print("Yes")
        exit()
    elif div4*2+div2>=lens:
        print("Yes")
        exit()
    else:
        print("No")




### FIXED CODE ###

N=int(input())

S=list(map(int,input().split()))

div1=0
div2=0
div4=0
lenS=len(S)

for i in range(N):
    if S[i]%4==0:
        div4+=1
    elif S[i]%2==0:
        div2+=1
    else:
        div1+=1

if lenS%2==0:

    if div4*2+div2>=lenS:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
else:
    
    if (div4*2+1)>=lenS:
        print("Yes")
        exit()
    elif div4*2+div2>=lenS:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
from collections import deque

Q = [deque() for _ in range(3)]
for i in range(3):
    for s in list(input()):
        Q[i].append(ord(s) - ord('a'))

k = Q[0].popleft()
while True:
    k = Q[k].popleft()
    if len(Q[k]) == 0:
        break

print('ABC'[k])


### FIXED CODE ###

from collections import deque

Q = [deque() for _ in range(3)]
for i in range(3):
    for s in list(input()):
        Q[i].append(ord(s) - ord('a'))

k = Q[0].popleft()
while len(Q[k]) != 0:
    k = Q[k].popleft()

print('ABC'[k])
a=map(int,input().split())
for i in range(1,6):
    if a[i-1]==0:
        print(i)
        break

### FIXED CODE ###

a=list(map(int,input().split()))
for i in range(1,6):
    if a[i-1]==0:
        print(i)
        break
from collections import deque
n = int(input())
an = list(map(int, input().split()))

an.sort()
an = deque(an)
ls = deque()
same = -1
while an:
    a = an.popleft()
    t = True
    if same == a:
      continue
    for i in ls:
        if i > a ** (1/2):
            t = False
            break
        if a == i:
            ls.pop()
            same = a
            t = False
            break
        if a % i == 0:
            t = False
            break
    if t:
        ls.append(a)

print(len(ls))


### FIXED CODE ###

x = list(map(int, input().split()))

for i in range(5):
    if x[i] == 0:
        print(i + 1)
        exit()
import sys

input = sys.stdin.readline

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


dp = [[float("inf") for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
	dp[i][i] = 0

def rec(i, j):
	if(dp[i][j] != float("inf")) : return dp[i][j];

	turn = N -(j-i)

	if (turn % 2 == 0):
		d = max(rec(i+1, j) + lst_a[i], rec(i, j-1) + lst_a[j-1])
	else :
		d = min(-lst_a[i] + rec(i + 1, j), -lst_a[j - 1] +rec(i, j - 1))

	dp[i][j] = d
	return dp[i][j]

rec(0,N)

print(dp[0][N])

### FIXED CODE ###

import sys

input = sys.stdin.readline

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


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

for len in range(1, N + 1):
	for i in range(N+1-len):
		j = i + len
		if ((N-len) % 2 == 0):
			dp[i][j] = max(dp[i+1][j] + lst_a[i], dp[i][j-1] + lst_a[j-1])
		else :
			dp[i][j] = min(-lst_a[i] + dp[i + 1][j], -lst_a[j - 1]+dp[i][j - 1])


print(dp[0][N])
import warnings
warnings.filterwarnings('ignore')
import numpy as np

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])



### FIXED CODE ###

import numpy as np
import warnings
warnings.filterwarnings('ignore')

Mv = 10 ** 5
Mw = 10 ** 11

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

V = np.max(v)

# dp[i,j]:iまでのアイテムで価値がj以下の時の重さの最小値
dp = np.array([[Mw] * (Mv + 1)] * (N+1))
dp[0][0] = 0
for i in range(1, N+1):
    tmp_arr = np.full(Mv+1, Mw, dtype=int)
    tmp_arr[v[i]:] = dp[i-1][:-v[i]] + w[i]
    dp[i] = np.minimum(dp[i-1], tmp_arr)

print(np.max(np.where(dp[N] <= W, dp[N], 0).nonzero()))
S = input(str())
 if S == Sunny:
     print(Cloudy)
 elif S == Cloudy:
     print(Rainy)
 else :
     print(Sunny)

### FIXED CODE ###

def main():
    S = input()
    if S[0] == 'S':
        print("Cloudy")
    elif S[0] == 'R':
        print("Sunny")
    else:
        print("Rainy")
    pass
 
 
if __name__ == "__main__":
    main()
N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 11)] for _ in range(b_sum + 11)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)
INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            # Black:2
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        for j in range(n):
            src = input()
            dst = src.replace('-1', 'INF')
            ai = list(map(int, dst.split()))
            A.append(ai)
    print(prim(A))

### FIXED CODE ###

INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            # Black:2
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        src = input()
        dst = src.replace('-1', str(INF))
        ai = list(map(int, dst.split()))
        A.append(ai)
    print(prim(A))
def next_contest(x):
  if x is 'ABC':
    return 'ARC'
  elif x is 'ARC':
    return 'ABC'
  else:
    return 'not defined contest'

next_contest(S)

### FIXED CODE ###

S = input()
if S == 'ABC':
  print('ARC')
else:
  print('ABC')
N = int(input())
a = [int(input()) for _ in range(N)]
light = 1
cnt = 0

for i in range(N):
  if i == 0:
    nxt = a[0] - 1
  else:
    nxt = a[nxt]
    
  if nxt == 2:
    break
  else:
    cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
nxt = a[0]-1
cnt = 1
if a[0]-1 == 1:
  print(cnt)
  exit()

for i in range(1, N+1):
  if a[nxt] == 2:
    cnt += 1
    print(cnt)
    exit()
  else:
    nxt = a[nxt] - 1
    cnt += 1
else:    
  print(-1)
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


def distance(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            distance(x, (d + w) % 2)


distance(0, 0)

for v in c:
    print(v)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100100)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

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


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])
s=int(input())
if s[0] == s[1] and s[1] == s[2] and s[0] == s[2]:
  print('No')
else:
  print('Yes')


### FIXED CODE ###

s=str(input())
if s[0] == s[1] and s[1] == s[2] and s[0] == s[2]:
  print('No')
else:
  print('Yes')
import numpy as np
N = int(input())
n2 = N % 2
if n2 != 0:
  ans = 0
else:
  F = list(range(2, N+1, 2))
  a5 = int(np.log(N) // np.log(5))
  B = []
  for i in range(a5):
    a=2 * (5 ** (i+1))
    b = [f for f in F if f % a == 0]
    B.append(len(b))
  ans = np.sum(B)
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
n2 = N % 2
if n2 != 0:
  ans = 0
elif N <= 2:
  ans =0
else:
  a = int(np.log(N) // np.log(5))
  A = [N // (2 * (5 ** (i + 1))) for i in range(a)]
  ans = np.sum(A)
print(ans)
for _ in range(n):
  si = str(input())
  di = {}
  for i in range(10):
    if si[i] in di.keys():
      di[si[i]] += 1
    else:
      di[si[i]] = 1
  frag = True
  for j,st in enumerate(li[0]):
    if di == st:
      li[1][j] += 1
      frag = False
  if frag:
    li[0].append(di)
    li[1].append(1)
sm = 0
for j in li[1]:
  sm += j*(j-1)//2
print(sm)

### FIXED CODE ###

n = int(input())
dic = {}
for _ in range(n):
  si = str(input())
  li = [si[i] for i in range(10)]
  li.sort()
  moji = "".join(li)
  if moji in dic.keys():
    dic[moji] += 1
  else:
    dic[moji] = 1
sm = 0
for j in dic.values():
  sm += j*(j-1)//2
print(sm)
def main():
    n = int(input())
    res = [0]*(n+1)

    for i in range(1,100):
        for j in range(1,100):
            for k in range(1,100):
                if(i**2 + j**2 + k**2 +i*j+j*k + k*i<=n):
                    res[i**2 + j**2 + k**2 +i*j+j*k + k*i]+=1
                    
    for i in range(1,n+1):
        print(res[i])
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    l,r,d=map(int, input().split())
    res = 0
    for i in range(l,r+1):
        if(i%d==0):
            res+=1
    print(res)

if __name__ == '__main__':
    main()
from random import shuffle
import numba
import numpy as np
N = int(input())
#P = list(range(N*N))
#shuffle(P)
P = int(c)-1 for c in input().split()]
#shuffle(P)
#N = int(input())
#P = [int(c)-1 for c in input().split()]
# Mat = [[min(y, N-1-y, x, N-1-x) for y in range(N)] for x in range(N)]
# Mat = np.array(Mat)
@numba.njit()
def proc(N, P):
    ans = 0
    Removed = np.zeros((N, N), dtype=np.int32)
    Mat = np.zeros((N, N), dtype=np.int32)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y][x]
        #print(p, Mat[y][x])
        Removed[y][x] = True
        #Mat[y][x] -= 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy][vx]
            val = Mat[vy][vx]
            for dy, dx in zip(Dy, Dx):
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy][ux]
                if vr:
                    if Mat[uy][ux] >= val+1:
                        Mat[uy][ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy][ux] >= val+2:
                        Mat[uy][ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)



### FIXED CODE ###

import numba
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])

#from random import shuffle
#N = 500
#P = list(range(N*N))
#shuffle(P)
#P = np.array(P)

@numba.njit("void(i8,i8[:])")
def proc(N, P):
    ans = 0
    Removed = np.zeros((500, 500), dtype=np.int8)
    Mat = np.zeros((500, 500), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y,x]
        Removed[y,x] = 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy,vx]
            val = Mat[vy,vx]
            #for dy, dx in zip(Dy, Dx):
            for j in range(4):
                dy = Dy[j]
                dx = Dx[j]
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy,ux]
                if vr:
                    if Mat[uy,ux] >= val+1:
                        Mat[uy,ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy,ux] >= val+2:
                        Mat[uy,ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)
def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    score = []
    checked = [0] * N
    for v in range(N):
        if checked[v]:
            continue
        t = []
        for _ in range(N):
            if checked[v]:
                break
            checked[v] = 1
            t.append(C[v])
            v = P[v]
        score.append(t)

    print(f'{score=}')

    ans = 0
    for loop_lst in score:
        L = len(loop_lst)
        s = sum(loop_lst)
        t = 0
        if s > 0:
            q, K = divmod(K, L)
            t += q * s
        K = min(K, L - 1)
        acc = [0]
        for x in loop_lst:
            acc.append(acc[-1] + x)
        add_v = 0
        for j in range(N)
        for i in range(K):
            add_v = max(acc[i+j] - acc[j])
        ans = max(ans, t + add_v)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説放送

def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    ans = -10**9 - 1

    for si in range(N):
        g = []
        tot = 0
        cur = si
        while True:
            cur = P[cur]
            g.append(C[cur])
            tot += C[cur]
            if cur == si or len(g) == K:
                break

        L = len(g)
        t = 0
        for i, x in enumerate(g, start=1):
            t += x
            now = t
            if tot > 0:
                rep = (K - i) // L
                now += tot * rep

            ans = max(ans, now)

    print(ans)


if __name__ == '__main__':
    main()
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

result = 0
mod = 10**9 +7

def solve(x, y):
    if x == 0:
        return 1
    else:
        r = 1
        for i in range(y-x+1, y+1):
            r = (r*i)%mod
        for i in range(1, x+1):
            r //= i
        return r

s, l = 0, 0
x = solve(k-1, n-1)
for i in range(n-k+1):
    s += a[i]*x
    l += a[n-i-1]*x
    x = (x*(n-k-i))//(n-1-i)
print((l-s)%mod)

### FIXED CODE ###

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

a.sort()

result = 0
mod = 10**9+7

 
def cmb(n, r, mod=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**5+1
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 )


if k==1:
    print(0)
else:
    result = 0
    for i in range(N-k+1):
        result += (a[N-i-1]-a[i])*cmb(N-1-i, k-1)
        result %= mod

    print(result%mod)
import heapq
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

### FIXED CODE ###

import heapq
import sys
sys.setrecursionlimit(10000000)
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))
n=input()
print(1000-int(n[1:4])

### FIXED CODE ###

n=int(input())
print((1000-n%1000)%1000)
while(1):print(oct(n)[2:].translate(str.maketrans('4567', '5789')))

### FIXED CODE ###

while(1):
  n = int(input())
  if n == 0:
    break
  print(oct(n)[2:].translate(str.maketrans('4567', '5789')))
h, n = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a)

for i in a:
  h = h - a
 
if h <= 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

h, n = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
 
for i in a:
  h = h - i
 
if h <= 0:
  print('Yes')
else:
  print('No')
#  ABC 079: B – Lucas Number
n = int(input())

l0 = 2
l1 = 1

if n == 1:
    print(l1)
else:
    for i in range(2, n + 1):
        l = l0 + l1
        l0 = l1
        l1 = l

print(l)

### FIXED CODE ###

# ABC 079: B – Lucas Number
n = int(input())
lucas = [2, 1]

for i in range(2, n + 1):
    lucas.append(lucas[i - 1] + lucas[i - 2])

print(lucas[n])
if A >=13:
  print(B)
elif A >= 6:
  print(B/2)
else:
  print(0)

### FIXED CODE ###

a, b=map(int, input().split())

if a >=13:
  print(b)
elif a >= 6:
  print(b//2)
else:
  print(0)
n, k = map(input().split())
s = (input())

if s[k] is 'A'
	s[k] = 'a'
elif s[k] is 'B'
	s[k] = 'b'
elif s[k] is 'C'
	s[k] = 'c'

print(s)

### FIXED CODE ###

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

s = (input())

if s[k-1] is 'A':
	o = s[:k-1] + 'a' +s[k:] 
elif s[k-1] is 'B':
	o = s[:k-1] + 'b' +s[k:] 
elif s[k-1] is 'C':
	o = s[:k-1] + 'c' +s[k:] 

print(o)