Harryxun/stf_run huggingface dataset:
from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))

def lcm(a, b):
    return int(a*b / gcd(a, b))
"""
ak の2を除く公約数の組み合わせ一覧のうち、M以下のものを上げれば良い？
もしakが0が含まれると、0個
"""

l = a[0]
for a_ in a[1:]:
    l = lcm(l, a_)
ans = (m // l)
if ans == 0:
    print(ans)
else:
    print(ans+1)

### FIXED CODE ###

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))

def lcm(a, b):
    return a*b // gcd(a, b)
"""
akが偶数だから、bk=2akとして、
bk × (2p + 1)を満たすpが存在すれば良い
2p+1は奇数のため、Xとbkの2の素因数は一致しなければならない
akに含まれる最大の2^kを探す。
"""
if len(a) == 1: lcm_all = a[0]//2
else: lcm_all = lcm(a[0]//2, a[1]//2)
amax = 0
for i in range(1, n):
    lcm_all = lcm(lcm_all, a[i]//2)
    amax = max(amax, a[i]//2)

f = True
if lcm_all > m:
    f = False
for i in range(n):
    if n == 1: break
    if (lcm_all//(a[i]//2))%2 == 0:
        # akの2の約数の数がそろわないので、どんな奇数を掛けても共通のXを作れない
        f = False
if f:
    # amaxの奇数倍でmを超えないもの
    ans = (m // lcm_all + 1)//2
    print(ans)
else:
    print(0)
[a, b] = list(map(int, input().split()))

print(a//b)
print(a%b)
print({:.5f}.format(a/b))

### FIXED CODE ###

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

print(a//b)
print(a%b)
print("{:.5f}".format(a/b))
S = input()

if S[2] = S[3]:
  if S[4] = S[5]:
    print('Yes')
  else:
    print('No')

else:
  print('No')

### FIXED CODE ###

S = input()

if S[2] == S[3]:
  if S[4] == S[5]:
    print('Yes')
  else:
    print('No')

else:
  print('No')
import math
a,b,c,d = map(int,input().split())
s=0
start = a//c
end = b//c
a * b // math.gcd(a, b)
if start*c<a:
    s += end-(start+1)+1
else:
    s += end - start + 1
if d%c!=0:
    start = a // d
    end = b // d
    if start * d < a:
        s += end - (start + 1) + 1
    else:
        s += end - start + 1
last =c * d // math.gcd(c, d)
start = a//last
end = b//last
if start*c<a:
    s -= end-(start+1)+1
else:
    s -= end - start + 1
print((b-a+1)-s)


### FIXED CODE ###

a, b, c, d = map(int, input().split())
s = 0
start = a // c
end = b // c
if start * c < a:
    s += end - (start + 1) + 1
else:
    s += end - start + 1
if d % c != 0:
    start = a // d
    end = b // d
    if start * d < a:
        s += end - (start + 1) + 1
    else:
        s += end - start + 1
    def gcd(x, y):
        while y != 0:
            (x, y) = (y, x % y)
        return x
        return gcd
    last = c * d // gcd(c, d)
    start = a // last
    end = b // last
    if start * last < a:
        s -= end - (start + 1) + 1
    else:
        s -= end - start + 1
print((b - a + 1) - s)
def R(xyrz,xyrz1):
	x, y, z, r  = xyrz
	x1,y1,z1,r1 = xyrz1
	return max(0,((x-x1)**2 + (y-y1)**2 + (z-z1)**2)**0.5 - r - r1)

while 1:
	n = input()
	if n == 0: break
	xyzr = [map(float,raw_input().split()) for i in range(n)]
	ml = 1e12
	for i in range(n):
		for j in range(i+1,n):
			l = R(xyzr[i],xyzr[j])
			if l < ml:
				ml = l
				s = i
	ans = 0.0
	chain = [xyzr.pop(s)]
	while xyzr:
		pipe = 1e12
		for i in range(len(xyzr)):
			for j in range(len(chain)):
				l = R(xyzr[i],chain[j])
				if l < pipe:
					pipe = l
					p = i
		ans += pipe
		chain.append(xyzr.pop(p))
	print ans

### FIXED CODE ###

inf = 1 << 28
def calc(xyzr1,xyzr2):
    x1,y1,z1,r1 = xyzr1
    x2,y2,z2,r2 = xyzr2
    d = ((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**0.5
    return max(0, d-r1-r2)
    
while 1:
    n = int(raw_input())
    if n == 0: break
    xyzr = [map(float,raw_input().split()) for i in xrange(n)]
    
    cost = [[0]*n for i in xrange(n)]
    for i in xrange(n):
        for j in xrange(n):
            cost[i][j] = cost[j][i] = calc(xyzr[i],xyzr[j])
    
    mincost = [inf]*n
    used = [False]*n
    mincost[0] = 0
    ans = 0
    while 1:
        v = -1
        for u in xrange(n):
            if not used[u] and (v == -1 or mincost[u] < mincost[v]): v = u
        if v == -1: break
        used[v] = True
        ans += mincost[v]
        for u in xrange(n):
            mincost[u] = min(mincost[u], cost[v][u])
    
    print "%.3f"%ans
def f(S,L):
  if not L:
    return True
  if L >= 7:
    if S[-7:] == "dreamer":
      return f(S[:-7],L-7)
  if L >= 6:
    if S[-6:] == "eraser":
      return f(S[:-6],L-6)
  if L >= 5:
    if S[-5:] == "dream" or S[-5:] == "erase":
      return f(S[:-5],L-5)
  return False

s = input()
if f(s, len(s)):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S = input()
L = len(S)

while L:
  f = True
  if L >= 7:
    if S[L-7:L] == "dreamer":
      L -= 7
      f = False
  if L >= 6:
    if S[L-6:L] == "eraser":
      L -= 6
      f = False
  if L >= 5:
    if S[L-5:L] == "dream" or S[L-5:L] == "erase":
      L -= 5
      f = False
  if f:
    break

if L:
  print("NO")
else:
  print("YES")
def gcd(a, b):
    while b:
        a, b = b, a % b
    return b

ans = 1
for _ in range(int(input())):
    t = int(input())
    ans = ans * t // gcd(ans, t)
print(ans)

### FIXED CODE ###

import fractions
import functools
lcm=lambda x,y:x*y//fractions.gcd(x,y)
print(functools.reduce(lcm,[int(input())for _ in[0]*int(input())]))
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Ds = list(mapint())

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        aNS += Ds[i]*Ds[j]

print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Ds = list(mapint())

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += Ds[i]*Ds[j]

print(ans)
n = int(input())
s = []

for num in range(2, n//2+1):
    a = num
    b = n - num
    a_s = sum(list(map(int, str(a))))
    b_s = sum(list(map(int, str(b))))
    c = a_s + b_s
    s.append(c)

print(min(s))


### FIXED CODE ###

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

for num in range(1, n//2+1):
    a = num
    b = n - num
    a_s = sum(list(map(int, str(a))))
    b_s = sum(list(map(int, str(b))))
    c = a_s + b_s
    s.append(c)

print(min(s))
W, H, x, y, r = [int(x) for x in input().split()]
if (0 <= x-r <= W) and (0 <= x+r <= w):
    if(0 <= y-r <= H) and (0 <= y+r <= H):
        print("Yes")
else:
    print("No")

### FIXED CODE ###

W, H, x, y, r = [int(x) for x in input().split()]
if (0 <= x-r <= W) and (0 <= x+r <= W):
    if(0 <= y-r <= H) and (0 <= y+r <= H):
        print("Yes")
    else:
        print("No")
else:
    print("No")
s1 = raw_input()
s2 = raw_input()
s2 = s2.split(" ")
f = 0
for a,b in enumerate(s2):
    if str(s2[int(b)-1]) == str(a+1):
        f = f+1
print f/2

### FIXED CODE ###

s1 = input()
s2 = input()
s2 = s2.split(" ")
f = 0
for a,b in enumerate(s2):
    if str(s2[int(b)-1]) == str(a+1):
        f = f+1
print (int(f/2))
_, *a = map(int, open(0).read().split())
for b in a:z ^= b
print("YNeos"[z>0])

### FIXED CODE ###

_, *a = map(int, open(0).read().split());z = 0
for b in a:z ^= b
print("YNeos"[z>0::2])
N=int(input())
V=[int,input().split()]
C=[int,input().split()]
ans=0
for i in range(N):
  if V[i]-C[i] >0:
    ans+=V[i]-C[i]
print(ans)

### FIXED CODE ###

N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
for i in range(N):
  if V[i]-C[i] >0:
    ans+=V[i]-C[i]
print(ans)
n=int(input())
for i in range(n):
    t,x,y=map(int,input().split())
    if x+y>t or (x+y+t)%2:
      print("NO")
      exit()
print("YES")


### FIXED CODE ###

a,b=map(int,input().split())
print("Even" if a*b%2==0 else "Odd")
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))


### FIXED CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in a:
	r+=i*(i-1)//2
print(r)

### FIXED CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)
import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]
count = {}


def bfs(x, y, p, q):
    if A[x][y] == 1:
        return
    else:
        A[x][y] = 1
        count[p * H + q] = count.get(p * H + q, {})
        count[p * H + q]['#'] = count[p * H + q].get('#', 0)
        count[p * H + q]['.'] = count[p * H + q].get('.', 0)
        count[p * H + q][S[x][y]] += 1
        dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W:
                if S[x][y] != S[nx][ny] and A[nx][ny] == 0:
                    bfs(nx, ny, p, q)


for i, j in itertools.product(range(H), range(W)):
    bfs(i, j, i, j)
ans = 0
for i in count:
    ans += count[i]['#'] * count[i]['.']
print(ans)


### FIXED CODE ###

import itertools
H, W = [int(_) for _ in input().split()]
S = [input() for _ in range(H)]
A = [[0 for _ in range(W)] for _ in range(H)]


def dfs(p, q):
    if A[p][q] == 1:
        return 0
    count = {'#': 0, '.': 0}
    stack = [[p, q]]
    while stack:
        x, y = stack.pop()
        if A[x][y] != 1:
            count[S[x][y]] += 1
            A[x][y] = 1
            dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and S[x][y] != S[nx][ny]:
                    stack += [[nx, ny]]
    return count['#'] * count['.']


print(sum([dfs(i, j) for i, j in itertools.product(range(H), range(W))]))
a = map(int,input().split())
Min = min(a)
Max = max(a)
Mid = sum(a) - Max - Min

ans = Mid-Min + Max-Mid
print(ans)

### FIXED CODE ###

a = list(map(int,input().split()))
Min = min(a)
Max = max(a)
Mid = sum(a) - Max - Min
 
ans = Mid-Min + Max-Mid
print(ans)
s = input()

for i in range(len(S)):
  if len(list(set(s))) >= 3:
    print("No")
  else:
    s = list(set(s))
    if count(s[0]) == count(s[1]):
      print("Yes")
   	else:
      print("No")

### FIXED CODE ###

s = input()
s_s = list(set(s))

if len(s_s) == 2:
  if s.count(s_s[0]) == s.count(s_s[1]):
    print("Yes")
else:
    print('No')
N = int(input())
A = list(map(int, input().split()))
if sum(A)>=H:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

H,N = map(int,input().split())
A = list(map(int, input().split()))
if sum(A)>=H:
    print("Yes")
else:
    print("No")
#coding:utf-8
n=[int(i) for i in input().split()]
if(n[1]-n[0]<=2*n[2]):
  for i in range(n[0],n[1]+1):
    print(i)
else:
  for j in range(n[0],n[0]+n[2]+1):
    print(j)
  for k in range(n[1]-n[2]+1,n[1]+1):
    print(k)


### FIXED CODE ###

#coding utf-8
s=input()
s1=[s[0],s[1],s[2]]
s1.sort()
s1=s1[0]+s1[1]+s1[2]
if(s1!='abc'):
  print("No")
else:
  print("Yes")
def start(l):
    for i in range(1, l-1):
        if S_list[i] == "A":
            return i + 1


def finish(l):
    for i in range(1, l-1):
        if S_list[l - i] == "Z":
            return l - i + 1


S_list = list(input())
l = len(S_list)
print(finish(l) - start(l) + 1)

### FIXED CODE ###

S_list = list(input())
l = len(S_list)
for i in range(l):
    if S_list[i] == "A":
        start = i
        break
for i in range(l):
    if S_list[i] == "Z":
        finish = i


print(finish - start + 1)
a,b,c = map(int(input().split()))
if (a <= c <= b) or (b <= c <= a):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a,b,c = map(int,(input().split()))
if (a <= c <= b) or (b <= c <= a):
    print('Yes')
else:
    print('No')
n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
max = 0
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
n, q = list(map(int, input().split()))
childs = [set() for _ in range(n)]
nodes = [0 for _ in range(n)]
for _ in range(n - 1):
    line = input().split()
    a, b = int(line[0]), int(line[1])
    childs[a - 1].add(b - 1)


def add(i, k):
    global childs
    nodes[i] += k
    for j in childs[i]:
        add(j, k)


for _ in range(q):
    line = input().split()
    i, k = int(line[0]), int(line[1])
    add(i - 1, k)

print(' '.join(map(str, nodes)))

### FIXED CODE ###

n, q = map(int, input().split())
parents = [set() for _ in range(n)]
nodes = [0 for _ in range(n)]

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

for _ in range(q):
    i, k = map(int, input().split())
    nodes[i - 1] += k

for i, p in enumerate(parents):
    nodes[i] += sum([nodes[j] for j in p])

print(*nodes)
n,k=map(int,input().split())
l=sorted(int(input().split()) ,reverse=True)
print(sum(l[:k]))

### FIXED CODE ###

n,k=map(int,input().split())
l=sorted(map(int,input().split()) ,reverse=True)
print(sum(l[:k]))
s = open(0).read()
def t(c): return eval(s.replace("\n",c))
print([["LESS","GREATER"][t(">")], "EQUAL"][t("==")])

### FIXED CODE ###

a, b = map(int, open(0))
print([["LESS","GREATER"][a>b], "EQUAL"][a==b])
a = int(input())
b = int(input())
 
if a >= 13:
  print(b)
elif a >= 6 and a <= 12:
  print(int(b/2))
else:
  print(0)

### FIXED CODE ###

a,b = map(int, input().split())
 
ans=0
if a <= 5:
	ans = 0
elif a >= 6 and a<=12:
	ans = b/2
else:
	ans = b
 
print(int(ans))
import numpy as np


l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

lr = np.arange(l, r+1)
lr = np.reshape(lr, (1, len(lr)))
lr_t = lr.T
mod = (lr*lr_t) % 2019
mod = np.triu(mod, k=1)
mod = mod[np.triu_indices_from(mod, k=1)]
print(mod.min())


### FIXED CODE ###

l, r = map(int, input().split())
if l <= 2019 <= r:
    print(0)
    exit()
elif r*(r-1) <= 2019:
    print(l*(l+1))
    exit()

a = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        a = min(a, i*j%2019)
        if a == 0:
            print(0)
            exit()

print(a)
str = input()
str_len = len(str)
h_flag = 0
for cat_i in range(str_len):
  if h_flag == 0 & str[cat_i] == 'h':
    h_flag = 1
  elif h_flag == 1 & str[cat_i] == 'i':
    h_flag = 0
  else:
    print('No')
    break;
    
  if cat_i == (str_len - 1):
    print('Yes')


### FIXED CODE ###

str = input()
str_len = len(str)
h_flag = 0
for cat_i in range(str_len):
  if str_len % 2 == 1:
    print('No')
    break
  
  if h_flag == 0 and str[cat_i] == 'h':
    h_flag = 1
  elif h_flag == 1 and str[cat_i] == 'i':
    h_flag = 0
  else:
    print('No')
    break
    
  if cat_i == (str_len - 1):
    print('Yes')
s = input().rstrip()
n = len(s)
res = 0
for i in range(2**(n - 1)):
    bs = bin(i)[2:].rjust(n - 1, '0')
    ss = s[0]
    for j, b in enumerate(bs, 1):
        if b == '1':
            ss += '+'
        ss += s[j]
    res += eval(ss)
print(res)

### FIXED CODE ###

s = input().rstrip()
n = len(s)
res = 0
for i in range(2**(n - 1)):
    bs = bin(i)[2:].rjust(n - 1, '0')
    ss = s[0]
    for b, c in zip(bs, s[1:]):
        if b == '1':
            ss += '+'
        ss += c
    res += eval(ss)
print(res)
import collections
N = int(input())
A = list(map(int , input().split()))
a = collections.Counter(A)
S = len(a)
k = 0
for j in range (S):
    b = a.most_common()[j][1]
    if b > 1:
        k += b * (b-1)/2
    

for i in range(N):
    s = A[i]
    p = a[s]
    print(int(k - q)    


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int , input().split()))
a = collections.Counter(A)
k = 0
def comb(n):
    return n * (n - 1) // 2
for j in a.values():
    k += comb(j)
    
for i in range(N):
    s = A[i]
    p = a[s]
    print(int(k - p + 1))
A, B = map(int, input().split())
input_list = input().split( )

for i in (range(len(input_list))):
  input_list[i] = int(input_list)

input_sum = sum(input_list)

if(A <= input_sum):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

A, B = map(int, input().split())
input_list = input().split( )

for i in (range(len(input_list))):
  input_list[i] = int(input_list[i])

input_sum = sum(input_list)

if(A <= input_sum):
  print("Yes")
else:
  print("No")
c = a*b
if c%2 ==0:
  print('Even')
else
  print('Odd')

### FIXED CODE ###

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

if((a*b)%2 == 0):
	print('Even')
else:
	print('Odd')
s=input()
pos=0
cnt=0
flag=False
check='keyence'
for i in range(len(s)):
  if s[i]==check[pos]:
    pos+=1
    flag=True
  else:
    if flag==True:
      cnt+=1
      flag=False
if pos==7 and flag<=1ju:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

s=input()
flag=1
if s=='keyence':
  flag=0
for i in range(len(s)):
  for j in range(1,len(s)-i+1):
    if (s[:i]+s[i+j:])=='keyence':
      flag*=0
if flag==0:
  print('YES')
else:
  print('NO')
n,k = map(int, input().split())
a = list(map(int, input().split()))

#############

mod = 10**9 + 7
max = 10*5+10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( n<0 | k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

#############

a = sorted(a)

mul = [0]* n
mul[k-1] = 1
for i in range(k, n):
    mul[i] = com(i, k-1)

ans = 0
for i in range(n):
    ans += (a[i] * mul[i]) - (a[i] * mul[ -1*(i+1)])
    ans = ans % mod

print(ans)

### FIXED CODE ###

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

#############

mod = 10**9 + 7
max = 10**5+10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( n<0 | k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

#############

a = sorted(a)

mul = [0]* n
mul[k-1] = 1
for i in range(k, n):
    mul[i] = com(i, k-1)

ans = 0
for i in range(n):
    ans += (a[i] * mul[i]) - (a[i] * mul[ -1*(i+1)]) % mod
    ans = ans % mod

print(ans)
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
kk=k
mx=0
while i<n and a[i]<=k:
    k-=a[i]
    i+=1
    mx+=1
j=0
while j<m and b[j]<=k:
    k-=b[j]
    j+=1
    mx+=1
cou=mx
while i>=0 and j<m:
    k+=a[i]
    i-=1
    cou-=1
    while j<m and b[j]<=k:
        j+=1
        k-=b[j]
        cou+=1
    mx=max(cou,mx)
print(mx)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
mx=0
lol=0
while i<n and a[i]<=k:
    k-=a[i]
    i+=1
    mx+=1
    lol=1
j=0
while j<m and b[j]<=k:
    k-=b[j]
    j+=1
    mx+=1
cou=mx

i-=1
while i>=0 and j<m:
    k+=a[i]
    i-=1
    cou-=1
    while j<m and b[j]<=k:
        k-=b[j]
        cou+=1
        j+=1
    mx=max(cou,mx)
print(mx)
A,B,K = [int(i) for i in input().split()]
if (A>B):
    A,B=B,A
f=[]
j=A
for i in range(1,A):
    if (i>=j):
        break
    if (A % i == 0 and B % i == 0):
        j=int(A/i)
        f.append(i)
        if (B % j == 0):
            f.append(j)
f.sort(reverse=True)
if A==1:
    print(1)
else:
    print(f[K-1])




### FIXED CODE ###

A,B,K = [int(i) for i in input().split()]
if (A>B):
    A,B=B,A
k=0
for i in reversed(range(1,A+1)):
    if (A % i == 0 and B % i == 0):
        k+=1
    if (k==K):
        print(i)
        break
n,m = map(int, input().split())
sc = [list(map(int,input().split())) for _ in range(m)]

ans = [-1] * n
for s,c in sc:
    if(ans[s-1] != -1):
        if(ans[s-1] != c):
            print(-1)
            exit()

    if(n>1)&(s==1)&(c==0):
        print(-1)
        exit(9)
    ans[s-1] = c

ans_num = 0
for i,num in enumerate(ans[::-1]):
    if(num == -1):
        if(i==n-1):
            ans_num += 1*10**(i)
        continue

    ans_num += num * 10**(i)

print(ans_num)

### FIXED CODE ###

n,m = map(int, input().split())
sc = [list(map(int,input().split())) for _ in range(m)]

ans = [-1] * n
for s,c in sc:
    if(ans[s-1] != -1):
        if(ans[s-1] != c):
            print(-1)
            exit()

    if(n>1)&(s==1)&(c==0):
        print(-1)
        exit()
    ans[s-1] = c

ans_num = 0
for i,num in enumerate(ans[::-1]):
    if(num == -1):
        if(i==n-1)&(n!=1):
            ans_num += 1*10**(i)
        continue

    ans_num += num * 10**(i)

print(ans_num)
C = input()

ary = "abcdefghijklmnopqrstuvwxyz".split("")

print(ary[ary.index(C) + 1])

### FIXED CODE ###

C = input()
 
ary = "a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z".split(",")
 
print(ary[ary.index(C) + 1])
n =input()
fn = 0
for i in range(len(n)):
  fn += n[i]
if int(n) % fn == 0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

n =input()
fn = 0
for i in range(len(n)):
  fn += int(n[i])
if int(n) % fn == 0:
  print('Yes')
else:
  print('No')
def bubbleSort(A, N):
    c = 0
    flag = 1   # ????????£??\????´?????????¨??????
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                c += 1
                flag = 1
    print " ".join(map(str, A))
    print c


N = int(raw_input())
L = map(int, raw_input().split())

bubbleSort(L, N)

### FIXED CODE ###

def bubble_sort(A, N):
    flag = True
    i, c = 0, 0
    while flag:
        flag = False
        for j in range(1, N-i):
              if A[j] < A[j-1]:
                  A[j],  A[j-1] = A[j-1], A[j]
                  flag = True
                  c += 1
        i += 1
    
    print " ".join(map(str, A))
    print c


N = int(raw_input())
A = map(int, raw_input().split())
 
bubble_sort(A, N)