Harryxun/stf_run huggingface dataset:
def equal_list(lst1, lst2):
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            break
    else:
        if not lst:
            return True
    return False


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

if a == [0]*N:
    print("Yes")
    exit()

if N % 3 == 0:
    n = N // 3
    sets = list(set(a))
    if len(sets) != 3:
        print("No")
        exit()

    for s in sets:
        if a.count(s) != n:
            print("No")
            exit()

    order = max(a).bit_length()

    for i in range(order):
        b = [sets[0] >> i & 1, sets[1] >> i & 1, sets[2] >> i & 1]
        if not equal_list(b, [0, 1, 1]):
            print("No")
            exit()

    print("Yes")

else:
    print("No")


### FIXED CODE ###

def equal_list(lst1, lst2):
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            break
    else:
        if not lst:
            return True
    return False


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

if a == [0]*N:
    print("Yes")
    exit()

if N % 3 == 0:
    n = N // 3
    sets = list(set(a))
    order = max(a).bit_length()
    if len(sets) == 3:
        for s in sets:
            if a.count(s) != n:
                print("No")
                exit()

        for i in range(order):
            b = [sets[0] >> i & 1, sets[1] >> i & 1, sets[2] >> i & 1]
            if b == [0, 0, 0]:
                continue
            if not equal_list(b, [0, 1, 1]):
                print("No")
                exit()
    elif len(sets) == 2:
        if a.count(sets[0]) == n:
            for i in range(order):
                b = [sets[0] >> i & 1, sets[1] >> i & 1]
                if b == [0, 0]:
                    continue
                if b != [0, 1]:
                    print("No")
                    exit()
        elif a.count(sets[1]) == n:
            for i in range(order):
                b = [sets[0] >> i & 1, sets[1] >> i & 1]
                if b == [0, 0]:
                    continue
                if b != [1, 0]:
                    print("No")
                    exit()
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()

    print("Yes")

else:
    print("No")
    exit()
import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


def find_n(x, y):
    moves = int((x+y)/3)
    for n in range(moves+1):
        if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
            return n, moves-n


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


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


def main():
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    x, y = map(int, input().split())

    if (x+y) % 3:
        print(0)
        sys.exit()

    n, m = find_n(x, y)

    ans = cmb(n+m, min([n, m]))

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import subprocess
import os
import time


import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# def find_n(x, y):
#     moves = int((x+y)/3)
#     for n in range(moves+1):
#         if n + (moves-n)*2 == x and n*2 + (moves-n) == y:
#             return n % mod, (moves-n) % mod


# def cmb(n, r):
#     return math.factorial(n) % mod // ((math.factorial(r) % mod) * (math.factorial(n-r) % mod))


def cmb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)

    return g1[n] * g2[r] * g2[n-r] % mod


def main():
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    x, y = map(int, input().split())

    if (x+y) % 3:
        print(0)
        sys.exit()

    # n, m = find_n(x, y)

    n = int(((x*2 - y) // 3))
    m = int(((y*2 - x) // 3))

    ans = cmb(n+m, n)

    print(ans)


if __name__ == '__main__':
    main()
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

Q = ii()
lr = li2(Q)
from collections import deque
que = deque()

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

prime = [0]*(10**5+1)
flag = [0]*(10**5+1)
prime[2] = 1

for i in range(3, 10**5+1, 2):
    if is_prime(i):
        prime[i] = 1

for i in range(3, 10**5+1, 2):
    if prime[i] and prime[(i+1)//2]:
        flag[i] = 1

ans = list(accumulate(flag))

for i in range(Q):
    print(ans[lr[i][1]]-ans[lr[i][0]-1])

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())

M = ii()

print(48-M)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

Mat = collections.namedtuple("Mat", "r c")

def mat_mul(ms):
    return Mat(ms[0].r, ms[-1].c)

def cost(m1, m2):
    return m1.r * m1.c * m2.c

def solve(n, ms):
    if n == 1: return 0

    dp = {}
    for i in range(n):
        dp[(i,i)] = 0

    for l in range(2, n+1):
        for i in range(n-l+1):
            cost_min = math.inf
            #cost_min = float("inf")
            for j in range(l-1):
                dbg("l, i, j: %d %d %d", l, i, j)
                m_lhs = mat_mul(ms[i:i+j+1])
                m_rhs = mat_mul(ms[i+j+1:i+l])
                dbg("m_lhs, m_rhs: %r %r", m_lhs, m_rhs)
                cost_lhs = dp[(i,i+j)]
                cost_rhs = dp[(i+j+1,i+l-1)]
                dbg("cost_lhs, cost_rhs: %d %d", cost_lhs, cost_rhs)
                cost_mul = cost(m_lhs, m_rhs)
                dbg("cost_mul: %d", cost_mul)
                cost_now = cost_mul + cost_lhs + cost_rhs
                dbg("cost_now: %d", cost_now)
                if cost_min > cost_now:
                    cost_min = cost_now
            dp[(i,i+l-1)] = cost_min

    dbg(dp)
    return dp[(0,n-1)]

def main():
    n = int(input())

    ms = []
    for _ in range(n):
        r,c = map(int, input().split())
        ms.append(Mat(r,c))

    print(solve(n, ms))

if __name__ == "__main__": main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

Mat = collections.namedtuple("Mat", "r c")

def mat_mul(ms):
    return Mat(ms[0].r, ms[-1].c)

def cost(m1, m2):
    return m1.r * m1.c * m2.c

def solve(n, ms):
    if n == 1: return 0

    dp = {}
    for i in range(n):
        dp[(i,i)] = 0

    for l in range(2, n+1):
        for i in range(n-l+1):
            #cost_min = math.inf
            cost_min = float("inf")
            for j in range(l-1):
                dbg("l, i, j: %d %d %d", l, i, j)
                m_lhs = mat_mul(ms[i:i+j+1])
                m_rhs = mat_mul(ms[i+j+1:i+l])
                dbg("m_lhs, m_rhs: %r %r", m_lhs, m_rhs)
                cost_lhs = dp[(i,i+j)]
                cost_rhs = dp[(i+j+1,i+l-1)]
                dbg("cost_lhs, cost_rhs: %d %d", cost_lhs, cost_rhs)
                cost_mul = cost(m_lhs, m_rhs)
                dbg("cost_mul: %d", cost_mul)
                cost_now = cost_mul + cost_lhs + cost_rhs
                dbg("cost_now: %d", cost_now)
                if cost_min > cost_now:
                    cost_min = cost_now
            dp[(i,i+l-1)] = cost_min

    dbg(dp)
    return dp[(0,n-1)]

def main():
    n = int(input())

    ms = []
    for _ in range(n):
        r,c = map(int, input().split())
        ms.append(Mat(r,c))

    print(solve(n, ms))

if __name__ == "__main__": main()
import math
n = int(input())
if n % 2 != 0:
    print(0)
    exit()
l = math.ceil(math.log(n, 5))
#print(l)
ans = 0
for i in range(1, l + 1):
    #print(pow(5, i), n // pow(5, i))
    ans += n // pow(5, i) // 2
print(ans)

### FIXED CODE ###

n = int(input())
if n % 2 == 1:
    print(0)
else:
    ans = 0
    for i in range(1, 26):
        if 5 ** i < n:
            ans += n // 2 // (5 ** i)
    print(ans)
n=int(input())
a = [input() for _ in range(n)]
nex=[]
k=1
for i in range(len(a)):
    nex.append(a[k-1])
    k=nex[-1]
    if nex[-1]==2:
        print(len(nex))
        break
    elif len(nex)>=n:print(-1)
    else:pass

### FIXED CODE ###

n=int(input())
a = [int(input()) for _ in range(n)]
nex=[]
k=1
for i in range(len(a)):
    nex.append(a[k-1])
    k=nex[-1]
    if nex[-1]==2:
        print(len(nex))
        break
    elif len(nex)>=n:print(-1)
    else:pass
def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

def lcm(a, b):
    return a / gcd(a, b) * b

n = int(input())
ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(t,ans)

print(int(ans))

### FIXED CODE ###

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

n = int(input())
ans = 1
for i in range(n):
    t = int(input())
    ans = lcm(ans, t)

print(int(ans))
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
count = 0
while((A%2==0).all()):
    A=A/2
    count+=1
print(count)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
count = 0
while((A%2==0).all()):
    A=A/2
    count+=1
print(count)
a,b=map(int,input())
if (a+b)%2==0:
  print (a+b)/2
else:
  print('IMPOSSIBLE')


### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2==0:
    print ((a+b)//2)
else:
    print('IMPOSSIBLE')
a, b = (int(i) for i in input().split())  
print (a+b)%24

### FIXED CODE ###

a,b = map(int, raw_input().split())
print (a+b)%24
num=int(input())
res=0
for i in range(num):
  t=input().split()
  if t[1]=='BTC':
    t[0]=int(t[0])*380000
  res+=int(t[0])
print(res)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(N):
    x, v = input().split()
    x = float(x)
    if v == "BTC":
        x *= 380000
    ans += x 
print(ans)
n=int(input())
x_=input()
px=x_.count("1")
if not px:
    print(0)
    for i in range(n-1):
        print(1)
    exit()

x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        dv=px-1
    else:
        tmp=x1+pow2[i]
        dv=px+1
    if dv==0:
        ans.append(0)
        continue
    cnt=1
    while tmp:
        tmp%=dv
        dv=bin(tmp).count("1")
        if not tmp:
            break
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)

### FIXED CODE ###

n=int(input())
x_=input()
px=x_.count("1")
if not px:
    for i in range(n):
        print(1)
    exit()
if px==1:
####[上から] i 桁目
    for i in range(n):
        if int(x_[i]):
            print(0)
        else:
            if i==n-1 or int(x_[-1])==1:###
                print(2)
            else:
                print(1)
    exit()
x=int(x_,2)

pow2=[1]

for i in range(n):
    tmp=pow2[-1]
    tmp*=2
    tmp%=px+1
    pow2.append(tmp)
pow22=[1]
for i in range(n):
    tmp=pow22[-1]
    tmp*=2
    tmp%=px-1
    pow22.append(tmp)
x1=x%(px+1)
x2=x%(px-1)
ans=[]
for i in range(n):
    tmp=0;dv=0
    if int(x_[-i-1]):
        tmp=x2-pow22[i]
        tmp%=(px-1)
        dv=px-1
    else:
        tmp=x1+pow2[i]
        tmp%=(px+1)
        dv=px+1
    
    cnt=1
    while tmp:
        
        dv=bin(tmp).count("1")
        if not dv or not tmp:
            break
        
        tmp%=dv
        cnt+=1
    ans.append(cnt)
for i in ans[::-1]:
    print(i)
n=int(input())
a=map(int,input().split())
ans=0
for i in range(0,2*n,2):
    ans+=a[i+1]
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(0,2*n,2):
    ans+=a[i]
print(ans)
b = input()
if b[i] == "A":
  b[i] = "T"
else if b[i] == "T":
  b[i] = "A"
else if b[i] == "C":
  b[i] = "G"
else if b[i] == "G":
  b[i] = "C"
print(b)

### FIXED CODE ###

b = input()
if b == "A":
  b = "T"
elif b == "T":
  b = "A"
elif b == "C":
  b = "G"
elif b == "G":
  b = "C"
print(b)
import numpy as np
N = int(input())
S = np.array([int(input()) for i in range(N)])
S = S.reshape(N, 1)

mat = np.zeros([2**N, N])
for i in range(2**N):
    for j in range(N):
        if (N * "0" + format(i, "b"))[-N+j] == "1":
            mat[i,j] = 1
score = np.dot(mat, S)
flg = score % 10 != 0 

print(int(np.max(score * flg)))


### FIXED CODE ###

N = int(input())
S = [int(input()) for i in range(N)]

ans = sum(S)
if ans % 10 == 0:
    d = [i for i in S if i % 10 != 0]
    if len(d):
        print(ans - min(d))
    else:
        print(0)
else:
    print(ans)
x=int(input())
string=input()
if x%2=1:
  print("No")
else:
  if string[:x/2]==string[x/2:]
  	print("Yes")
  else:
    print("No")
  

### FIXED CODE ###

x=int(input())
string=input()
if x%2==1:
  print("No")
else:
  if string[:x//2]==string[x//2:]:
  	print("Yes")
  else:
    print("No")
import math

A, B, N = tuple(map(int, input().split()))

m = 0
n = 1

def cal(x):
  return math.floor(A*x/B)-A*math.floor(x/B)

while n<N:
  c = B*(math.floor((n+1)/B)+1)-1
  n = min(N, c)
  m = max(cal(n), m)
  if (A*x)%B == 0:
    break
  
print(m)

### FIXED CODE ###

import math

A, B, N = tuple(map(int, input().split()))

m = 0
n = 1

def cal(x):
  return math.floor(A*x/B)-A*math.floor(x/B)

while n<N:
  c = B*(math.floor((n+1)/B)+1)-1
  n = min(N, c)
  m = max(cal(n), m)
  if (A*n)%B == 0:
    break
  
print(m)
abc = sorted(map(int, input().split()))
print(`Yes` if abc[0]+abc[1] == abc[2] else `No`)


### FIXED CODE ###

abc = sorted(map(int, input().split()))
print ('Yes' if abc[0]+abc[1] == abc[2] else 'No')
def divisors(n):
  ret=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if n//i!=i:
        ret.append(n//i)
  return ret

n=int(input())
divs1=divisors(n)
divs2=divisors(n-1)
print(divs1)
print(divs2)
cand=divs2
for val in divs2:
  cand.add(val)
for val in divs1:
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cand.append(val)
if n not in cand:
  cand.append(n)
if n-1!=1 and n-1 not in cand:
  cand.append(n-1)
print(cand)
print(len(cand))

### FIXED CODE ###

def divisors(n):
  ret=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      if n//i!=i:
        ret.append(n//i)
  return ret

n=int(input())
if n==2:
  print(1)
else:
  divs1=divisors(n)
  divs2=divisors(n-1)
  cand=divs2
  for val in divs1:
    tmp=n
    while tmp%val==0:
      tmp=tmp//val
    if tmp%val==1:
      cand.append(val)
  if n not in cand:
    cand.append(n)
  if n-1 not in cand:
    cand.append(n-1)
  print(len(cand))
l = list(map(int, input().split()))
for i in range(3):
    for j in range(i + 1, 3):
        if l[i] == l[j]:
            s = s + 1
print(s)

### FIXED CODE ###

l = list(map(int, input().split()))
s = 3
for i in range(3):
    for j in range(i + 1, 3):
        if l[i] == l[j]:
            s = s - 1
if l[0] == l[1] and l[1] == l[2]:
    s = s + 1
print(s)
H, W, K = [int(n) for n in input().split()]
for _ in range(K):
  a = 1
print(count)

### FIXED CODE ###

from itertools import product
import numpy as np

H, W, K = [int(n) for n in input().split()]
arr = np.zeros((H, W))
count = 0

for h in range(H):
    row = input()
    arr[h, :] = np.array([0 if mark=='.' else 1 for mark in row])

for row_onehot, col_onehot in product(product(range(2), repeat=H), product(range(2), repeat=W)):
    row_indexes = np.argwhere(np.array(row_onehot)==1).flatten()
    col_indexes = np.argwhere(np.array(col_onehot)==1).flatten()
    arr_ = arr.copy()
    for row_idx in row_indexes:
        arr_[row_idx, :] = 0
    for col_idx in col_indexes:
        arr_[:, col_idx] = 0
    if arr_.sum() == K:
        count += 1

print(count)
k=int(input())

print('ACL'*K)

### FIXED CODE ###

k=int(input())
print('ACL'*k)
lis=[]
lis.append(input())

while true:
    inp=input()
    if inp==0:
        print lis[-1]
        del lis[-1]
    else:
        lis.append(inp)

### FIXED CODE ###

import sys
import sys

a = []
for line in sys.stdin:
    a.append(line)

lis=[]
for n in a:
    inp=int(n)
    if inp==0:
        print lis[-1]
        del lis[-1]
    else:
        lis.append(inp)
S = input()
if S =＝ "hi"*int(len(S)//2):
    print("Yes")
else:
    print("No")    

### FIXED CODE ###

S = input()
if S == "hi"*int(len(S)//2):
    print("Yes")
else:
    print("No")
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

p=gcd_list(a)

print(p)




### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

p=gcd_list(a)

print(p)
import math
 
i = input().split()
n = int(i[0])
D = int(i[1])
num_list = []
count = 0
for i in range(n):
	num_list.append(list(map(int,input().split())))
 
for j in num_list:
    x = j[0]
    y = j[1]
    dist = math.sqrt(x ** 2 + y ** 2)
    if dist <= D:
        count += 1
 
print(count)

### FIXED CODE ###

rawtemp = input()
temp = int(rawtemp)

if temp < 30:
    print("No")
else:
    print("Yes")
N = int(input())
S = input()
if N%2 == 1:
  print("NO")
if (S[0: N/2 -1] == S[N/2: N-1 ]):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

N = int(input())
S = input()
if N%2 == 1:
  print("No")
else:
  if S[0: N//2] == S[N//2: N]:
    print("Yes")
  else:
    print("No")
n = int(input())
if n >= 30:
  return "Yes"
else:
  return "No"

### FIXED CODE ###

n = int(input())
a = "Yes"
b = "No"
if n >= 30:
  print(a)
else:
  print(b)
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

#nCr
def comb(n,r):
    x = 1
    y = 1
    for i in range(r):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

ncr = [0]*(n+1)
for i in range(1,n+1):
    ncr[i] = comb(n-i,k-1)

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

print(ans)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

f=[1]
for i in range(1,n+1):
  f.append(f[-1]*i % mod)

#nCr
def comb(n,r):
    if n <= 0 or r <= 0:
        return 0
    x = f[n] % mod
    y = f[r] * f[n-r] % mod
    return (x * pow(y, mod-2, mod) % mod)

ans = 0
for i in range(n):
    c = comb(n-i-1,k-1)
    ans += A[n-1-i] * c - A[i] * c
    ans %= mod
    if c == 1:
        break

print(ans)
import math


def actual(n, a, b):
    # 文字列の長さがN以上になるために必要な操作の回数
    required_operations = math.ceil(n / (a + b))

    s = ''

    for _ in range(required_operations):
        s += '青' * a + '赤' * b

    return s[:n].count('青')


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


### FIXED CODE ###

def actual(n, a, b):
    n_op_least = n // (a + b)

    n_blue_least = a * n_op_least
    adjustment = min(n % (a + b), a)

    return n_blue_least + adjustment

n, a, b = map(int, input().split())
print(actual(n, a, b))
N = int(input())
X = input()

def f(n, first):
    cnt = 1
    n %= first
    while n!=0:
        pc = bin(n).count("1")
        n = n%pc
        cnt += 1
    return cnt

v = 0
for i, j in enumerate(X[::-1]):
    if j=="1":
        v += 2**i
cnt = X.count("1")

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        buf = v+2**p
        c2 = cnt+1
    else:
        buf = v-2**p
        c2 = cnt-1
    print(f(buf, c2))

### FIXED CODE ###

def f(n):
    cnt = 0
    while n:
        buf = n
        pc = 0
        while buf:
            pc += buf%2
            buf //= 2
        n = n%pc
        cnt += 1
    return cnt

N = int(input())
X = input()

v1, v2 = 0, 0
cnt = X.count("1")
for i, j in enumerate(X[::-1]):
    if j=="1":
        v1 += pow(2, i, cnt+1)
        v1 %= (cnt+1)

        if cnt>1:
            v2 += pow(2, i, cnt-1)
            v2 %= (cnt-1)

for i in range(N):
    p = N-i-1
    buf = 0
    c2 = 0
    if X[i]=="0":
        c2 = cnt+1
        buf = (v1+pow(2, p, c2))%c2
        print(f(buf)+1)
    else:
        c2 = cnt-1
        if c2>0:
            buf = (v2-pow(2, p, c2))%c2
            print(f(buf)+1)
        else:
            print(0)
N = input()
A = list(map(int, input().split(' ')))
bit = 0
for a in A:
    bit |= a
print(len(bit) - len(bit.rstrip('0')))

### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
cnt = 0
while all(i%2==0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
H, W = map(int, input().split())
C = [0] * W
for i in range(H):
    C[i] = input()

for i in range(H):
    print(C[i])
    print(C[i])

### FIXED CODE ###

H, W = map(int, input().split())
C = [''] * H
for i in range(H):
    C[i] = input()

for i in range(H):
    print(C[i])
    print(C[i])
a,b=map(int,input().split())
if a*b*(a+b)%3==0:
  print(""Possible")
else:
        print("Impossible")

### FIXED CODE ###

a,b=map(int,input().split())
if a*b*(a+b)%3==0:
  print("Possible")
else:
  print("Impossible")