Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math


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


def main(A, B, N):
    last = 0
    x = 0
    while x <= N:
        tmp = f(A, B, x)
        if tmp < last:
            print(last)
            return
        else:
            last = tmp
            x += 1
    else:
        print(last)
        return


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


Fixed submission:
A, B, N = map(int, input().split())


def f(x):
    global A, B
    return (A * x) // B - A * (x // B)


if N < B:
    print(f(N))
else:
    print(f(B - 1))

Buggy python submission (verdict: Time Limit Exceeded):
import math


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


def main(A, B, N):
    last = 0
    x = 0
    while x <= N:
        tmp = f(A, B, x)
        if tmp < last:
            print(last)
            return
        else:
            last = tmp
            x += 1
    else:
        print(last)


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


Fixed submission:
A, B, N = map(int, input().split())


def f(x):
    global A, B
    return (A * x) // B - A * (x // B)


if N < B:
    print(f(N))
else:
    print(f(B - 1))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(num):
    global N, ans, M
    n = len(num)
    if n == N:
        cnt = 0
        for a, b, c, d in con:
            a -= 1; b -= 1
            if num[b] - num[a] == c:
                cnt += d
        ans = max(ans, cnt)
    else:
        e = 1 if n == 0 else num[-1]
        for i in range(e, M + 1):
            dfs((*num, i))


N, M, Q = map(int, input().split())
con = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0
dfs(tuple())

print(ans)


Fixed submission:
A, B, N = map(int, input().split())


def f(x):
    global A, B
    return (A * x) // B - A * (x // B)


if N < B:
    print(f(N))
else:
    print(f(B - 1))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

l = 0
num = set()
step = set()
for k in range(1, M + 1):
    while True:
        if l in num:
            l += 1
            l %= N
            continue
        if (l + k) % N not in num:
            break
        if (l + (N - k)) % N not in num:
            l = (l + (N - k)) % N
            break
        l += 1
        l %= N

    print(l + 1, (l + k) % N + 1)
    num.add(l)
    num.add((l + k) % N)


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

cnt = 0

l = 0
k = M
while cnt < M and k > 0:
    print(l + 1, l + k + 1)
    cnt += 1
    l += 1
    k -= 2

l = M + 1
k = M - 1
while cnt < M:
    print(l + 1, l + k + 1)
    cnt += 1
    l += 1
    k -= 2
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


S = input()
N = len(S)

L = [0] * (N + 1)
s = 0
for i in range(N):
    s += int(S[N - 1 - i]) * pow(10, i)
    L[i + 1] = (s % 2019)

C = Counter(L)
cnt = 0
for key in list(C.keys()):
    k = C[key]
    cnt += (k * (k - 1)) // 2

print(cnt)


Fixed submission:
from collections import Counter


S = input()
N = len(S)

L = [0] * (N + 1)
s = 0
for i in range(N):
    s += int(S[N - 1 - i]) * pow(10, i, 2019)
    L[i + 1] = (s % 2019)

C = Counter(L)
cnt = 0
for key in list(C.keys()):
    k = C[key]
    cnt += (k * (k - 1)) // 2

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, rest):
    global C, N
    rst = 0
    if maxR[n] > 0:
        rst = maxR[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n + (C + 1) < N:
            rst += dfs(n + C + 1, C)
    else:
        if n + 1 < N:
            rst += dfs(n + 1, rest + 1)
    return rst


def dfs2(n, rest):
    global C, N
    rst = 0
    if maxL[n] > 0:
        rst = maxL[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n - (C + 1) >= 0:
            rst += dfs2(n - (C + 1), C)
    else:
        if n - 1 >= 0:
            rst += dfs2(n - 1, rest + 1)
    return rst


N, K, C = map(int, input().split())
S = input()
maxR = [-1] * N
for i in range(N):
    if S[i] == 'o' and maxR[i] == -1:
        maxR[i] = dfs(i, C)

if maxR[-1] == -1:
    maxR[-1] = 0
for i in range(N - 2, -1, -1):
    if maxR[i] == -1:
        maxR[i] = maxR[i + 1]

maxL = [-1] * N
for i in range(N - 1, -1, -1):
    if S[i] == 'o' and maxL[i] == -1:
        maxL[i] = dfs2(i, C)

if maxL[0] == -1:
    maxL[0] = 0
for i in range(1, N):
    if maxL[i] == -1:
        maxL[i] = maxL[i - 1]

ans = []
for i in range(N):
    r = maxR[i + 1] if i + 1 < N else 0
    l = maxL[i - 1] if i - 1 >= 0 else 0
    if r + l < K:
        ans.append(i + 1)

print(*ans, sep='\n')


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(n, rest):
    global C, N
    rst = 0
    if maxR[n] > 0:
        rst = maxR[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n + (C + 1) < N:
            rst += dfs(n + C + 1, C)
    else:
        if n + 1 < N:
            rst += dfs(n + 1, rest + 1)
    maxR[n] = rst
    return rst


def dfs2(n, rest):
    global C, N
    rst = 0
    if maxL[n] > 0:
        rst = maxL[n]
    elif rest >= C and S[n] == 'o':
        rst += 1
        if n - (C + 1) >= 0:
            rst += dfs2(n - (C + 1), C)
    else:
        if n - 1 >= 0:
            rst += dfs2(n - 1, rest + 1)
    maxL[n] = rst
    return rst


N, K, C = map(int, input().split())
S = input()
maxR = [-1] * N
for i in range(N):
    if S[i] == 'o' and maxR[i] == -1:
        maxR[i] = dfs(i, C)

if maxR[-1] == -1:
    maxR[-1] = 0
for i in range(N - 2, -1, -1):
    if maxR[i] == -1:
        maxR[i] = maxR[i + 1]

maxL = [-1] * N
for i in range(N - 1, -1, -1):
    if S[i] == 'o' and maxL[i] == -1:
        maxL[i] = dfs2(i, C)

if maxL[0] == -1:
    maxL[0] = 0
for i in range(1, N):
    if maxL[i] == -1:
        maxL[i] = maxL[i - 1]

ans = []
for i in range(N):
    r = maxR[i + 1] if i + 1 < N else 0
    l = maxL[i - 1] if i - 1 >= 0 else 0
    if r + l < K:
        ans.append(i + 1)

print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)
from heapq import heappush, heappop


def dfs(s, v, step):
    if step == 3:
        edge3[s].add(v)
        edge3[v].add(s)
    else:
        for nv in edge[v]:
            if status[nv] == 0:
                status[nv] = 1
                dfs(s, nv, step + 1)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
edge3 = [set() for _ in range(N)]
for s in range(N):
    status = [0] * N
    status[s] = 1
    dfs(s, s, 0)

# print(edge3)
q = []
for i, e3 in enumerate(edge3):
    heappush(q, (-len(e3), i))

x = (y for y in range(N + 1) if y % 3 != 0)
z = 1
Z = N // 3
ans = [None] * N
for i in range(N):
    lenE3, v = heappop(q)
    if ans[v] is None:
        if z <= Z:
            ans[v] = 3 * z
            z += 1
        else:
            ans[v] = next(x)
        for e3 in edge3[v]:
            if ans[e3] is None:
                ans[e3] = next(x)
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(v, step):
    global node0, node1
    if step & 1:
        color[v] = 1
        node1 += 1
    else:
        color[v] = 0
        node0 += 1
    for nv in edge[v]:
        if color[nv] is None:
            dfs(nv, step + 1)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
color = [None] * N
node0 = node1 = 0
dfs(0, 0)

ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
if node0 > num0 and node1 > num0:
    cur = 0
    while num1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num1 - 2
            num1 -= 1
        cur += 1
    cur = 0
    while num2 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num2 - 1
            num2 -= 1
        cur += 1
elif node0 <= num0:
    cur = 0
    while node0 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num0
            num0 -= 1
            node0 -= 1
        cur += 1
else:
    cur = 0
    while node1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num0
            num0 -= 1
            node1 -= 1
        cur += 1

cur = 0
while num0 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num0
        num0 -= 1
    cur += 1
while num1 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num1 - 2
        num1 -= 1
    cur += 1
while num2 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num2 - 1
        num2 -= 1
    cur += 1


print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * (10 ** i)
        mods[num % P] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        c = num % P
        cnt += mods[c] - 1
        mods[c] -= 1
        num -= int(s) * (10 ** (N - 1 - i))

print(cnt)


Fixed submission:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    T = [0] * (N + 1)
    mods = Counter({0: 1})
    for i, s in enumerate(reversed(S)):
        T[N - 1 - i] = (T[N - i] + int(s) * pow(10, i, P)) % P
        mods[T[N - 1 - i]] += 1
    for t in T:
        mods[t] -= 1
        cnt += mods[t]

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * (10 ** i)
        mods[num % P] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        c = num % P
        cnt += mods[c] - 1
        mods[c] -= 1
        num -= int(s) * (10 ** (N - 1 - i))

print(cnt)


Fixed submission:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    T = [0] * (N + 1)
    mods = Counter({0: 1})
    for i, s in enumerate(reversed(S)):
        T[N - 1 - i] = (T[N - i] + int(s) * pow(10, i, P)) % P
        mods[T[N - 1 - i]] += 1
    for t in T:
        mods[t] -= 1
        cnt += mods[t]

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * (10 ** i)
        mods[num % P] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        c = num % P
        cnt += mods[c] - 1
        mods[c] -= 1
        num -= int(s) * (10 ** (N - 1 - i))

print(cnt)


Fixed submission:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    T = [0] * (N + 1)
    mods = Counter({0: 1})
    for i, s in enumerate(reversed(S)):
        T[N - 1 - i] = (T[N - i] + int(s) * pow(10, i, P)) % P
        mods[T[N - 1 - i]] += 1
    for t in T:
        mods[t] -= 1
        cnt += mods[t]

print(cnt)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right


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

nega = bisect_left(A, 0)
posi = N - bisect_right(A, 0)
zero = N - nega - posi

numNega = nega * posi
numZero = (nega + posi) * zero + zero * (zero - 1) // 2
numPosi = N * (N - 1) // 2 - numNega - numZero

Nega = A[:nega]
Posi = A[N - posi:]


def negaCnt(n):
    rst = 0
    for a in Nega:
        b = n // a
        idx = bisect_right(Posi, b)
        rst += posi - idx
    return rst


def posiCnt(n):
    rst = 0
    for i, a in enumerate(Posi):
        b = (n + a - 1) // a
        idx = bisect_left(Posi, b, i + 1)
        rst += idx - (i + 1)
    for i, a in enumerate(Nega):
        b = (n + a - 1) // a
        idx = bisect_left(Nega, b, i + 1)
        rst += idx - (i + 1)
    return rst


if K <= numNega:
    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = Nega[0] * Posi[0]
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if negaCnt(mid) < K:
            ok = mid
        else:
            ng = mid
    ans = ok
elif numNega < K <= numNega + numZero:
    ans = 0
else:
    K2 = K - numNega - numZero
    Nega = [-x for x in reversed(Nega)]
    ok = 0
    ng = max(Nega[-1] ** 2, Posi[-1] ** 2) if nega > 0 else Posi[-1] ** 2
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if posiCnt(mid) < K2:
            ok = mid
        else:
            ng = mid
    ans = ok

print(ans)


Fixed submission:
N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for a in (plus, minus):
                l, r = 0, len(a) - 1
                while l < r:
                    while l < r and a[l] * a[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)

    if cnt < K:
        ok = mid
    else:
        ng = mid

print(ok)
Buggy python submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def f(i, j):
    if F[i][j]:
        return F[i][j]
    else:
        Fij = modFacts[i + j]
        Ii = invs[i]
        Ij = invs[j]
        rst = (Fij * Ii * Ij) % MOD
        F[i][j] = rst
        F[j][i] = rst
        return rst


r1, c1, r2, c2 = map(int, input().split())
modFacts, invs = prepare(max(r1, c1, r2, c2) * 2)


F = [[0] * (max(r2 + 1, c2 + 1)) for _ in range(max(r2 + 1, c2 + 1))]
ans = 0
for x in range(r1, r2 + 1):
    for y in range(c1, c2 + 1):
        tmp = f(x, y)
        ans += tmp
        ans %= MOD

print(ans)


Fixed submission:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def f(i, j):
    Fij = modFacts[i + j]
    Ii = invs[i]
    Ij = invs[j]
    rst = (Fij * Ii * Ij) % MOD
    return rst


def g(r1, r2, y):
    rst = 0
    for x in range(r1, r2 + 1):
        rst += f(x + 1, y)
        rst %= MOD
    return rst


r1, c1, r2, c2 = map(int, input().split())
modFacts, invs = prepare(max(r1, c1, r2, c2) * 2 + 1)


ans = g(r1, r2, c2) - g(r1, r2, c1 - 1)


print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    H, N = map(int, input().split())
    M = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = float('inf')
    dp = [INF] * (H + 1)
    dp[0] = 0
    
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)

    print(dp[H])


if __name__ == "__main__":
    main()


Fixed submission:
import sys

H, N = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
# A = [0] * N
# B = [0] * N
# for i, (a, b) in enumerate(M):
#     A[i] = a
#     B[i] = b


INF = 10 ** 9
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(H):
    for j in range(N):
        ni = min(H, i + M[j][0])
        b = M[j][1]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_right

H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for _ in range(N)]
M.sort()
A = [0] * N
B = [0] * N
for i, (a, b) in enumerate(M):
    A[i] = a
    B[i] = b


INF = 10 ** 9
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(H):
    for j in range(N):
        ni = min(H, i + A[j])
        b = B[j]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])


Fixed submission:
import sys

H, N = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
# A = [0] * N
# B = [0] * N
# for i, (a, b) in enumerate(M):
#     A[i] = a
#     B[i] = b


INF = 10 ** 9
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(H):
    for j in range(N):
        ni = min(H, i + M[j][0])
        b = M[j][1]
        dp[ni] = min(dp[ni], dp[i] + b)

print(dp[H])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys


N, D, A = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
M.sort()

q = deque()
qt = deque()

ans = 0
for x, h in M:
    if len(q) == 0:
        bomb = (h + A - 1) // A
        q.append((x + 2 * D, bomb))
        ans += bomb
    else:
        while h > 0:
            d, bomb = q.popleft()
            if x <= d:
                h -= bomb * A
                qt.append((d, bomb))
            if h > 0 and len(q) == 0:
                bomb = (h + A - 1) // A
                h -= bomb * A
                qt.append((x + 2 * D, bomb))
                ans += bomb
        while len(qt) > 0:
            q.appendleft(qt.pop())

print(ans)


Fixed submission:
from collections import deque
import sys


N, D, A = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
M.sort()

q = deque()
qt = deque()

ans = 0
dmg = 0
for x, h in M:
    if len(q) == 0:
        bomb = (h + A - 1) // A
        q.append((x + 2 * D, bomb))
        dmg += bomb * A
        ans += bomb
    else:
        while len(q) > 0:
            d, bomb = q.popleft()
            if d < x:
                dmg -= bomb * A
            else:
                q.appendleft((d, bomb))
                break
        if h > dmg:
            bomb = ((h - dmg) + A - 1) // A
            q.append((x + 2 * D, bomb))
            dmg += bomb * A
            ans += bomb

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


N, K = map(int, input().split())
A = list(map(int, input().split()))
modFacts, invs = prepare(N)


# mod2 = [0] * (N + 1)
# mod2[0] = 1
# for i in range(N):
#     mod2[i + 1] = mod2[i] * 2
#     mod2[i + 1] %= MOD

A.sort()
ans = 0
for i in range(N):
    for j in range(K - 1, N - i):
        x = A[i + j]
        y = A[i]
        ans += (x - y) * modFacts[j - 1] * invs[j - 1 - (K - 2)] * invs[K - 2]
        ans %= MOD

print(ans)


Fixed submission:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


N, K = map(int, input().split())
A = list(map(int, input().split()))
modFacts, invs = prepare(N)


# mod2 = [0] * (N + 1)
# mod2[0] = 1
# for i in range(N):
#     mod2[i + 1] = mod2[i] * 2
#     mod2[i + 1] %= MOD

A.sort()
ans = 0

for i in range(K - 1, N):
    n = i
    r = K - 1
    num = (modFacts[n] * invs[n - r] * invs[r]) % MOD
    ans += A[i] * num
    ans %= MOD

for i in range(N - K + 1):
    n = N - (i + 1)
    r = K - 1
    num = (modFacts[n] * invs[n - r] * invs[r]) % MOD
    ans -= A[i] * num
    ans %= MOD


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7


def modFact(n):
    global MOD
    if n == 1:
        return 1
    else:
        return (n * modFact(n - 1)) % MOD


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


N = int(input())
C = list(map(int, input().split()))
C.sort()
modFacts, invs = prepare(N)

mod2 = [0] * (N + 1)
mod2[0] = 1
x = 1
for i in range(N):
    mod2[i + 1] = x = (x * 2) % MOD

ans = 0
for i, c in enumerate(C):
    c %= MOD
    N_ = N - i - 1
    for j in range(0, N_ + 1):
        ans += mod2[N_] * mod2[i + 1] * mod2[i] * c * (j + 1) * modFacts[N_] * invs[N_ - j] * invs[j]
        ans %= MOD

print(ans)


Fixed submission:
MOD = 10 ** 9 + 7


N = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)

mod4 = [0] * (N + 1)
mod4[0] = 1
for i in range(N):
    mod4[i + 1] = (mod4[i] * 4) % MOD

ans = 0
N4 = mod4[N - 1]
for i, c in enumerate(C):
    j = i + 1
    ans += N4 * (j + 1) * c
    ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
R, S, P = map(int, input().split())
score = {'r': R, 's': S, 'p': P}
T = input()
hand = {'r': 'p', 's': 'r', 'p': 's'}

history = ['a'] * (2 * N)
cnt = 0
for i, t in enumerate(T):
    l = i - K
    r = i + K
    u = hand[t]
    flag = 1

    if u == history[l]:
        u = T[r]
        flag = 0

    cnt += score[u] * flag
    history[i] = u

print(cnt)


Fixed submission:
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

score = {'p': P, 'r': R, 's': S}
hand = {'r': 'p', 's': 'r', 'p': 's'}
H = [' '] * N

ans = 0
for sub in range(K):
    i = sub
    while i < N:
        c = T[i]
        if i - K >= 0 and hand[c] == H[i - K]:
            s = 0
            if i + K < N and hand[T[i + K]] == c:
                H[i] = hand[hand[c]]
            else:
                H[i] = c
        else:
            H[i] = hand[c]
            s = score[hand[c]]
        i += K
        ans += s

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

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


print(lcm(A, B))


Fixed submission:
from fractions import gcd

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


def lcm(x, y):
    return (x * y) // gcd(x, y)


print(lcm(A, B))