Buggy python submission (verdict: Time Limit Exceeded):

def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret

N,K = map(int, input().split())
MOD = 10**9+7
A = list(map(int, input().split()))
A.sort()

if N == 1 or K == 1:
    print(0)
    exit()

# A_iがminに選ばれる回数と、maxに選ばれる回数それぞれをわけて考えて足していく
ans = 0
for i in range(N):
    # minになれるのは、iの右からK-1個選べる場合
    if N - (i+1) >= K-1:
        ans -= A[i] * nCr(N - (i+1), K-1) % MOD
    # maxになれるのは、iの左からK-1個選べる場合
    if i >= K-1:
        ans += A[i] * nCr(i, K-1) % MOD

    ans %= MOD

print(ans)

Fixed submission:

N,K = map(int, input().split())
MOD = 10**9+7
A = list(map(int, input().split()))
A.sort()




if N == 1 or K == 1:
    print(0)
    exit()


def nCr(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    # nCr = n!  / (r! * (n-r)!)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = MOD
#N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    # (a * b * c) % MOD = (a * b % MOD) * c % MOD みたいなやつを利用して、大きな値にならないように一ステップごとにMODをとる
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# A_iがminに選ばれる回数と、maxに選ばれる回数それぞれをわけて考えて足していく
ans = 0
for i in range(N):
    # minになれるのは、iの右からK-1個選べる場合
    if N - (i+1) >= K-1:
        ans -= A[i] * nCr(N - (i+1), K-1, MOD)
    # maxになれるのは、iの左からK-1個選べる場合
    if i >= K-1:
        ans += A[i] * nCr(i, K-1, MOD)

    ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):


from operator import mul
from functools import reduce

def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    # reduceは第一引数で与えた関数を第二引数のiterbleのそれぞれで実行した結果をもどす
    over = reduce(mul, range(n, n - r, -1), 1)
    under = reduce(mul, range(1,r + 1), 1)
    return over // under

N,K = map(int, input().split())
MOD = 10**9+7
A = list(map(int, input().split()))
A.sort()

if N == 1 or K == 1:
    print(0)
    exit()

# A_iがminに選ばれる回数と、maxに選ばれる回数それぞれをわけて考えて足していく
ans = 0
for i in range(N):
    # minになれるのは、iの右からK-1個選べる場合
    if N - (i+1) >= K-1:
        ans -= A[i] * nCr(N - (i+1), K-1) % MOD
    # maxになれるのは、iの左からK-1個選べる場合
    if i >= K-1:
        ans += A[i] * nCr(i, K-1) % MOD

    ans %= MOD

print(ans)

Fixed submission:

N,K = map(int, input().split())
MOD = 10**9+7
A = list(map(int, input().split()))
A.sort()




if N == 1 or K == 1:
    print(0)
    exit()


def nCr(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    # nCr = n!  / (r! * (n-r)!)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = MOD
#N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    # (a * b * c) % MOD = (a * b % MOD) * c % MOD みたいなやつを利用して、大きな値にならないように一ステップごとにMODをとる
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# A_iがminに選ばれる回数と、maxに選ばれる回数それぞれをわけて考えて足していく
ans = 0
for i in range(N):
    # minになれるのは、iの右からK-1個選べる場合
    if N - (i+1) >= K-1:
        ans -= A[i] * nCr(N - (i+1), K-1, MOD)
    # maxになれるのは、iの左からK-1個選べる場合
    if i >= K-1:
        ans += A[i] * nCr(i, K-1, MOD)

    ans %= MOD

print(ans)