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

def bfs():
      global count
      now=que.popleft()
      now_step=steps[now[0]][now[1]]
      for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
            ny=now[0]+dy
            nx=now[1]+dx
            if 0<=ny<=H-1 and 0<=nx<=W-1:
                  if maze[ny][nx]=="G":
                        count=now_step+1
                        break
                  elif maze[ny][nx]==".":
                        if ([ny,nx] in que)==False:
                              que.append([ny,nx])
                              steps[ny][nx]=now_step+1
                  else:
                        pass

import copy
from collections import deque

H,W=map(int,input().split())
maze=[]
for i in range(H):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze_copy=copy.deepcopy(maze)
max_step=0

for s_i in range(H):
   for s_j in range(W):
      if maze[s_i][s_j]=="#":
         continue

      for g_i in range(H):
         for g_j in range(W):
            if maze[g_i][g_j]=="#":
               continue
            
            maze=copy.deepcopy(maze_copy)
            que=deque([[s_i,s_j]])
            maze[s_i][s_j]="S"
            maze[g_i][g_j]="G"
            steps=[[-1]*W for c in range(H)]
            steps[s_i][s_j]=0
            count=0

            if (s_i,s_j)==(g_i,g_j):
               max_step=max(max_step,0)

            else:
               while(count==0):
                  bfs()
               max_step=max(max_step,count)

print(max_step)

### FIXED CODE ###

def bfs():
      global flag
      if len(que)==0:
         flag=False
      else:
         now=que.popleft()
         now_step=steps[now[0]][now[1]]
         for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
            ny=now[0]+dy
            nx=now[1]+dx
            if 0<=ny<=H-1 and 0<=nx<=W-1:
               if maze[ny][nx]==".":
                  if ([ny,nx] in que)==False:
                     maze[ny][nx]="A"
                     que.append([ny,nx])
                     steps[ny][nx]=now_step+1
               else:
                  pass

import copy
from collections import deque

H,W=map(int,input().split())
maze=[]
for i in range(H):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze_copy=copy.deepcopy(maze)
max_step=0

for s_i in range(H):
   for s_j in range(W):
      if maze[s_i][s_j]=="#":
         continue
            
      maze=copy.deepcopy(maze_copy)
      maze[s_i][s_j]="S"
      que=deque([[s_i,s_j]])
      steps=[[-1]*W for c in range(H)]
      steps[s_i][s_j]=0
      flag=True

      while(flag):
         bfs()

      toriaezu_max=0
      for i in range(H):
         toriaezu_max=max(toriaezu_max,max(steps[i]))
      max_step=max(max_step,toriaezu_max)

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

l, r = map(int, input().split())
x = []
for i in range(l, r):
    for j in range(i + 1, r + 1):
        mod = i * j % 2019
        x.append(mod)
print(min(x))


### FIXED CODE ###

l, r = map(int, input().split())
x = []
for i in range(l, r):
    for j in range(i + 1, r + 1):
        mod = i * j % 2019
        x.append(mod)
        if mod == 0:
            print(0)
            exit()
print(min(x))
### BUGGY CODE ###

x = int(input())

count = 0

for i in range(x+1):
    y = str(i)

    hako = []
    for k in range(10):
        hako.append(0)

    for j in range(len(y)):
        if y[j] == '0':
            hako[0] += 1
        if y[j] == '1':
            hako[1] += 1
        if y[j] == '2':
            hako[2] += 1
        if y[j] == '3':
            hako[3] += 1
        if y[j] == '4':
            hako[4] += 1
        if y[j] == '5':
            hako[5] += 1
        if y[j] == '6':
            hako[6] += 1
        if y[j] == '7':
            hako[7] += 1
        if y[j] == '8':
            hako[8] += 1
        if y[j] == '9':
            hako[9] += 1

    if hako[0] >= 1 or hako[1] >= 1 or hako[2] >= 1 or hako[4] >= 1 or hako[6] >= 1 or hako[8] >= 1 or hako[9] >= 1:
        continue

    if hako[3] >= 1 and hako[5] >= 1 and hako[7] >= 1:
        count += 1

print(count)

### FIXED CODE ###

N = int(input())

def dfs(s): # 文字列 s で始まる七五三数の個数
    if int(s) > N:
        return 0
    ret = 0
    flag = True
    for c in '753':
        if s.count(c) == 0:
            flag = False
    if flag:
        ret = 1
    for c in '753':
        ret += dfs(s + c)
    return ret

print(dfs("0"))
### BUGGY CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    h = [int(input()) for _ in range(N)]
    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 ###

from fractions import Fraction
from collections import deque
import math

A,B,C,D,E,F = map(int, input().split())

# 作りうる水の量を洗い出す
waters = set()
waters.add(100*A)
if 200*B <= F:
    waters.add(200*B)
q = deque([100*A, 200*B])

while q:
    w = q.popleft()
    # 容器に入れられる量より多いならパス
    if w > F: continue
    for n in [100*A, 200*B]:
        if w + n <= F:
            waters.add(w + n)
            q.append(w + n)

waters = list(waters)
waters.sort()

# 砂糖もFまでなのでとりうる量作れるやん
sugars = set()
sugars.add(C)
sugars.add(D)
q = deque([C,D])
while q:
    s = q.popleft()
    if s > F: continue
    for n in [C,D]:
        if s + n <= F:
            sugars.add(s+n)
            q.append(s+n)
sugars = list(sugars)
sugars.sort()

# 最大濃度
max_conc = 0
# 最大濃度の時の水と砂糖
total = 0
sugar = 0

for w in waters:
    for s in sugars:
        conc = 0
        # 容量を超えたらアウト
        if w+s > F: break
        # 解けきれない量でもアウト
        if s > w * Fraction(E,100): break

        conc = Fraction(s, s+w)
        if conc > max_conc:
            max_conc = conc
            total = s+w
            sugar = s

print(total, sugar)

### FIXED CODE ###




A,B,C,D,E,F = map(int, input().split())

# 作りうる水の量を洗い出す
waters = set()

for i in range(F//(100*A) + 1):
    for j in range((F-100*A*i)//(100*B) + 1):
        w = 100*A*i + 100*B*j
        if w != 0:
            waters.add(w)
waters = list(waters)
waters.sort()


sugars = set()
# Cを何回入れるか
for i in range(F//C + 1):
    # Dを何回いれるか
    for j in range((F - C*i) // D + 1):
        s = i*C + j*D
  
        sugars.add(s)


sugars = list(sugars)
sugars.sort()

# 最大濃度
max_conc = 0
# 最大濃度の時の水と砂糖
total = 0
sugar = 0

best_w = best_s = best_r = -1
for water in sorted(waters):
    for sugar in sorted(sugars):
        if water + sugar > F: break
        if water*E < sugar*100: break
        rate = sugar / (water + sugar)
        if rate > best_r:
            best_r = rate
            best_w = water
            best_s = sugar
print(best_s+best_w, best_s)
### BUGGY CODE ###

n, m = input().split()
n = int(n)
m = int(m)

result_list = []

# 正解した問題を入れるlist
done_list = []
correct = 0
pn = 0
done_list = []
pn_list = [0] * n

for i in range(m):
    a,b=input().split()
    
    if a not in done_list and b == "AC":
        done_list.append(a)
        correct += 1
        pn += pn_list[int(a) - 1]
    elif b == "WA":
        pn_list[int(a) - 1] += 1

print(correct, pn)

### FIXED CODE ###

n, m = input().split()
n = int(n)
m = int(m)

# 正解した問題を入れるlist

correct = 0
pn = 0
done_list = [0] * n
pn_list = [0] * n

for i in range(m):
    a,b=input().split()
    
    if done_list[int(a)-1] == 0 and b == "AC":
        done_list[int(a)-1] += 1
        correct += 1
        pn += pn_list[int(a) - 1]
    elif b == "WA":
        pn_list[int(a) - 1] += 1

print(correct, pn)
### BUGGY CODE ###

N = int(input())
A = list(int(m) for m in input().split())
ans = 1
for t in reversed(range(min(A) - 1)):
  B = list()
  for x in range(N):
    B.append(A[x] % (t+2))
    if B.count(0) != x+1:
      break
  if B.count(0) == N:
    ans = t+2
    break
print(ans)

### FIXED CODE ###

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x % y == 0:
      return y
    else:
      while x % y != 0:
        z = x % y
        x = y
        y = z
      return y


N = int(input())
A = list(int(m) for m in input().split())
ans = A[0]
for i in range(N):
  ans = gcd(A[i], ans)
print(ans)
### BUGGY CODE ###

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

x = 1
for i in a:
    x *= i
    
if x > 1000000000000000000:
    print(-1)
else:
    print(x)

### FIXED CODE ###

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

x = 1
flag = False
INF = 10**18
if 0 in a:
    print(0)
else:
    for i in range(n):
        if flag == False:
            x *= a[i]
        if x > INF:
            flag = True
    
    if flag:
        print(-1)
    else:
        print(x)
### BUGGY CODE ###

import numpy as np
n=int(input())
A=list(map(int,input().split()))
anp=np.array(A)
anp*=2
for i in range(len(A)):
    x=anp[i]
    flag=1
    for j in range(i+1,i+len(A)):
        k=j%len(A)
        if flag:
            x-=anp[k]
            flag=0
        else:
            x+=anp[k]
            flag=1
    x/=2
    print(int(x),end=" ")
print()

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

suma=sum(a)
x=[0]*n
tmp=0
for i in range(1,n,2):
    tmp+=a[i]
x[0]=suma-2*tmp

for i in range(1,n):
    x[i]=2*a[i-1]-x[i-1]
for i in x:
    print(i,end=" ")
### BUGGY CODE ###

def div(n,m):
    try:
        return n/m
    except ZeroDivisionError:
        return 0
def degit(n, m):
    r = []
    b = -1
    for i in xrange(m):
        s = div(n%(10**(i+1)),(10**i))
        if(b<s):
            b = s
            r.append(s)
    if(len(r) == m):
        return r
while True:
    (n, s) = [int(i) for i in raw_input().split()]
    if((0,0) == (n,s)):
        break
    ans = 0
    for i in xrange(10**n):
        r = degit(i,n)
        if(r==None):
            continue
        if(len(r)!=len(list(set(r)))):
            continue
        if(reduce(lambda x,y:x+y,r) == s):
            ans += 1
    print ans

### FIXED CODE ###

def dfs(n, sum ,depth):
    if(depth == 0):
        return int(sum == s)
    else:
        count = 0
        for i in xrange(n+1,10):
            count += dfs(i, sum+i, depth-1)
        return count

while True:
    (n, s) = [int(i) for i in raw_input().split()]
    if((0,0) == (n,s)):
        break
    print dfs(-1,0,n)
### BUGGY CODE ###

import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0
last_i=0
jyunban=[i for i in range(n)]
match=[0 for i in range(n)]
while True:
  day+=1
  check=[True for i in range(n)]
  jyunban_n=[]
  if jyunban==[]:
    print(-1)
    sys.exit()
  
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
        jyunban_n.append(i)
        jyunban_n.append(vs)
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
        
print(day)
      
    


### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = [[False]*W for _ in range(H)]
for h in range(H):
    s = input()
    for w in range(W):
        if s[w] == ".":
            S[h][w] = True
d = [[10**9]*W for _ in range(H)]
d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c > d[h][w]:
        continue
    # 歩いて移動
    # 上
    if h > 0:
        if S[h-1][w] and c < d[h-1][w]:
            d[h-1][w] = c
            deque.append(D, (h-1, w, c))
    # 下
    if h < H-1:
        if S[h+1][w] and c < d[h+1][w]:
            d[h+1][w] = c
            deque.append(D, (h+1, w, c))
    # 左
    if w > 0:
        if S[h][w-1] and c < d[h][w-1]:
            d[h][w-1] = c
            deque.append(D, (h, w-1, c))
    # 右
    if w < W-1:
        if S[h][w+1] and c < d[h][w+1]:
            d[h][w+1] = c
            deque.append(D, (h, w+1, c))
    # ワープで移動
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] and d[hh][ww] > c+1:
                d[hh][ww] = c+1
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])




### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = [[False]*W for _ in range(H)]
for h in range(H):
    s = input()
    for w in range(W):
        if s[w] == ".":
            S[h][w] = True
d = [[10**9]*W for _ in range(H)]
d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c > d[h][w]:
        continue
    # 歩いて移動
    # 上
    if h > 0:
        if S[h-1][w] and c < d[h-1][w]:
            d[h-1][w] = c
            deque.appendleft(D, (h-1, w, c))
    # 下
    if h < H-1:
        if S[h+1][w] and c < d[h+1][w]:
            d[h+1][w] = c
            deque.appendleft(D, (h+1, w, c))
    # 左
    if w > 0:
        if S[h][w-1] and c < d[h][w-1]:
            d[h][w-1] = c
            deque.appendleft(D, (h, w-1, c))
    # 右
    if w < W-1:
        if S[h][w+1] and c < d[h][w+1]:
            d[h][w+1] = c
            deque.appendleft(D, (h, w+1, c))
    # ワープで移動
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] and d[hh][ww] > c+1:
                d[hh][ww] = c+1
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])
### BUGGY CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

### FIXED CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)
### BUGGY CODE ###

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

    rui = [[0] * (M + 1) for _ in range(N + 1)]
    cnt = [[0] * (M) for _ in range(N)]

    n = 1
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            #cnt[i][j] = c
            rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] - rui[i][j] + c
            n = (n + c) % MOD

    #for v in cnt:
    #    n = (n + sum(v)) % MOD

    #print(rui)
    #print(cnt)
    print(n)

main()


### FIXED CODE ###

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

    rui = [[0] * (M + 1) for _ in range(N + 1)]
    #cnt = [[0] * (M) for _ in range(N)]

    n = 1
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            #cnt[i][j] = c
            rui[i+1][j+1] = (rui[i+1][j] + rui[i][j+1] - rui[i][j] + c) % MOD
            n = (n + c) % MOD

    #for v in cnt:
    #    n = (n + sum(v)) % MOD

    #print(rui)
    #print(cnt)
    print(n)

main()
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
  st = input().split()
  if int(st[0]) == 1:
    s = s[::-1]
  else:
    if int(st[1]) == 1:
      s = st[2] + s
    else:
      s = s + st[2]

print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

flag = 1
for i in range(q):
  st = input().split()
  if int(st[0]) == 1:
    flag *= -1
  else:
    tmp = int(st[1])*flag
    if tmp == 1 or tmp == -2:
      s.appendleft(st[2])
    else:
      s.append(st[2])

if flag == -1:
  s.reverse()
print(''.join(s))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

############################################################################################################
from itertools import combinations

MOD = mod=10**9+7

N, K = map(int, input().split())
C = Combination(N)
A = list(map(int, input().split()))
if K == 1:
    print(0)
    exit()
A.sort()

res = 0
for i,j in combinations(range(N),2):
    res += C(j-i+1-2,K-2) * (A[j] - A[i])

print(res%MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline

class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

############################################################################################################
from itertools import combinations

MOD = mod=10**9+7

N, K = map(int, input().split())
C = Combination(N)
A = list(map(int, input().split()))
if K == 1:
    print(0)
    exit()
A.sort()

res = 0
for i in range(K-1,N):
    res += C(i+1-1,K-1) * A[i]

for i in range(N-K+1):
    res -= C(N-i-1,K-1) * A[i]

print(res%MOD)
### BUGGY CODE ###

n = int(input())
s = sorted([str(input()) for _ in range(n)])

S = set(s)
c_m = int(0)
l = []

for i in range(len(S)):
    a = S.pop()
    c_i = int(s.count(a))
    if c_i > c_m:
        c_m = c_i
        l = [a]
    elif c_i == c_m:
        l.append(a)

l.sort()
for i in range(len(l)):
  print(l[i])


### FIXED CODE ###

n = int(input())
d = dict()
for _ in range(n):
    x = str(input())
    if x in d:
        d[x] += 1
        continue
    else:
        d[x] = 0

d_sort = sorted(d.items(), key=lambda d:d[1], reverse = True)
d_max = d_sort[0][1]

ans = []
for i in d_sort:
    if d_max == i[1]:
        ans.append(i[0])
    else:
        break

ans.sort()
for a in ans:
    print(a)