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

import sys
input = sys.stdin.readline

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = (-1, -1)
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] = v
            if l&1:
                self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] > res:
                res = self.data[i]
            i = ~-i//2
        return res

n,q = map(int, input().split())
start = [None]*q
se = set()
road = []
for i in range(n):
    s,t,x = map(int, input().split())
    se.add(x-s)
    se.add(x-(t-1))
    road.append([x, x-(t-1), x-s])
for i in range(q):
    d = int(input())
    start[i] = -d
    se.add(-d)

dd = sorted(se)
d = {j:i for i, j in enumerate(dd)}
k = len(d)

RUQ = RangeUpdateQuery(k)
road.sort(reverse=True)

for i, (x, s, t) in enumerate(road):
    l = d[s]
    r = d[t]
    RUQ.update(l, r+1, (i, x))

ans = []
for i in range(q):
    _, x = RUQ.query(d[start[i]])
    ans.append(x)

print(*ans, sep="\n")

### FIXED CODE ###

import sys
input = sys.stdin.readline

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = float("inf")
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] = v
            if l&1:
                self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,q = map(int, input().split())
start = [None]*q
se = set()

road = []
for i in range(n):
    s,t,x = map(int, input().split())
    road.append([x, x-t, x-s])
for i in range(q):
    d = int(input())
    start[i] = -d

start = start[::-1]

RUQ = RangeUpdateQuery(q)
road.sort(reverse=True)
from bisect import bisect_left,bisect_right
for i, (x, s, t) in enumerate(road):
    l = bisect_right(start, s)
    r = bisect_right(start, t)
    #print(x, (s,t), l, r)
    RUQ.update(l, r, x)

ans = []
for i in range(q):
    x = RUQ.query(i)
    if x == float("inf"):
        x = -1
    ans.append(x)
ans = ans[::-1]
print(*ans, sep="\n")
### BUGGY CODE ###

e = list(map(int,input().split()))
a = int(e[0])
b = int(e[1])
c = int(e[2])
d = int(e[3])

def div(x,y):
    cnt = 0
    for i in range(a,b+1):
        if (int(i/x)-i/x != 0) and (int(i/y)-i/y != 0):
            cnt += 1
    return cnt

print(div(c,d))

### FIXED CODE ###

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

def gcd(x,y):
    while y !=0:
        x,y = y,x%y
    return x

def sums(x):
    S1 = x//c
    S2 = x//d
    S3 = x// (c*d//gcd(c,d))
    return x - S1 - S2 + S3


print(sums(b)-sums(a-1))
### BUGGY CODE ###

import copy
n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = copy.deepcopy(x)
kako = [x]
while True:
  for i in range(m):
    to = a[i]-1
    if to == 0:
      b[0] = b[1]*2-b[0]
    elif to == n-1:
      b[n-1] = b[n-2]*2 - b[n-1]
    else:
      b[to] = (b[to+1]*2-b[to]+b[to-1]*2-b[to])/2
  if b in kako:
    break
  kako.append(copy.deepcopy(b))
rp = kako.index(b)
if rp>= k:
  for i in kako[k]:
    print(i)
  exit()
k -= rp
kako = kako[rp:]
k %= len(kako)
for i in kako[k]:
  print(i)


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
m,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
x2 = []
c = []
for i in range(1,n):
  b.append(i-1)
  x2.append(x[i]-x[i-1])
for i in range(m):
  to = a[i]-1
  b[to],b[to-1] = b[to-1],b[to]
c = [-1] * (n-1)
for i in range(n-1):
  c[b[i]] = i
for i in range(60):
  x3 = [0]*(n-1)
  if k&(1<<i):
    for i in range(n-1):
      x3[c[i]] = x2[i]
    x2 = x3
  c2 = [-1] * (n-1)
  for i in range(n-1):
    c2[i] = c[c[i]] 
  c = c2
s = x[0]
print(s)
for i in x2:
  s += i
  print(s)
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
for i,(a,b) in enumerate(AB):
    for t in range(T-1,-1,-1):
        for k in range(2):
            if dp[i][t][k] < 0: continue
            if dp[i+1][t][k] < dp[i][t][k]: dp[i+1][t][k] = dp[i][t][k]
            if t+a < T:
                if dp[i+1][t+a][k] < dp[i][t][k] + b: dp[i+1][t+a][k] = dp[i][t][k] + b
            if k==0:
                if dp[i+1][t][1] < dp[i][t][0] + b: dp[i+1][t][1] = dp[i][t][0] + b
print(max(a[1] for a in dp[-1]))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))
### BUGGY CODE ###

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = []
for i in range(n):
    print(dijkstra(adj, n, i)[0] % 2)

### FIXED CODE ###

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = dijkstra(adj, n, 0)
for i in shortest:
    print(i % 2)
### BUGGY CODE ###

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

ans = a[0]
for i in range(1, n):
  if a[i] == 0:
    ans = 0
    break
  ans = ans * a[i]

if ans > 1000000000000000000:
  ans = -1

print(ans)


### FIXED CODE ###

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

if (0 in a):
  print(0)
else:
  ans = 1
  for num in a:
    ans *= num
    if ans > 1000000000000000000:
      print(-1)
      exit()
  print(ans)
### BUGGY CODE ###

from fractions import gcd
k=int(input())
ans=0
for p in range(1,k+1):
  for q in range(1,k+1):
    for r in range(1,k+1):
      ans+=gcd(p,gcd(q,r))
print(ans)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for p in range(1,k+1):
  for q in range(1,k+1):
    for r in range(1,k+1):
      ans+=gcd(p,gcd(q,r))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = count = 0; pro = 1

d,g=map(int,input().split());g//=100
D=collections.defaultdict(lambda: inf )
D[0]=0
for i in range(1,d+1):
    p,c=map(int,input().split());c//=100
    # for key, value in tuple(D.items()):
    #     print(D[key],p)
    #     D[key+i*p+c//100] = min(D[key+i*p+c//100], D[key]+p)
    S=D.copy()
    for key,value in tuple(D.items()):
        for k in range(1,p):    
        # print(D[key+i])
            D[key+i*k] = min(D[key+i*k],S[key]+k)
        D[key+i*p+c] = min(D[key+i*p+c],S[key]+p)
ans=inf
for key,value in sorted(D.items()):
    # print(key,value)
    if key>=g:
        ans=min(ans,value)
print(ans)
        


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = count = 0; pro = 1

d,g=map(int,input().split());g//=100
D=collections.defaultdict(lambda: inf )
D[0]=0
for i in range(1,d+1):
    p,c=map(int,input().split());c//=100
    # for key, value in tuple(D.items()):
    #     print(D[key],p)
    #     D[key+i*p+c//100] = min(D[key+i*p+c//100], D[key]+p)
    S=D.copy()
    for key,value in S.items():
        for k in range(1,p):    
        # print(D[key+i])
            D[key+i*k] = min(D[key+i*k],S[key]+k)
        D[key+i*p+c] = min(D[key+i*p+c],S[key]+p)
ans=inf
for key,value in D.items():
    # print(key,value)
    if key>=g:
        ans=min(ans,value)
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int,  input().split())
ans = 0
for i in range(3000 // R + 1):
    for j in range(3000 // G + 1):
        tmp = (N - i * R - j * G)
        if tmp % B == 0 and tmp >= 0:
            ans += 1
print(ans)


### FIXED CODE ###

R, G, B, N = map(int,  input().split())
ans = 0
for i in range(3000 // R + 1):
    for j in range(3000 // G + 1):
        tmp = (N - i * R - j * G)
        if tmp % B == 0 and tmp >= 0:
            ans += 1
        elif tmp < 0:
            break
print(ans)
### BUGGY CODE ###

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())
A = list(map(int, input().split()))
B = A[:]
B.sort()
C = [B[0]]
D = [1]
L = 0
for i in range(N-1):
    if B[i] == B[i+1]:
        D[L] += 1
    else:
        C.append(B[i+1])
        D.append(1)
        L += 1

for i in range(N):
    ans = 0
    for j in range(len(C)):
        if C[j] == A[i] and D[j]>2:
            ans += cmb(D[j]-1,2)
        if C[j] != A[i] and D[j]>1:
            ans += cmb(D[j],2)
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
C = {}
for i in A:
    if i in C.keys():
        C[i] += 1
    else:
        C[i] = 1

total = 0

for i in C.keys():
   if C[i]>1:
        total += (C[i]*(C[i]-1))//2

for i in A:
    print(total-(C[i]-1))
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        for x in range(10):
            each_extras[cnt][x] = x * 10 ** i % 13
        cnt += 1

each_extras = np.array(each_extras)
# print(extra)
dp = np.array([[0 for i in range(13)] for j in range(cnt+1)])
dp[0][extra % 13] = 1
for i in range(cnt):
    for each in each_extras[i]:
        # for j in range(13):
            # dp[i+1][(j + each) % 13] += dp[i][j] % mod
        # print(each)
        dp[i+1] += np.roll(dp[i],each) % mod

# print(dp)
print(dp[-1][5] % mod)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))


"""
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


# print(dp)
print(dp[-1][5] % mod)
"""


S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13

# print(dp)
print(dp[-1][5])
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
MAX = 100000

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)
        inP_list[prime] = True

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)
        inP_list[a]=True

    return P

inP_list = [False]*MAX
p_list=eratosthenes(MAX)

ans_sum_list = [0] * MAX

for i in range(3,MAX, 2):
    if inP_list[i] and inP_list[(i+1)//2]:
        ans_sum_list[i] += 1
    ans_sum_list[i] += ans_sum_list[i-2]

q = int(input())
ans = [0]*q
for i in range(q):
    l, r = map(int, input().split())
    ans[i] = ans_sum_list[r] - ans_sum_list[max(1,l-2)]

print(*ans, sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

q = int(input())

def eratosthenes2(limit):
    is_prime = [1] * (limit + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]==0:
            continue
        for j in range(i * 2, limit + 1, i):
            is_prime[j] = 0
    return is_prime

limit = 10**5

is_prime = eratosthenes2(limit)
prime_list = [i for i in range(limit + 1) if is_prime[i]]

like_2017=[0]*limit

for p in prime_list:
    if is_prime[(p+1)//2]==1:
        like_2017[p] = 1

from itertools import accumulate
B = [0] + like_2017
B = list(accumulate(B))

ans=[0]*q
for i in range(q):
    l, r = map(int, input().split())
    ans[i]=B[r+1]-B[l]

print(*ans,sep='\n')
### BUGGY CODE ###

import numpy as np

n = int(input())
arr = []

for i in range(n):
    arr.append(list(map(int, input().split(' '))))

arr = np.array(arr)

takahashi = 0
aoki = 0


for i in range(n):
    max_i = np.argmax(np.sum(arr, axis=1))
    if i % 2 == 0:
        takahashi += arr[max_i, 0]
    else:
        aoki += arr[max_i, 1]
    arr = np.delete(arr, max_i, axis=0)
    
print(takahashi - aoki)

### FIXED CODE ###

import numpy as np

n = int(input())
arr = []

for i in range(n):
    arr.append(list(map(int, input().split(' '))))

arr = np.array(arr)
arr = arr[np.argsort(np.sum(arr, axis=1))[::-1]]
takahashi = np.sum(arr[::2, 0], axis=0)
aoki = np.sum(arr[1::2, 1], axis=0)

print(takahashi - aoki)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
# import math
# sys.setrecursionlimit(10**8)
# INF = float('inf')
# PI = math.pi()
# from functools import lru_cache
# @lru_cache(maxsize=None)

n = int(input())
# a, b = map(int, input().split())
a = list(map(int, input().split()))
# s = [list(map(int,list(input()))) for i in range(h)]

ans = 1
for item in a:
    ans=ans*item
if ans>10**18:
    print(-1)
    sys.exit()
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import numpy as np

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

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

a = [s for s in aa if s != 1]
a.sort(reverse=True)

# keta = 0
# for item in a:
#     k = len(str(item))
#     keta += k-1
#     if keta>18:
#         print(-1)
#         sys.exit()

prod = 1
for item in a:
    prod*=item
    if prod>10**18:
        print(-1)
        sys.exit()

# arr = np.array(a)
# ans = arr.prod()
# if ans>10**18:
#     print(-1)
#     sys.exit()

print(prod)
### BUGGY CODE ###

N, K = map(int, input().split())
LR = set()
MOD = 998244353
import sys
sys.setrecursionlimit(10**6)

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        LR.add(j)
#print(list(LR))


class Search:
    def __init__(self):
        self.ans = 0

    def dfs(self, now):
        if now == N:
            self.ans += 1
            return
        if now > N:
            return
        for d in LR:
            self.dfs(d + now)


s = Search()
s.dfs(1)
print(s.ans % MOD)

# LR = [list(map(int,input().split())) for i in range(N)]
# dp = [0] * (N + 1)
# dp[0] = 1
# for i in range(1, N):
#     for d in LR:
#         if i - d < 0: break
#         dp[i] += (dp[i - d]) % MOD
# print(dp[N-1] % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(K)]
MOD = 998244353

dp = [0] * (N + 1)
dp[1] = 1
dp_sum = [0] * (N + 1)
dp_sum[1] = 1


def get(l, r, i):
    return dp_sum[max((i - l), 0)] - dp_sum[max((i - r-1), 0)]


for i in range(1, N+1):
    for l, r in LR:
        dp[i] += get(l, r, i) % MOD
    dp_sum[i] = (dp_sum[i - 1] + dp[i])%MOD
print(dp[N] % MOD)
### BUGGY CODE ###

n=int(input())
lisa=[]

for i in range(n):
    a=int(input())
    if a in lisa:
        lisa.remove(a)
    else:
        lisa.append(a)

print(len(lisa))


### FIXED CODE ###

n=int(input())
s=set()
for i in range(n):
    a=int(input())
    if a in s:
        s.remove(a)
    else:
        s.add(a)
print(len(s))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,W+1):
    DP[i][j] = max(DP[i][j],DP[i-1][j])
    if j-wv[i-1][0] >= 0:
      DP[i][j] = max(DP[i][j],DP[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(DP[-1][-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,W+1):
    DP[i][j] = max(DP[i][j],DP[i-1][j])
    if j-wv[i-1][0] >= 0:
      DP[i][j] = max(DP[i][j],DP[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(DP[-1][-1])
### BUGGY CODE ###

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

import sys
input = sys.stdin.readline
mod = 10**9+7  
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = sorted(a)
a = tuple(a)

ans = 0
for i in range(n):
  p = a[i]*comb(n-1-i,k-1,mod)
  q = a[i]*comb(i,k-1,mod)
  if n-i < k:
    p = 0
  if i < k-1:
    q = 0
  #print(p,q)
  ans += q
  ans -= p
  ans %= mod
print(ans)

### FIXED CODE ###

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        # モジュラ逆数の性質
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

import sys
input = sys.stdin.readline
mod = 10**9+7  
n,k = [int(i) for i in input().split()]
fact, fact_inv = make_array_for_comb(n,mod)
a = [int(i) for i in input().split()]
a = sorted(a)
a = tuple(a)

ans = 0
for i in range(0,n-k+1):
  p = a[i]*comb(n-1-i,k-1,mod)
  ans -= (p%mod)
  ans %= mod
for i in range(k-1,n):
  q = a[i]*comb(i,k-1,mod)
  ans += (q%mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
#for p in lcm_pf:
#    lcm = lcm * (p ** lcm_pf[p])
import math
for v in a:
    lcm = (lcm // math.gcd(lcm, v)) * v

ans = 0
for v in a:
    #ans = ans + (lcm // v)
    ans = (ans + (lcm // v)) % MOD
print(ans % MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)
### BUGGY CODE ###

n=int(input())
m=n;i=2
while i<=n and m!=1:
    if not m%i:
        n=n*(i-1)//i
        while not m%i:m//=i
    i+=1
print(n)

### FIXED CODE ###

n=m=int(input())
i=2
while i*i<=n:
    if n%i==0:
        m=m//i*(i-1)
        while n%i==0: n//=i
    i+=1
if n!=1:m=m//n*(n-1)
print(m)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print(extractMax(A))
    else:
        break



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))