Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    Nmax = 10**6+1

    A = list(map(int, input().split()))
    A. sort()

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline

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

    A = list(map(int, input().split()))
    A. sort()
    Nmax = A[-1] + 1

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Nmax = 10**6+1

A = list(map(int, input().split()))
A. sort()

prime = [0]*Nmax
for i in range(N):
    if prime[A[i]] == 0:
        prime[A[i]] = 1
    else:
        prime[A[i]] = -1

for a in A:
    if prime[a] != 0:
        for q in range(a*2, Nmax, a):
            prime[q] = 0



print(sum(a for a in prime if a == 1))

Fixed submission:
import sys
input = sys.stdin.readline

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

    A = list(map(int, input().split()))
    A. sort()
    Nmax = A[-1] + 1

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
N = int(input())
Nmax = 2*(10**5)+1

A = list(map(int, input().split()))
A. sort()

prime = [0]*Nmax
for i in range(N):
    if prime[A[i]] == 0:
        prime[A[i]] = 1
    else:
        prime[A[i]] = -1

for a in A:
    if prime[a] == 1:
        for q in range(a*2, Nmax, a):
            prime[q] = 0



print(sum(a for a in prime if a == 1))

Fixed submission:
import sys
input = sys.stdin.readline

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

    A = list(map(int, input().split()))
    A. sort()
    Nmax = A[-1] + 1

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = list(map (int, input().split()))
B = 1

for i in range(N):
    B *= A[i]

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

Fixed submission:
N = int(input())

A = list(map(int, input().split()))

res = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1
        break



print(res)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = list(map(int, input().split()))

res = A[0]



for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1

if 0 in A:
    res = 0

print(res)

Fixed submission:
N = int(input())

A = list(map(int, input().split()))

res = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1
        break



print(res)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = list(map(int, input().split()))

res = A[0]

for i in range(N-1):
    res = res*A[i+1]

if res > 10**18:
    res = -1

print(res)

Fixed submission:
N = int(input())

A = list(map(int, input().split()))

res = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(N-1):
    res = res*A[i+1]
    if res > 10**18:
        res = -1
        break



print(res)
Buggy python submission (verdict: Runtime Error):
import math
import collections

n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if n == 1:
    print(0)
else:
    c = collections.Counter(prime_factorize(n))

res = 0
for x, y in c.items():
    num = int( (-1 + (1 +8*y)**(0.5))/2 )
    res += num

print(res)


Fixed submission:
import math
import collections

n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if n == 1:
    print(0)
    exit()
else:
    c = collections.Counter(prime_factorize(n))

res = 0
for x, y in c.items():
    num = int( (-1 + (1 +8*y)**(0.5))/2 )
    res += num

print(res)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from math import gcd
N = int(input())
MOD = 10**9 + 7
L = defaultdict(lambda: [0,0])
for _ in range(N):
    A, B = map(int, input().split())
    d = gcd(A,B)
    A, B = A//d, B//d
    if A<0:
        A, B = -A, -B
    if B>=0:
        L[(A,B)][0] += 1
    else:
        L[(-B,A)][1] += 1
res = 1
for x,y in L.values():
    res *= pow(2,x,MOD) + pow(2,y,MOD) -1
    res %= MOD
print(res-1)

Fixed submission:
from collections import defaultdict
from math import gcd
N = int(input())
MOD = 10**9 + 7
L = defaultdict(lambda: [0,0])
zero = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A==0: d=B
    elif B==0: d=A
    else: d=gcd(A,B)
    if d != 0:
        A, B = A//d, B//d
        if A<0: A, B = -A, -B
        if B>0: L[(A,B)][0] += 1
        else: L[(-B,A)][1] += 1
    else: zero += 1
res = 1
for x,y in L.values():
    res *= pow(2,x,MOD) + pow(2,y,MOD) -1
    res %= MOD
print((res+zero-1)%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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


res = 0
for i in range(N):
    if A[i] >= N:
        continue
    for j in range(i,N):
        if abs(i-j) == A[i] + A[j]:
            res += 1

print(res)


Fixed submission:
# https://atcoder.jp/contests/abc166/tasks/abc166_e

"""
変数分離すれば互いに独立なので、
連想配列でO(N)になる。
"""


import sys
input = sys.stdin.readline
from collections import Counter

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

P = (j+1-A[j] for j in range(N))
M = (i+1+A[i] for i in range(N))

dic = Counter(P)

res = 0
for m in M:
    res += dic.get(m,0)

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
from itertools import chain
from collections import Counter

def floyd_warshall(V, dist):                                               # 動的計画法。頂点 k まで経由することが可能な場合の最短距離という部分問題を考えて、k = 0 から漸化式的に計算する
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]                # dist は頂点 k までを経由した場合の最短距離。dist[i][k]は k を経由することは無いので、dist[i][k]は k ステップ目で更新されることはない。
                                                                        # よって、min の中身は全て k-1 ステップ目の情報で構成されており、漸化式となっている。
    return dist

##############################
V, X, Y = map(int, input().split())                                        # V:頂点数　E:辺の数

INF = float("inf")                                                      # 10**18 にすると、負のコストがある場合に少し面倒になる

dist = [[INF] * V for _ in range(V)]                                    # 辺が存在しない事をコスト無限大で表現
for k in range(V-1):
    i,j,weight = k, k+1, 1
    # i -= 1                                                            # 番号のデクリメントが必要な場合、コメントアウトを消す
    # j -= 1
    dist[i][j] = weight
    dist[j][i] = weight                                               # 無向グラフの場合はコメントアウトを消す
for i in range(V):
    dist[i][i] = 0                                                      # 自身のところに行くコストは０

dist[X-1][Y-1] = 1
dist[Y-1][X-1] = 1

d = floyd_warshall(V, dist)                                                # 各点間の距離が隣接行列の形で与えられる

res = Counter(chain.from_iterable(d))

for i in range(1,V):
    print(res.get(i,0)//2)


Fixed submission:
N, X, Y = map(int, input().split())

X -= 1
Y -= 1
dist = [0]*(N-1)
for i in range(N):
    for j in range(i+1, N):
        dist[min(j-i, abs(X-i) + 1 + abs(Y-j))-1] += 1

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

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import chain
from collections import Counter


V, X, Y = map(int, input().split())                             # V:頂点数 E:辺の数 r:始点

edge = np.array([[i,i+1,1] for i in range(1,V)] + [[X, Y,1]], dtype = np.int64).T

graph = csr_matrix((edge[2], (edge[:2] - 1)), (V, V))           # [[辺の左端],[辺の右端],[辺の距離]] の形で渡す
# graph = csr_matrix((edge[2], (edge[:2] )), (V, V))           # 番号のデクリメントが不要な場合


d = floyd_warshall(graph, directed = False)                         # 有効グラフの場合は directed = True とする。

nagativity = False                                             # 負のサイクルかどうかを判定
for i in range(V):
    if d[i][i] < 0:
        nagativity = True
if nagativity:
    print('NEGATIVE CYCLE')
else:
    d = [['INF' if i == float("inf") else int(i) for i in l ] for l in d]   # numpy.float64をintに変換し、inf をどのように記述するかを指定

res = Counter(chain.from_iterable(d))

for i in range(1,V):
    print(res.get(i,0)//2)




Fixed submission:
N, X, Y = map(int, input().split())

X -= 1
Y -= 1
dist = [0]*(N-1)
for i in range(N):
    for j in range(i+1, N):
        dist[min(j-i, abs(X-i) + 1 + abs(Y-j))-1] += 1

print(*dist, sep="\n")
Buggy python submission (verdict: Runtime Error):
"""

制約の小ささから見て全探索

"""

from itertools import product, accumulate
from bisect import *
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = []
T = []
for i in range(H):
    S.append(list(map(int, input().strip())))
    T.append(list(accumulate([0] + S[-1])))

cnt_list = []
for a in product((0,1),repeat=H):
    past_a = a[0]
    T2 = [[0]*(W+1)]
    for i in range(H):
        if a[i] == past_a:
            for j, t in enumerate(T[i]):
                T2[-1][j] += t
        else:
            T2.append(T[i])
        past_a = a[i]
    cnt = len(T2) - 1
    l = 0
    flg = False
    while True:
        temp = []
        for s in T2:
            temp.append(bisect_right(s[l+1:], K + s[l]) + l)
        if min(temp) == 0:
            flg = True
            break
        else:
            l = min(temp)
        if l >= W:
            break
        else:
            cnt += 1
    if not flg:
        cnt_list.append(cnt)

print(min(cnt_list))



Fixed submission:
"""

制約の小ささから見て全探索

"""

from itertools import product, accumulate
from bisect import *
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = []
T = []
for i in range(H):
    S.append(list(map(int, input().strip())))
    T.append(list(accumulate([0] + S[-1])))

cnt_list = []
for a in product((0,1),repeat=H):
    past_a = a[0]
    T2 = [[0]*(W+1)]
    for i in range(H):
        if a[i] == past_a:
            for j, t in enumerate(T[i]):
                T2[-1][j] += t
        else:
            T2.append(T[i].copy())
        past_a = a[i]
    cnt = len(T2) - 1
    l = 0
    flg = False
    while True:
        temp = []
        for s in T2:
            temp.append(bisect_right(s[l+1:], K + s[l]) + l)
        if min(temp) == 0:
            flg = True
            break
        else:
            l = min(temp)
        if l >= W:
            break
        else:
            cnt += 1
    if not flg:
        cnt_list.append(cnt)

print(min(cnt_list))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

flip = 0
for _ in range(Q):
    q = input().split()
    if q[0] == "1":
        flip += 1
        flip %= 2
    else:
        if (int(q[1]) + flip)%2 == 0:
            S = "".join([S,q[2]])
        else:
            S = "".join([q[2],S])

if flip == 0:
    print(S)
else:
    print(S[::-1])

Fixed submission:
from collections import deque

S = deque(input())
Q = int(input())

flip = 0
for _ in range(Q):
    q = input().split()
    if q[0] == "1":
        flip += 1
        flip %= 2
    else:
        if (int(q[1]) - 1 + flip)%2 == 0:
            S.appendleft(q[2])
        else:
            S.append(q[2])

S = list(S)
if flip == 0:
    print(*S, sep="")
else:
    print(*S[::-1], sep="")

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

flip = 0
for _ in range(Q):
    q = input().split()
    if q[0] == "1":
        flip += 1
        flip %= 2
    else:
        if (int(q[1]) + flip)%2 == 0:
            S = S + q[2]
        else:
            S = q[2] + S

if flip == 0:
    print(S)
else:
    print(S[::-1])

Fixed submission:
from collections import deque

S = deque(input())
Q = int(input())

flip = 0
for _ in range(Q):
    q = input().split()
    if q[0] == "1":
        flip += 1
        flip %= 2
    else:
        if (int(q[1]) - 1 + flip)%2 == 0:
            S.appendleft(q[2])
        else:
            S.append(q[2])

S = list(S)
if flip == 0:
    print(*S, sep="")
else:
    print(*S[::-1], sep="")
Buggy python submission (verdict: Runtime Error):
"""
タグ：区間
"""
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
S = input()

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p = p*10%P

    cnt = [0]*P
    for i in range(N+1):
        cnt[T[i]%P] += 1

    res = 0
    for c in cnt:
        res += c*(c-1)//2
    print(res)

Fixed submission:
"""
タグ：区間
"""
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
S = input().strip()

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p = p*10%P

    cnt = [0]*P
    for i in range(N+1):
        cnt[T[i]%P] += 1

    res = 0
    for c in cnt:
        res += c*(c-1)//2
    print(res)

Buggy python submission (verdict: Time Limit Exceeded):
"""
タグ：区間
"""

N, P = map(int, input().split())
S = input()

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p *= 10

    cnt = [0]*P
    for i in range(N+1):
        cnt[T[i]%P] += 1

    res = 0
    for c in cnt:
        res += c*(c-1)//2
    print(res)

Fixed submission:
"""
タグ：区間
"""
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
S = input().strip()

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p = p*10%P

    cnt = [0]*P
    for i in range(N+1):
        cnt[T[i]%P] += 1

    res = 0
    for c in cnt:
        res += c*(c-1)//2
    print(res)
Buggy python submission (verdict: Runtime Error):
def knapsack_price(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[price <= V] = 価値を固定した時の最大重量 """
    V = 10**6
    dp_max = 0
    dp = [dp_max] * (V + 1)
    dp[0] = 0   # 境界条件：　価値0 の時は重さは0

    for item in range(N):
        if single:
            S = range(V, price_list[item]-1, -1)
        else:
            S = range(price_list[item], V + 1)
        for price in S:
            dp[price] = max2(dp[price], dp[price - price_list[item]] + weight_list[item])
    return min(price for price in range(V+1) if dp[price] >= W)


#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


W, N = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


print(knapsack_price(single=False))


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


Fixed submission:
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さを固定した時の最小価値 """
    weight_max = max(weight_list)
    price_max = max(price_list)
    W2 = W + weight_max
    dp_max = float("inf")  # 総和価値の最大値
    dp = [dp_max] * W2
    dp[0] = 0               # 重さ 0 の時は価値 0

    for item in range(N):
        if single:
            S = range(W2, weight_list[item] - 1, -1)
        else:
            S = range(weight_list[item], W2)
        for weight in S:
            dp[weight] = min2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return min(dp[w] for w in range(W, W2))

#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


W, N = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


print(knapsack_weight(single=False))


############################################################################################
Buggy python submission (verdict: Runtime Error):
from bisect import *

N, D, A = map(int, input().split())
X = [0]
H = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append(X[-1] + x)
    H.append(h)

Imos = [0]*N
cnt = 0
damage = 0
res = 0
for i in range(N):
    h = H[i] - damage
    x = X[i+1]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = bisect_left(X, x+2*D) - 1
        Imos[p] += cnt
        damage = damage - Imos[i]*A + cnt * A
        res += cnt
print(res)

Fixed submission:
from bisect import *

N, D, A = map(int, input().split())

data = []
for _ in range(N):
    x, h = map(int, input().split())
    data.append((x,h))
data.sort()

X = []
H = []
for x, h in data:
    X.append(x)
    H.append(h)

Imos = [0]*(N+1)
cnt = 0
damage = 0
res = 0
for i in range(N):
    damage -= Imos[i]*A
    h = H[i] - damage
    x = X[i]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = min(bisect_right(X, x+2*D)-1, N-1)
        Imos[p+1] += cnt
        damage = damage + cnt * A
        res += cnt
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

############################################################################################################
from itertools import combinations

MOD = mod=10**9+7

N, K = map(int, input().split())
C = Combination(N)
A = list(map(int, input().split()))
if K == 1:
    print(0)
    exit()
A.sort()

res = 0
for i,j in combinations(range(N),2):
    res += C(j-i+1-2,K-2) * (A[j] - A[i])

print(res%MOD)


Fixed submission:
import sys
input = sys.stdin.readline

class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

############################################################################################################
from itertools import combinations

MOD = mod=10**9+7

N, K = map(int, input().split())
C = Combination(N)
A = list(map(int, input().split()))
if K == 1:
    print(0)
    exit()
A.sort()

res = 0
for i in range(K-1,N):
    res += C(i+1-1,K-1) * A[i]

for i in range(N-K+1):
    res -= C(N-i-1,K-1) * A[i]

print(res%MOD)