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

A, B = map(int, input().split())
ans = A * B
for i in range(min(A, B) * 2,(A * B) + 1):
    if i % A == 0 and i % B == 0:
        ans = i
        break

print(ans)

### FIXED CODE ###

# 約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

A, B = map(int, input().split())
ptn = list(reversed(make_divisors(A * B)))

for i in range(0, len(ptn), 2):
    if ptn[i] % A == 0 and ptn[i] % B == 0:
        print(ptn[i])
        exit()
print(A * B)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
n = 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if i< j< k:
                if L[i-1]< L[j-1] + L[k-1] and L[j-1]< L[i-1] + L[k-1] and L[k-1]< L[j-1] + L[i-1]:
                    n +=1
print(n)

### FIXED CODE ###

import bisect
 
n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
 
for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)#二分探索,abをlの中のどこに挿入するか
        count += index_c - j -1

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

N = int(input())
A = [int(i) for i in input().split()]

if N % 2:
    if A.count(0) != 1:
        flg = 0
    else:
        if all(A.count(i) == 2 for i in range(2, N, 2)):
            if all(j % 2 == 0 for j in A):
                flg = 1
            else:
                flg = 0
        else:
            flg = 0
else:
    if all(A.count(i) == 2 for i in range(1, N, 2)):
        if all(j % 2 for j in A):
            flg = 1
        else:
            flg = 0
    else:
        flg = 0

print(2**(N//2) if flg else 0)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
c = Counter(A)

flg = 0
if N % 2:
    if c[0] != 1:
        flg = 1
    else:
        for i in range(2, N, 2):
            if c[i] != 2:
                flg = 1
                break
else:
    for i in range(1, N, 2):
        if c[i] != 2:
            flg = 1
            break

if flg:
    ans = 0
else:
    ans = 2 ** (N//2) % (10**9+7)

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

a, b = map(int, input().split())
l = [x for x in range(a, b+1)]
result = 0
for x in l:
    result = result ^ x
    
print(result)

### FIXED CODE ###

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

def f(n):
    # XOR([o to n])
    if (n+1)%2 == 0: # 総数が偶数
        if ((n+1)//2)%2 == 0: # ペアが偶数
            return 0
        else: # ペアが奇数
            return 1
    else: # 総数が奇数
        if ((n+1)//2)%2 == 0: # 2つ1組のペアが偶数
            return n
        else: # ペアが奇数
            return n+1
        
        
result = f(a-1) ^ f(b)
    
print(result)
### BUGGY CODE ###

import numpy as np

H,W,D = map(int,input().split())
N = H*W

# 各数値の書かれている位置, 1-indexed
X = np.zeros(N+1,dtype=np.int64)
Y = np.zeros(N+1,dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    X[int(n)] = x
    Y[int(n)] = y

#n%Dからnへ移動するために必要な魔力
MAGIC = np.zeros(N+1,dtype=np.int64)

for d in range(1,D+1):
  DX = np.abs(np.diff(X[d::D]))
  DY = np.abs(np.diff(Y[d::D]))
  MAGIC[d+D::D] = (DX + DY).cumsum()


Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  print(MAGIC[r] - MAGIC[l])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

H,W,D = map(int,input().split())
N = H*W
ND = N//D

# 各数値の書かれている位置, 1-indexed
X = np.zeros((D,ND+1),dtype=np.int64)
Y = np.zeros((D,ND+1),dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    n = int(n)
    q,r = n//D,n%D
    X[r,q] = x
    Y[r,q] = y

# 0D+d から nD+d への移動コスト
MAGIC = np.zeros_like(X)
MAGIC[:,1:] = (np.abs(np.diff(X,axis = 1)) + np.abs(np.diff(Y,axis = 1))).cumsum(axis = 1)

Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  d = l%D
  print(MAGIC[d,r//D] - MAGIC[d,l//D])
### BUGGY CODE ###

#B問題
R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, 3001):
    for g in range(0, 3001 - r):
        if (N - R*r - G*g) % B == 0 and (N - R*r - G*g)/B >=0:
            ans += 1
print(ans)            

### FIXED CODE ###

#B問題
import math
R, G, B, N = map(int, input().split())

ans = 0
if R == G == B == 1:
    print (int((N+2)*(N+1)/2))
else:
    for r in range(0, N // R + 1):
        for g in range(0, N // G + 1):
            if (N - R*r - G*g) % B == 0 and (N - R*r - G*g)/B >=0:
                ans += 1
    print(ans)
### BUGGY CODE ###

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

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		iturn2=iturn%2
		if (t[1]=='1' and iturn2==0) or (t[1]=='2' and iturn2==1):
#			s=t[2]+s
			s='{}{}'.format(t[2],s)
		else:
#			s=s+t[2]
			s='{}{}'.format(s,t[2])

if iturn%2==1:
	s=s[::-1]
print (s)

### FIXED CODE ###

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

top=""
btm=""

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		iturn2=iturn%2
		if (t[1]=='1' and iturn2==0) or (t[1]=='2' and iturn2==1):
#			s=t[2]+s
#			s='{}{}'.format(t[2],s)
			top=t[2]+top
		else:
#			s=s+t[2]
#			s='{}{}'.format(s,t[2])
			btm=btm+t[2]

if iturn%2==0:
	s=top+s+btm
else:
	s=btm[::-1]+s[::-1]+top[::-1]
print (s)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    for a, b in arr:
        f = True
        for i in range(32):
            if k & (1<<i) == 0 and a & (1<<i) != 0:
                f = False
                break
        if f:
            ans += b
    for i in range(32):
        p = 1<<i
        tmp = 0
        if p & k == 0:
            continue
        for a, b in arr:
            if a <= k and a&p == 0:
                f = True
                for j in range(i+1, 32):
                    if k & (1<<j) == 0 and a & (1<<j) != 0:
                        f = False
                        break
                if f:
                    tmp += b
        if ans < tmp:
            ans = tmp
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    for a, b in arr:
        f = True
        for i in range(32):
            if k & (1<<i) == 0 and a & (1<<i) != 0:
                f = False
                break
        if f:
            ans += b
    for i in range(32):
        p = 1<<i
        tmp = 0
        if p & k == 0:
            continue
        for a, b in arr:
            if a <= k and a&p == 0:
                f = True
                for j in range(i+1, 32):
                    if k & (1<<j) == 0 and a & (1<<j) != 0:
                        f = False
                        break
                if f:
                    tmp += b
        if ans < tmp:
            ans = tmp
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
from collections import Counter
x = 1
mod = 2019
total = 0
ans = 0
cnt = Counter()
for i in range(len(s)-1,-1,-1):
    cnt[total] += 1
    total += int(s[i])*x
    total %= mod
    ans += cnt[total]
    x *= 10%2019
print(ans)

### FIXED CODE ###

s = input()
from collections import Counter
x = 1
mod = 2019
total = 0
ans = 0
cnt = Counter()
for i in range(len(s)-1,-1,-1):
    cnt[total] += 1
    total = total + int(s[i])*x
    total %= mod
    ans += cnt[total]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
for i in range(n):
	s[i].sort()
count=0
for i in range(n):
	for j in range(n):
		if s[i]==s[j]:
			count+=1
print(int((count-n)/2))

### FIXED CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
dic={}
t=[0]*n
for i in range(n):
	s[i].sort()
	t[i]=str(s[i])
for i in range(n):
	if t[i] in dic:
		dic[t[i]]+=1
	else:
		dic[t[i]]=1
counts=list(dic.values())
count=0
for i in range(len(counts)):
	count+=(counts[i])*(counts[i]-1)/2
print(int(count))
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
x = 1
for i in lst:
    x*=i
if(x>1e18):
    print(-1)
else:
    print(x)

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
zero = False
fl = False
x = 1
for i in lst:
    if(i==0):
        zero = True
        break
    if not fl:
        x*=i
    if(x>1e18):
        fl = True
if zero:
    print(0)
elif fl:
    print(-1)
else:
    print(x)
### BUGGY CODE ###

n,k,q=list(map(int,input().split()))
a=[int(input()) for i in range(q)]
s=[k]*n
for i in a:
  s=list(map(lambda x:x-1,s))
  s[i-1]+=1
for j in range(n):
  if s[j]>0:print('Yes')
  else:print('No')

### FIXED CODE ###

n,k,q=list(map(int,input().split()))
s=[k]*n
for i in range(q):
  a=int(input())
  s[a-1]+=1
s=list(map(lambda x:x-q,s))
t=list(map(lambda x:print('Yes') if x>0 else print('No'),s))
### BUGGY CODE ###

# 初期入力
N= int(input())
S =input()


#
R_index=[]
G_index=[]
B_index=[]
for i,v in enumerate(S):
    if v =="R":
        R_index.append(i)
    if v =="G":
        G_index.append(i)
    if v =="B":
        B_index.append(i)

count_3jurupe =0
for i in R_index:
    for j in G_index:
        for k in B_index:
            if abs(i-j) == abs(j-k) or abs(i-k) == abs(j-k) or abs(i-j) == abs(i-k):
                count_3jurupe +=1
                #print(i,j,k,end=" ,")

#選んだ文字が３つとも違う＝RGB（全体）
a = len(R_index) * len(G_index) * len(B_index) 

kotae =a -count_3jurupe
#print()
print(kotae)

### FIXED CODE ###

# 初期入力
N= int(input())
S =input()


#
R_index=[]
G_index=[]
B_index=[]
for i,v in enumerate(S):
    if v =="R":
        R_index.append(i)
    if v =="G":
        G_index.append(i)
    if v =="B":
        B_index.append(i)

# 例　R_index各要素から等距離離れたところに左にG、右にBがあればOK
R_B =[]
B_G =[]
count_ij_jk_onaji =0
for r in R_index:
    for g in G_index:
        if 0<=g-(r-g) and g-(r-g)<N  :
            #if S[g-(r-g)]=="B" and r<g:
            if S[g-(r-g)]=="B" :
                count_ij_jk_onaji +=1
               # print(r,g,g-(r-g),"B")
for b in B_index:
    for r in R_index:
        if 0<=r-(b-r) and r-(b-r)<N :
            #if S[r-(b-r)] == "G" and b<r:
            if S[r-(b-r)] == "G" :
                count_ij_jk_onaji +=1
                #print(r,b,r-(b-r),"G")
for g in G_index:
    for b in B_index:
        if 0<=b-(g-b) and b-(g-b)<N :
            #if S[b-(g-b)] =="R" and g<b:
            if S[b-(g-b)] =="R":
                count_ij_jk_onaji +=1
                #print(b,g,b-(g-b),"R")

            
#3つとも異なる文字=all
kotae_all = len(R_index) * len(G_index) * len(B_index) 
print(kotae_all -count_ij_jk_onaji)
### BUGGY CODE ###

n = int(input())
sum = list(map(int,input().split()))
x = 1

for i in range(n):
    x *= sum[i]

if x>1000000000000000000:
    print(-1)
    
else:
    print(x)

### FIXED CODE ###

N=int(input())
number=list(map(int,input().split()))
ans=1
if 0 in number:
    print(0)
    exit(0)
    
for i in range(N):
    ans *= number[i]
    if ans>1000000000000000000:
        print(-1)
        exit(0)
print(ans)
### BUGGY CODE ###

from functools import reduce

n = int(input())
l = list(map(int, input().split()))
ans = reduce(lambda x, y: x * y, l)

if ans > 10**18:
    print (-1)
else:
    print(ans)

### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from sys import stdin
input = stdin.readline



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

ans = 1
ng = False
for i in range(n):
    if l[i] == 0:
        print(0)
        quit()
    if not ng:
        ans *= l[i]
        if ans > 10**18:
            ng = True

if ng:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import heapq
n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heapq.heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] != -1:
            continue
        dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heapq.heappop(pqs[i])
    ans += val
pqs = sum(pqs, [])
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

### FIXED CODE ###

import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()[:-1]

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] == -1:
            dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heappop(pqs[i])
    ans += val
pqs = [flatten for inner in pqs for flatten in inner] 
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)
### BUGGY CODE ###


H, W = map(int, input().split())
edges = [[None for i in range(W)] for i in range(H)]

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

from collections import deque

def dfs(i, j):
  colors = [[["white"] for i in range(W)] for j in range(H)]
  queue = deque()
  queue.append((i, j))
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  result = -1
  while queue:
    i, j = map(int, queue.popleft())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] != "black":
        d = min(distance[i][j] + 1, distance[x][y])
        distance[x][y] = d
        result = max(result, d)
        queue.append((x, y))
  
  return result


import itertools
ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "#": 
      continue

    ans = max(ans, dfs(i, j))

print(ans)

### FIXED CODE ###


H, W = map(int, input().split())
edges = [[None for i in range(W)] for i in range(H)]

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

from collections import deque

def dfs(i, j):
  colors = [["white" for i in range(W)] for j in range(H)]
  queue = deque()
  queue.append((i, j))
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  result = -1
  while queue:
    i, j = map(int, queue.popleft())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] == "white":
        colors[x][y] = "gray"
        d = min(distance[i][j] + 1, distance[x][y])
        distance[x][y] = d
        result = max(result, d)
        queue.append((x, y))
  return result


ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "#": 
      continue
    
    ans = max(ans, dfs(i, j))

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

N=int(input())
S=[input() for i in range(N)]
ans=0
for k in range(N):
    flag=1
    for i in range(N):
        for j in range(N):
            if S[(i+k)%N][j]!=S[(j+k)%N][i]:
                flag=0
                break
        if flag==0:
            break
    if flag==1:
        ans+=N
print(ans)


### FIXED CODE ###

N=int(input())
S=[list(input()) for i in range(N)]
def issym(IL):
    for i in range(N):
        for j in range(i+1,N):
            if IL[i][j]!=IL[j][i]:
                return False
    return True
def changelist(A,B):
    T=[["" for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            T[i][j]=S[(i+A)%N][(j+B)%N]
    return T
ans=0
for i in range(N):
    L=changelist(i,0)
    if issym(L):
        ans+=N
print(ans)
### BUGGY CODE ###

K = int(input())

mm = 7
ans = 0
for i in range(10**6):
    ans += 1
    if mm%K==0:
        print(ans)
        break
    mm = mm*10 +7

else:
    print(-1)

### FIXED CODE ###

K = int(input())

mm = 7
cnt = 1
for i in range(10**7):
    if mm%K==0:
        print(cnt)
        break
    else:
        mm = mm*10+7
        mm %= K
        cnt += 1
else:
    print(-1)
### BUGGY CODE ###

import math

def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    return True


def find_all_prime(num):
    prime_list = [2]
    for i in range(3, num, 2):
        if isPrime(i):
            prime_list.append(i)

    return prime_list


if __name__ == "__main__":
    N = int(input())
    if isPrime(N):
        print(1)
    else:      
        prime_list = find_all_prime(int(1.25*10**6))
        count = 0  
        for i in prime_list:
            j = 1
            while N > 1:
                if N // i**j == 0:
                    break
                if N % i**j == 0:
                    N = N // i**j
                    count += 1
                j +=1
        
        print(count)

### FIXED CODE ###

def factorization(n):
    factorization_list = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp //= i
            factorization_list.append([i, count])

    if temp != 1:
        factorization_list.append([temp, 1])

    if factorization_list==[]:
        factorization_list.append([n, 1])

    return factorization_list


if __name__ == "__main__":
    N = int(input())

    if N == 1:
        print(0)

    else:
        factorization_list = factorization(N)
        count = 0
        for factor in factorization_list:
            e = factor[1]
            i = 1
            while True:
                e -= i
                i += 1
                count += 1
                if e < i:
                    break
        print(count)
### BUGGY CODE ###

# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 品物を増やすごとに、配列を更新して使いまわす。
# 重さは1~W 添え字は0<=w<=W<W+1 dpリストの長さはW+1
# ループは1~N回回す　添え字は0<=i<=N-1<N
# 添え字i, i+1回目のループでのdp[j]の求め方 i+1番目の品物を選ぶかどうか？
# j-w(i)<0のとき、重量オーバーで選べない。dp[j]は変わらない
# j-w(i)>=0のとき、dp[j]=max(dp[j], dp[j-w(i)]+v(i))
# 配列は逆側から更新していく
# 解答はN回ループした後のdp[W+1]=dp[-1] 最後の値

# 入力
# tableは二次元配列　table[i][0]でi番目の品物の重さ、table[i][1]で価値
N, W = list(map(int, input().strip().split()))
table = []
for i in range(N):
    table.append(list(map(int, input().strip().split())))

# 初期化
dp = [0] * (W + 1)

# dpテーブル
for i in range(N):
    for j in range(W, -1, -1):
        if j - table[i][0] >= 0:
            dp[j] = max(dp[j], dp[j - table[i][0]] + table[i][1])

print(dp[-1])

### FIXED CODE ###

# dp[w] i番目までの品物で、重さがw以下になるよう選んだときの価値の最大値。
# 参考 https://qiita.com/drken/items/68b8503ad4ffb469624c

import numpy as np

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = np.zeros(W + 1, dtype='int64')

# dpテーブル
for i in range(N):
    w, v = map(int, input().strip().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

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

from math import factorial

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

ans = 0
for i in range(1, n + 1, 1):
    if i == a or i == b:
        continue

    ans += factorial(n) // (factorial(n - i) * factorial(i))

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

### FIXED CODE ###

# input
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
al = (pow(2, n, mod) - 1)


# 参考：https://qiita.com/MyOden/items/b669bfbf6dbf83242bdf =>フェルマーの小定理を基に演算関数を用意
def fur(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * pow(q, mod - 2, mod) % mod


nca = fur(n, a)
ncb = fur(n, b)
ans = (al - nca - ncb) % mod

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

inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if cost[i] < min:
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())
	if n == 0:break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a, b, c, t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T, i) for i in range(m)]
	CS = [solve(C, i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int, raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]

### FIXED CODE ###

inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:	
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())
	if n == 0:break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a,b,c,t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T,i) for i in range(m)]
	CS = [solve(C,i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int,raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]
### BUGGY CODE ###

from math import factorial

n,k = map(int,input().split())
a = [int(i) for i in input().split()]

a.sort()
ans = 0
#print(a)
if k > 1:
    for i in range(k-1, n):
        for j in range(0, i - k + 2):
            ans += (a[i] - a[j]) * factorial(i - j - 1) // factorial(k - 2) // factorial(i - j - 1 - k + 2)
            #print(j, i, ' ', a[j],a[i], ' ', a[i] - a[j])

    ans %= pow(10, 9) + 7
    print(ans)
else:
    print(0)

### FIXED CODE ###

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = pow(10, 5)  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
mod = pow(10, 9) + 7

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
if k > 1:
    ans = 0
    for i in range(k-1, n):
        maxs = a[i]
        ncr = cmb(i, k-1)
        #print(maxs, ncr, maxs * ncr)
        ans += maxs * ncr
        ans %= mod
    for i in range(n-k+1):
        mins = a[i]
        ncr = cmb(n-i-1, k-1)
        #print(mins, ncr, mins * ncr)
        ans -= mins * ncr
        ans %= mod
    print(ans)
else:
    print(0)