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

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        #z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        S1, S2 = C1, C2[j:]
        res = [0]
        c = 0
        for i in range(min(len(S1), len(S2))):
            if S1[i] == S2[i]:
                c += 1
            res.append(c)
        res.reverse();  Z1.append(res)

        #z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
        S1, S2 = C1[j:], C2
        res = [0]
        c = 0
        for i in range(min(len(S1), len(S2))):
            if S1[i] == S2[i]:
                c += 1
            res.append(c)
        res.reverse();  Z2.append(res)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

n=int(input())

S=[input() for _ in range(n)]

ans=0

for i in range(n-1):
    for j in range(i+1,n):
        if sorted(S[i])==sorted(S[j]):
            ans+=1
print(ans)

### FIXED CODE ###

import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())

S=[''.join(sorted(input())) for _ in range(n)]

c=collections.Counter(S)
ans=0
for i in c.values():
    if i==2:
        ans+=1
    elif i>2:
        ans+=cmb(i,2)
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
count = [0]
def sub(i1,i2,i3):
    count[0] += 1
    if dp[i1][i2][i3] is not None:
        return dp[i1][i2][i3]
    ans = 1
    p = 0
    if i1>0:
        ans += i1/n * sub(i1-1,i2,i3)
        p += i1/n
    if i2>0:
        ans += i2/n * sub(i1+1,i2-1,i3)
        p += i2/n
    if i3>0:
        ans += i3/n * sub(i1,i2+1,i3-1)
        p += i3/n
    ans = ans/p
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from itertools import count, cycle, repeat
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)
### BUGGY CODE ###

#####
# C #
#####

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

ans = 0
for i in range(len(A)-1):
    tmp1 = A[i] % (10**9 + 7)
    tmp2 = sum(A[i+1:]) % (10**9 + 7)
    ans += tmp1 * tmp2
    ans %= (10**9 + 7)
    # for j in range(1,len(A)-i
    #     # print(A[i],'A[i]',A[i+j],'A[i+j]')
    #     tmp_ai = A[i] % (10**9 + 7)
    #     tmp_aij = A[i+j] % (10**9 + 7)
    #     tmp += (tmp_ai * tmp_aij) % (10**9 + 7)
    #     # print(tmp,'tmp')
    # tmp %= (10**9 + 7)
    # ans += tmp

# ans %= (10**9 + 7)
print(ans)

### FIXED CODE ###

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

sumA = sum(A)
ans = 0
for i in range(len(A)-1):
    sumA -= A[i]
    tmp1 = A[i] % (10**9 + 7)
    tmp2 = sumA % (10**9 + 7)
    ans += tmp1 * tmp2
    ans %= (10**9 + 7)
    
print(ans)
### BUGGY CODE ###

# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

        # r-1の時に満たすべき条件
        g_min[r-1] = max(g_min[r-1], l)

    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))


### FIXED CODE ###

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
INF = float("inf")


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def update_all(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        # idx番目の要素をxに更新する
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        # [a, b)の最小値を求める
        if r <= a or b <= l:
            # [a, b)が[l, r)と交差しない
            return self.ele_id

        if a <= l and r <= b:
            # [a, b)が[l, r)を完全に含む
            return self.data[k]
        else:
            # [a, b)と[l, r)は一部被る
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n, m = map(int, input().split())
l_dict = [[] for _ in range(n)]
r_dict = [[] for _ in range(n)]
edge = []
for i in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    l_dict[l].append(i)
    r_dict[r].append(i)
    edge.append((l, r, c))

dp = [INF] * n
dp[0] = 0
seg_rmq = SegTree(n, INF, min)
seg_rmq.update(0, 0)

for i in range(1, n):
    for j in r_dict[i]:
        l, r, c = edge[j]
        tmp = seg_rmq.query(l, r)
        dp[i] = min(dp[i], tmp + c)

    seg_rmq.update(i, dp[i])

ans = dp[-1] if dp[-1] != INF else -1

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    INF = float('inf')
    dist = [INF] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap, (dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edge[l].append((c, r))
for i in range(1, n):
    edge[i].append((0, i - 1))

dist = dijkstra(edge, n, 0)
ans = dist[-1] if dist[-1] != float("inf") else -1

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

N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for low in range(N-2):
    for mid in range(low+1,N-1):
        for hi in range(mid+1,N):
            if L[hi] < L[low] + L[mid]: ans += 1
print(ans)

### FIXED CODE ###

from itertools import *
N = int(input())
L = list(map(int,input().split()))
csum = list(0 for _ in range(2000+1))
for i in range(N): csum[L[i]] += 1
csum = list(accumulate(csum))
ans = 0
for ib in range(N):
    for ia in range(ib):
        a, b = L[ia], L[ib]
        minL, maxL = abs(a-b), a+b
        ans += csum[maxL-1] - csum[minL]
        if minL < a and a < maxL: ans -= 1
        if minL < b and b < maxL: ans -= 1
print(ans//3)
### BUGGY CODE ###

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

l=[]
for i in range(n,0,-1):
  l.append(syain.count(i))
  syain = [s for s in syain if s != i]

for i in range(n):
  print(l[n-1-i])

### FIXED CODE ###

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

b = [0]*(n+2)

for i in range(n-1):
  b[a[i]] += 1
  
for i in range(1,n+1):
  print(b[i])
### BUGGY CODE ###

from math import gcd
ans=0
n=int(input())
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      num=gcd(i,j)
      ans+=gcd(num,k)
print(ans)
      

### FIXED CODE ###

import math
import collections
k=int(input())
ans=0
a=[]
for i in range(1,k+1):
    for j in range(1,k+1):
        a.append(math.gcd(i,j))
a=collections.Counter(a)
for key,value in a.items():
    for i in range(1,k+1):
        ans+=math.gcd(i,key)*value
print(ans)
### BUGGY CODE ###

import math

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = math.gcd(a,l[i])
    return a

K = int(input())
list_A=[]
for i in range(K-1):
    for j in range(K-1):
        for k in range(K-1):
            list_A.append(gcdlist([i+2,j+2,k+2]))
print(sum(list_A)+K**2+(K**2-K)+(K**2-2*K)+1)

### FIXED CODE ###

import math


K = int(input())
S=0
for i in range(1,K+1):
    for j in range(1,K+1):
        s=math.gcd(i,j)
        for k in range(1,K+1):
            S += math.gcd(s,k)

print(S)
### BUGGY CODE ###

N = int(input())
x = list([int(i) for i in input().split()])
cnt = 0
while True:
    flag = False
    for i in x:
        if i & 1:
            flag = True
            break
        else:
            i >>= 1
    else:
        cnt += 1
    if flag:
        break
print(cnt)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
mn_lst = []
for i in x:
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i >>= 1
    mn_lst.append(cnt)
    
print(min(mn_lst))
### BUGGY CODE ###

n = input()
s = input()

n = int(n)

allnum = list(range(0, 1000))

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            num = int(s[i]) * 100 + int(s[j]) * 10 + int(s[k])
            # print(num)

            try:
                allnum.remove(num)
            except:
                pass

print(1000 - len(allnum))

### FIXED CODE ###

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

ans_count =0

for i in range(10):
    for j in range(10):
        for k in range(10):
            i_pos = s.find(str(i))

            if i_pos < 0:
                continue

            j_pos = s.find(str(j),i_pos+1)

            if j_pos < 0:
                continue

            k_pos = s.find(str(k), j_pos +1)

            if k_pos < 0:
                continue

            ans_count += 1

print(ans_count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
S = [0]*(N+1)
S[0] = 0
diff = float("INF")
idx = -1
for i in range(N):
  S[i+1] = S[i] + A[i]
  if abs(sum(A)/2 - S[i+1]) < diff:
    diff = sum(A)/2 - S[i+1]
    idx = i+1
lsum = S[idx]
rsum = S[-1]-S[idx]
print(abs(lsum-rsum))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
c = sum(A)/2

S = [0] * (N+1)
S[0] = 0
for i in range(N):
  S[i+1] = A[i] + S[i]

m = float("INF")
j = -1
for i in range(1, N+1):
  if abs(c - S[i]) < m:
    m = abs(c - S[i])
    j = i

print(abs((S[N] - S[j]) - S[j]))
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(-b)
    except:
        pass
ans = 0
a = []
for i in range(M):
    a += w[i]
    heapq.heapify(a)
    try:
        ans += -heapq.heappop(a)
    except:
        pass
print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
w = [[] for i in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    try:
        w[a-1].append(-b)
    except:
        pass
ans = 0
a = []
heapq.heapify(a)
for i in range(M):
    for x in w[i]:
        heapq.heappush(a, x)
    try:
        ans += -heapq.heappop(a)
    except:
        pass
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
b = 1
def multi(n,b,l):
    for i in range(n):
        b = b * l[i] 
    if b > 10 ** 18:
        b = -1
    return b
b = multi(n,b,l)
print(b)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def input():
    return sys.stdin.readline()[:-1]
n = int(input())
l = list(map(int, input().split(" ")))
output = 1

if 0 in l:
    print(0)
    sys.exit()

for i in range(n):
    output = output * int(l[i])
    if output > 10 ** 18:
        output = -1
        break
print(output)
### BUGGY CODE ###

from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

s = list(input())
n = len(s)
c = n-1
ans = 0
while True:
    if c <2:
        break
    if s[c-2]+s[c-1]+s[c]=="ABC":
        ans += 1
        s[c-2]="B"
        s[c-1]="C"
        s[c]="A"
        if c+2 < n:
            c +=2
    else:
        c -=1

print(ans)

### FIXED CODE ###

S = input()
S = S.replace("BC","D")

ans = 0
a = 0
for s in S:
    if s =="A":
        a += 1
    elif s =="D":
        ans += a
    else:
        a = 0

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

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    L = lcm(L,a)
print(sum([L//a for a in A])%(10**9+7))

### FIXED CODE ###

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    newL = lcm(L,a)
    ans = ans*(newL//L) + newL//a
    L = newL
print(ans%(10**9+7))
### BUGGY CODE ###

n, w = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(n)]
dp = {}
for j in range(1,w+1):
    for i in range(1,n+1):
        if j-items[i-1][0] >= 0:
            if str(i-1)+":"+str(j) not in dp:
                dp[str(i - 1) + ":" + str(j)] = 0
            if str(i-1)+":"+str(j-items[i-1][0]) not in dp:
                dp[str(i - 1) + ":" + str(j - items[i - 1][0])] = 0
            dp[str(i)+":"+str(j)] = max(dp[str(i-1)+":"+str(j)],dp[str(i-1)+":"+str(j-items[i-1][0])]+items[i-1][1])
        else:
            if str(i-1)+":"+str(j) not in dp:
                dp[str(i - 1) + ":" + str(j)] = 0
            dp[str(i)+":"+str(j)] = dp[str(i-1)+":"+str(j)]
print(dp[str(n)+":"+str(w)])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[-1]*301 for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    w,v=map(int,input().split())
    if i==0:
        base=w
    for i in range(N)[::-1]:
        for j in range(301)[::-1]:
            if dp[i][j]!=-1:
                dp[i+1][j+w-base]=max(dp[i][j]+v,dp[i+1][j+w-base])

ans=0
for index,item in enumerate(dp):
    if W-index*base+1<=0:
        break
    ans=max(max(item[:W-index*base+1]),ans)

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

n = int(input())
trs = [int(input()) for _ in range(n)]
cannot = False

visited = [False] * n
visited[0] = True
for i in range(n):
  if not visited[i]:
    cannot = True
  else:
    x = min(i + trs[i] // 10, n - 1)
    if not visited[x]:
      for j in range(i + 1, x + 1):
        visited[j] = True

visited = [False] * n
visited[n - 1] = True
for i in range(n - 1, -1, -1):
  if not visited[i]:
    cannot = True
  else:
    x = max(i - trs[i] // 10, 0)
    if not visited[x]:
      for j in range(i - 1, x - 1, -1):
        visited[j] = True

if cannot:
  print("no")
else:
  print("yes")


### FIXED CODE ###

n = int(input())
trs = [int(input()) for _ in range(n)]
cum = []
cannot = False

acc = 0
for i in range(n):
  acc = max(acc, i + trs[i] // 10)
  acc = min(acc, n -  1)
  cum.append(acc)

rev = []
acc = 0
for i in range(n):
  acc = max(acc, i + trs[n - 1 - i] // 10)
  acc = min(acc, n - 1)
  rev.append(acc)

ind = 0
tmp = 0
while True:
  ind = cum[ind]
  if ind == n - 1:
    break
  if ind == tmp:
    cannot = True
    break
  tmp = ind

ind = 0
tmp = 0
while True:
  ind = rev[ind]
  if ind == n - 1:
    break
  if ind == tmp:
    cannot = True
    break
  tmp = ind

if cannot:
  print("no")
else:
  print("yes")
### BUGGY CODE ###

def COMint():
  fac[0]=1
  fac[1]=1
  finv[0]=1
  finv[1]=1
  inv[1]=1
  for i in range(2,N+1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
def com(n,k):
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

MOD=10**9+7
N,K=[int(x) for x in input().split()]
A= [int(x) for x in input().split()]
A= sorted(A)
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
COMint()
ans=0
#print(fac)
for j in range(N-1,-1,-1):
  for i in range(j-K+2):
    mi = A[i]
    ma = A[j]
    #print(ma,mi,i,j,L[j-i-1])
 #     print(j-i-1,com(j-i-1,K-2))
    ans+=(ma-mi)*com(j-i-1,K-2)
print(ans%(10**9+7))

### FIXED CODE ###

def COMint():
  fac[0]=1
  fac[1]=1
  finv[0]=1
  finv[1]=1
  inv[1]=1
  for i in range(2,N+1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
def com(n,k):
  if n<k:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
MOD=10**9+7
N,K=[int(x) for x in input().split()]
A= [int(x) for x in input().split()]
A= sorted(A)
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
COMint()
ans=0
#print(fac)
for j in range(N):
  ans+=(A[j])*com(j,K-1)
  ans-=(A[j])*com(N-1-j,K-1)
print(ans%(10**9+7))