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

import sys
input = sys.stdin.readline

n = int(input())
s = list(input())
q = int(input())

ans = []
for i in range(q):
    query = input().split()
    if query[0] == "1":
        s[int(query[1])-1] = query[2]
    else:
        ans.append(len(set(s[int(query[1])-1:int(query[2])])))

for i in ans:
    print(i)

### FIXED CODE ###

import bisect

n = int(input())
s = list(input())
q = int(input())

alphabet = [chr(ord('a') + i) for i in range(26)]

d = {alphabet[i]: [] for i in range(26)}
for i, a in enumerate(s):
    d[a].append(i)

ans = []
for i in range(q):
    query = input().split()

    if query[0] == '1':
        idx, c = int(query[1]) - 1, query[2]
        if s[idx] == c:
            continue
        d[s[idx]].remove(idx)
        bisect.insort_left(d[c], idx)
        s[idx] = c
    else:
        l, r = int(query[1]) - 1, int(query[2]) - 1
        res = 0
        for c in alphabet:
            if bisect.bisect_right(d[c], r) > bisect.bisect_left(d[c], l):
                res += 1
        ans.append(res)

for i in ans:
    print(i)
### BUGGY CODE ###

import numpy as np
N= int(input())
a = list(map(int, input().split(' ')))
#N = 5
#a = [3, 2, 2, 4, 1]


a = np.array(a, dtype=int)
for i in range(N):
    ind = np.ones(N, dtype=bool)
    ind[i] = False
    tmp = a[ind]
    print(int(np.median(tmp)))

### FIXED CODE ###

import numpy as np
N= int(input())
a = list(map(int, input().split(' ')))
sort_a = sorted(a)
small = sort_a[N//2-1]
big = sort_a[N//2]
for aa in a:
    if aa < big:
        print(big)
    else:
        print(small)
### BUGGY CODE ###

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

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(i*10+a)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])

### FIXED CODE ###

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

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

# Next Prime
import numpy as np

# input
X = int(input())

# solve
primes = np.array([1])
numbers = np.array(list(range(2, 10**5 + 1)))
while len(numbers) > 0 and max(primes) < X:
    primes = np.append(primes, numbers[0])
    numbers = numbers[numbers % numbers[0] != 0]

res = int(max(primes))

# output
print(res)

### FIXED CODE ###

# Next Prime
import numpy as np

# input
X = int(input())

# solve
prime = 0
numbers = np.array(list(range(2, 10**5 + 4)))

while prime < X:
    prime = numbers[0]
    numbers = numbers[numbers % prime != 0]

# output
print(prime)
### BUGGY CODE ###

n, p = map(int, input().split())
if n==1:
  print(p)
  exit()
for i in range(int(p**(1/n))+1, 0, -1):
  if p%(i**n)==0:
    print(i)
    exit()

### FIXED CODE ###

n, p = map(int, input().split())
if n==1:
  print(p)
  exit()
elif p==1 or n>=60:
  print(1)
  exit()
for i in range(int(p**(1/n))+1, 0, -1):
  if p%(i**n)==0:
    print(i)
    exit()
### BUGGY CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    h = []
    for _ in range(N):
        h.append(int(input()))
    ans = 10 ** 18
    h.sort()

    for i in range(N - K + 1):
        res = h[i:K + i]
        ans = min(ans, res[-1] - res[0])
    print(ans)
    return


resolve()

### FIXED CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    h = [int(input()) for _ in range(N)]
    ans = 10 ** 10
    h.sort()

    for i in range(N - K + 1):
        res = h[i+K-1] - h[i]
        ans = min(ans, res)
    print(ans)
    return


resolve()
### BUGGY CODE ###

import math
H, N = list(map(int, input().split()))
 
AB = [list(map(int, input().split())) for _ in range(N)]
 
dp = [float('inf')] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
        dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0
print(dp[0])

### FIXED CODE ###

import math
H, N = list(map(int, input().split()))
 
AB = [list(map(int, input().split())) for _ in range(N)]
 
dp = [float('inf')] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
    dp[0] = min(dp[0], min(dp[:a+1]) + b) # if hp is not just 0
print(dp[0])
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
A = []
B = []
C = []
for _ in range(N):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)

INF = 4001
Na = sum(A)
Nb = sum(B)
dp = [[[INF]*(Nb+1) for _ in range(Na+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(Na+1):
        for k in range(Nb+1):
            if j < A[i] or k < B[i]:
                dp[i+1][j][k] = dp[i][j][k]
            else:
                dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-A[i]][k-B[i]]+C[i])
            
ans = INF
for i in range(1, N+1):
    for j in range(1, Na+1):
        for k in range(1, Nb+1):
            if j*Mb == k*Ma:
                ans = min(ans, dp[i][j][k])
                
if ans == INF:
    ans = -1
    
print(ans)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
A = []
B = []
C = []
for _ in range(N):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)

INF = 4001
Na = sum(A)
Nb = sum(B)
dp = [[[INF]*(Nb+1) for _ in range(Na+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(Na+1):
        for k in range(Nb+1):
            if j < A[i] or k < B[i]:
                dp[i+1][j][k] = dp[i][j][k]
            else:
                dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-A[i]][k-B[i]]+C[i])
            
ans = INF
for i in range(1, N+1):
    for j in range(1, Na+1):
        for k in range(1, Nb+1):
            if j*Mb == k*Ma:
                ans = min(ans, dp[i][j][k])
                
if ans == INF:
    ans = -1
    
print(ans)
### BUGGY CODE ###

from itertools import product

x, y, z, k = map(int, input().split())

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

s = sum

delecious = []
for prod in product(a, b, c):
    delecious.append(s(prod))

delecious.sort(reverse=True)

for i in range(k):
    print(delecious[i])

### FIXED CODE ###

import collections
import heapq
 
x, y, z, k = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(3)]
for i in range(3):
    ls[i].sort(reverse=True)
q = [(-sum([ls[i][0] for i in range(3)]), 0, 0, 0)]
res = []
used = collections.defaultdict(lambda: False)
while len(res) < k:
    s, i, j, l = heapq.heappop(q)
    res.append(-s)
    if i + 1 < x and not used[(i + 1, j, l)]:
        heapq.heappush(q, (-(ls[0][i + 1] + ls[1][j] + ls[2][l]), i + 1, j, l))
        used[(i + 1, j, l)] = True
    if j + 1 < y and not used[(i, j + 1, l)]:
        heapq.heappush(q, (-(ls[0][i] + ls[1][j + 1] + ls[2][l]), i, j + 1, l))
        used[(i, j + 1, l)] = True
    if l + 1 < z and not used[(i, j, l + 1)]:
        heapq.heappush(q, (-(ls[0][i] + ls[1][j] + ls[2][l + 1]), i, j, l + 1))
        used[(i, j, l + 1)] = True
print(*res, sep='\n')
### BUGGY CODE ###


from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in range(n):
    res += gcd//a[i]
    res%=mod
print(res)



### FIXED CODE ###


from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in a:
    res += gcd//i
    #res%=mod
print(res%mod)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
count = 0
for i in range(N-1):
    if A[i] <= A[i+1] : count += 1
if count > N * 0.8 : print(1)
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import numpy as np
import sys
from collections import defaultdict


def first_prime_list(N):
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(1, N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i

    return D


def factorization_with_fpl(A, D):

    Ps = defaultdict(int)
    current_p = D[A]

    while D[A] > 1:
        cnt = 0
        while D[A] == current_p:
            A = A // D[A]
            cnt += 1

        Ps[current_p] = cnt
        current_p = D[A]

    if A != 1:
        Ps[A] = 1

    return Ps


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]

D = first_prime_list(max(A))

pc = True
sp = True

maxlist = factorization_with_fpl(A[0], D)
minlist = factorization_with_fpl(A[0], D)

arrA = np.array(A)

for i in range(1, N):
    d = factorization_with_fpl(A[i], D)
    for p in d.keys():
        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])

    for p in minlist.keys():
        minlist[p] = min(minlist[p], d[p])
    

for p in minlist.keys():
    if minlist[p] != 0:
        sp = False


if pc:
    print("pairwise coprime")
elif sp:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import sys
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)

    # 1 <= a <= maxA までの、要素の登場回数
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    # p の倍数である個数をカウントする
    for p in range(2, maxA + 1):
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        # k*p となるような要素が2個以上あったら、pairwise coprime ではない
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

    GCD = A[0]
    for i in range(1, N):
        GCD = math.gcd(GCD, A[i])

    if GCD == 1:
        print("setwise coprime")
        return

    print("not coprime")


main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()

def main():
    md=10**9+7
    dp=[[0]*(n+1) for _ in range(n+1)]
    dp[1][0]=1
    dpx=dp[1]
    for x in range(2,n+1):
        dpx1=dpx
        dpx=dp[x]
        for i in range(x):
            if s[n-x]=="<":
                dpx[i]=sum(dpx1[i:x-1])%md
            else:
                dpx[i]=sum(dpx1[:i])%md
    #p2D(dp)
    print(sum(dp[n])%md)

main()


### FIXED CODE ###

md = 10 ** 9 + 7
n = int(input())
s = input()
dp = [1] * n
for i in range(n - 1):
    if s[i] == "<":
        for dpi in range(1, n - i - 1):
            dp[dpi] = (dp[dpi] + dp[dpi - 1]) % md
        dp = dp[:-1]
    else:
        for dpi in range(n - i - 2, 0, -1):
            dp[dpi] = (dp[dpi] + dp[dpi + 1]) % md
        dp = dp[1:]
print(dp[0])
### BUGGY CODE ###

S = input()
S_list = list(S)

while len(S_list) >= 5 :
    a = len(S_list)
    if S_list[0:5] == ['e', 'r', 'a', 's', 'e']:
        if a >= 6 :
            if S_list[5] == 'r' :
                del S_list[0:6]
        else:
            del S_list[0:5]
    elif S_list[0:5] == ['d', 'r', 'e', 'a', 'm']:
        if a >= 8 :
            if S_list[5:8] == ['e', 'r', 'a'] :
                del S_list[0:5]
        elif a >= 7 :
            if S_list[5:7] == ['e', 'r'] :
                del S_list[0:7]
        else :
            del S_list[0:5]
    else:
        print('NO')
        break


if len(S_list) == 0:
    print('YES')
elif 0<len(S_list)<5:
    print('NO')

### FIXED CODE ###

S = input()
S_list = list(S)

while len(S_list) >= 5 :
    a = len(S_list)
    if S_list[0:5] == ['e', 'r', 'a', 's', 'e']:
        if a >= 6 :
            if S_list[5] == 'r' :
                del S_list[0:6]
            else:
                del S_list[0:5]
        else:
            del S_list[0:5]
    elif S_list[0:5] == ['d', 'r', 'e', 'a', 'm']:
        if a >= 8 :
            if S_list[5:8] == ['e', 'r', 'a'] :
                del S_list[0:5]
            elif S_list[5:7] == ['e', 'r'] :
                del S_list[0:7]
            else :
                del S_list[0:5]
        elif a >= 7 :
            if S_list[5:7] == ['e', 'r'] :
                del S_list[0:7]
            else:
                del S_list[0:5]
        else :
            del S_list[0:5]
    else:
        print('NO')
        break


if len(S_list) == 0:
    print('YES')
elif 0<len(S_list)<5:
    print('NO')
### BUGGY CODE ###

n,m = map(int,input().split())
lst = [1]*n
red_lst = [0]

for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    if (x in red_lst) and (y not in red_lst):
        red_lst.append(y)
    if lst[x]==1 and x in red_lst:
        red_lst.remove(x)
    lst[x] -= 1
    lst[y] += 1

cnt = 0
for i in range(n):
    if lst[i] != 0 and i in red_lst:
        cnt += 1
print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
lst = [1]*n
red_lst = [False]*n
red_lst[0] = True

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

for i in range(m):
    x,y = xx[i], yy[i]
    if red_lst[x]==True and red_lst[y]==False:
        red_lst[y]=True
    if lst[x]==1 and red_lst[x]:
        red_lst[x] = False
    lst[x] -= 1
    lst[y] += 1

print(red_lst.count(True))
### BUGGY CODE ###

from collections import deque

n = int(input())
output = deque()
for i in range(n):
    li = input().split(' ')
    if(li[0] == 'insert'):
        output.appendleft(int(li[1]))
    elif(li[0] == 'delete'):
        if(int(li[1]) in output):
            output.remove(int(li[1]))
    elif(li[0] == 'deleteFirst'):
        output.popleft()
    elif(li[0] == 'deleteLast'):
        output.pop()
str_l = [str(o) for o in output]
print(' '.join(str_l))



### FIXED CODE ###

from collections import deque
n = int(input())
output = deque()
for i in range(n):
    li = input().split(' ')
    if(li[0] == 'insert'):
        output.appendleft(li[1])
    elif(li[0] == 'deleteFirst'):
        output.popleft()
    elif(li[0] == 'deleteLast'):
        output.pop()
    elif(li[0] == 'delete'):
        try:
            output.remove(li[1])
        except:
            pass
print(' '.join(output))
### BUGGY CODE ###

N, W = [int(item) for item in input().split()]
item = [[int(item) for item in input().split()] for _ in range(N)]

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

for i in range(N):
    for w in range(W+1):
        if 0 <= w - item[i][0]:
            dp[i+1][w] = max(dp[i][w], dp[i][w - item[i][0]] + item[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

### FIXED CODE ###

N, W = [int(item) for item in input().split()]
item = [[int(item) for item in input().split()] for _ in range(N)]

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

for i in range(N):
    for w in range(W+1):
        if 0 <= w - item[i][0]:
            dp[i+1][w] = max(dp[i][w], dp[i][w - item[i][0]] + item[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

X = int(input())

for a in range(0 , 10**2 , 1):
  for b in range(0 , X+1 , 1):
    if(a**5-b**5==X):
      print(a, b)
      exit()
    else:
      continue
      
for a in range(0 , 10**2 , 1):
  for b in range(0 , -X , -1):
    if(a**5-b**5==X):
      print(a, b)
      exit()
    else:
      continue

### FIXED CODE ###

X = int(input())
 
for a in range(-119 , 120 , 1):
  A = a**5
  for b in range(-119 , 120 , 1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


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

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


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

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])
### BUGGY CODE ###

from collections import Counter
from itertools import combinations
N = int(input())
S = input()
MOD = 10**9 + 7

C = Counter(S)
ans = 0
for i in range(1, min(N+1, 27)):
    for prod in combinations(C.values(), i):
        a = 1
        for p in prod:
            a *= p
            a %= MOD
        ans += a
        ans %= MOD

print(ans)     


### FIXED CODE ###

# input
n = int(input())
s = input()


prod = 1
for char in set(s):
    num = s.count(char)
    prod *= (num + 1)

print((prod - 1) % (pow(10, 9) + 7))
### BUGGY CODE ###

N = int(input())
num_list = list(map(int,input().split()))
q = int(input())

for i in range(q):
  query = list(map(int,input().split()))
  for j in range(len(num_list)):
    if num_list[j] == query[0]:
      num_list[j] = query[1]
  print(sum(num_list))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
c = 0
s = sum(A)
table = [0] * 100001
 
for i in A:
    table[i] += 1
 
for i in range(Q):
    B, C = map(int,input().split())
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    S.append(s)

for s in S:
    print(s)
### BUGGY CODE ###

s = list(input())
pos = 0
str_len = len(s)
count = 0
state = 0
seq_a = 0

while pos < str_len:
    if state == 0:
        if s[pos] == "A":
            state = 1
            seq_a = 1
        pos += 1
    elif state == 1:
        if s[pos] == "B":
            state = 2
        elif s[pos] == "A":
            state = 1
            seq_a += 1
        else:
            state = 0
        pos += 1
    elif state == 2:
        if s[pos] == "C":
            for i in range(pos - seq_a + 1, pos + 1):
                s[i] = "A"
            s[pos - seq_a - 1] = "B"
            s[pos - seq_a] = "C"
            pos = pos - seq_a + 1
            if pos < 0:
                pos = 0
            count += seq_a
            state = 0
            seq_a = 0
#            print(pos, s)
        elif s[pos] == "A":
            state = 1
            seq_a = 1
            pos += 1
        else:
            state = 0
            pos += 1

print(count)


### FIXED CODE ###

s = input()
pos = 0
str_len = len(s)
count = 0
seq_a = 0
seq_bc = 0

while pos < str_len:
    if s[pos] == "A":
        while pos < str_len and s[pos] == "A":
            seq_a += 1
            pos += 1
        if pos + 1 < str_len and s[pos] == "B" and s[pos+1] == "C":
            while pos < str_len and s[pos] == "B" and pos + 1 < str_len and s[pos+1] == "C":
                seq_bc += 1
                pos += 2
            count += seq_a * seq_bc
            if pos < str_len and s[pos] != "A":
                seq_a = 0
            seq_bc = 0
        else:
            pos += 1
            seq_a = 0
    else:
        pos += 1
        seq_a = 0

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

from itertools import combinations, product
import copy
H, W = map(int, input().split())


def search_steps(maze, cy, cx, gy, gx, step):
    if (cy, cx) == (gy, gx):
        return step
    ss = []
    for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        ny, nx = cy + dy, cx + dx
        new_maze = copy.deepcopy(maze)
        new_maze[cy][cx] = "#"
        if 0 <= ny <= H - 1 and 0 <= nx <= W - 1 and maze[ny][nx] == ".":
            s = search_steps(new_maze, ny, nx, gy, gx, step + 1)
            if s >= 0:
                ss.append(s)

    if len(ss) == 0:
        return -1
    else:
        mss = min(ss)
        return min(ss) if mss >= 0 else -1


S = [0] * H
for i in range(H):
    S[i] = list(input())

max_steps = 0
for s, g in combinations(range(H * W), 2):
    sy, sx = s // W, s % W
    gy, gx = g // W, g % W
    if S[sy][sx] == "#" or S[gy][gx] == "#":
        continue

    steps = search_steps(copy.deepcopy(S), sy, sx, gy, gx, 0)
    if steps > max_steps:
        max_steps = steps

print(max_steps)

### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

max_step = 0
for i in range(H * W):
    sy, sx = i // W, i % W
    if S[sy][sx] == "#":
        continue

    steps = [[-1] * W for _ in range(H)]
    steps[sy][sx] = 0
    queue = [(sy, sx)]
    while len(queue) >= 1:
        cy, cx = queue.pop(0)
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                continue
            if S[ny][nx] == "#" or steps[ny][nx] >= 0:
                continue
            queue.append((ny, nx))
            steps[ny][nx] = steps[cy][cx] + 1

    ms = max(max(r) for r in steps)
    max_step = max(ms, max_step)

print(max_step)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

answer = 0
for i in range(n-k+1):
    for j in range(i+k-1,n):
        answer = (answer + (a[j] - a[i]) * kai[j-i-1] *gyaku[j-i-1-(k-2)] * gyaku[k-2])%mod

if k == 1:
    print(0)
else:
    print(answer)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

answer = 0
for i in range(k-1,n):
    answer = (answer + a[i] * kai[i] * gyaku[(i)-(k-1)] * gyaku[k-1]) % mod

answer2 = 0
for i in range(n-k+1):
    answer2 = (answer2 + a[i] * kai[n-i-1] * gyaku[(n-i)-k] * gyaku[k-1]) % mod


if k == 1:
    print(0)
else:
    print((answer - answer2)%mod)