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

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
map = [[False]*W for _ in range(H)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
    map[h-1][w-1] = True
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

cnt = len(hs)*len(ws)
for h in hs:
    for w in ws:
        if not map[h][w]:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)


Fixed submission:
import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

HW = set(HW)
for h in hs:
    for w in ws:
        if (h+1, w+1) not in HW:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)

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

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

cnt = len(hs)*len(ws)
for h, w in HW:
    if h-1 in hs and w-1 in ws:
        cnt -= 1
print(max(h_count)+max(w_count) - (cnt==0))



Fixed submission:
import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

HW = set(HW)
for h in hs:
    for w in ws:
        if (h+1, w+1) not in HW:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
for i in range(K):
    ans *= A[i]

for i in range(K, N):
    newans = (ans * A[i]) // A[i-K]
    print('Yes' if ans < newans else 'No')


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

for ai_k, ai in zip(A, A[K:]):
    print('Yes' if ai_k < ai else 'No')
Buggy python submission (verdict: Runtime Error):
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
x_popcounts = [x_popcount - 1, x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N

if X == 0:
    for i in range(N-1):
        print(1)
    print(0)
    sys.exit()

def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt

flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1

for i in range(1, N):
    flg = (X>>i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1


print('\n'.join(map(str, ans[::-1])))



Fixed submission:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
is_zeroflg = [x_popcount-1 <= 0, False]
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N


def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1
if is_zeroflg[flg]:
    ans[0] = 0

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if is_zeroflg[flg]:
        ans[i] = 0

print('\n'.join(map(str, ans[::-1])))

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

def f(n):
    cnt = 0
    while n!=0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt

for i in range(1, N+1):
    print(f(X ^ (1 << (N-i))))





Fixed submission:
import sys
N = int(input())
X = int(input(), 2)
x_popcount = sum(map(int, bin(X)[2:]))
is_zeroflg = [x_popcount-1 <= 0, False]
x_popcounts = [max(1, x_popcount - 1), x_popcount + 1]
X_per_popcounts = [X % x_popcounts[0], X % x_popcounts[1]]
mods = [0, 0]
ans = [0]*N


def f(n):
    cnt = 0
    while n != 0:
        popcount = sum(map(int, bin(n)[2:]))
        n = n % popcount
        cnt += 1
    return cnt


flg = X & 1 ^ 1
mods[0] = (-1) % x_popcounts[0]
mods[1] = 1 % x_popcounts[1]
tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
ans[0] = f(tmp) + 1
if is_zeroflg[flg]:
    ans[0] = 0

for i in range(1, N):
    flg = (X >> i) & 1 ^ 1
    mods[0] = (mods[0] * 2) % (x_popcounts[0])
    mods[1] = (mods[1] * 2) % (x_popcounts[1])
    tmp = (X_per_popcounts[flg] + mods[flg]) % x_popcounts[flg]
    ans[i] = f(tmp) + 1
    if is_zeroflg[flg]:
        ans[i] = 0

print('\n'.join(map(str, ans[::-1])))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

T = int(input())

def solve():
    N = int(input())
    KLR = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[2]-x[1])
    line = [-1]*N
    ans = 0
    for k, l, r in KLR:
        if l < r:
            break
        flg = False
        for i in range(k-1, -1, -1):
            if line[i] == -1:
                line[i] = 1
                flg = True
                break
        if flg:
            ans += l
        else:
            ans += r
    line = [-1] * N
    for k, l, r in KLR[::-1]:
        if l >= r:
            break
        flg = False
        for i in range(k, N):
            if line[i] == -1:
                line[i] = 1
                flg = True
                break
        if flg:
            ans += r
        else:
            ans += l
    print(ans)


for _ in range(T):
    solve()


Fixed submission:
import sys
import heapq


input = sys.stdin.readline

T = int(input())

def solve():
    N = int(input())
    ls = []
    rs = []
    heapq.heapify(ls)
    heapq.heapify(rs)
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l - r >= 0:
            heapq.heappush(ls, (k, l, r))
        else:
            heapq.heappush(rs, (N-k, l, r))
    ans = 0
    ls_l = []
    heapq.heapify(ls_l)
    while len(ls) != 0:
        k, l, r = heapq.heappop(ls)
        heapq.heappush(ls_l, (l-r))
        ans += r
        while len(ls_l) > k:
            heapq.heappop(ls_l)
    rs_r = []
    heapq.heapify(rs_r)
    while len(rs) != 0:
        k, l, r = heapq.heappop(rs)
        heapq.heappush(rs_r, (r-l))
        ans += l
        while len(rs_r) > k:
            heapq.heappop(rs_r)
    while len(ls_l) != 0:
        ans += heapq.heappop(ls_l)
    while len(rs_r) != 0:
        ans += heapq.heappop(rs_r)
    print(ans)


for _ in range(T):
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
ans = 0
for i in range(1, N+1):
    til = N//i
    divsum = int(til*(til+1)/2)
    ans += divsum*i
print(ans)


Fixed submission:
N = int(input())
ans = 0
for i in range(1, N+1):
    til = N//i
    divsum = int(til*(til+1)/2)
    ans += divsum*i
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
ans = 0
for i in range(1, N+1):
    divsum = sum(range(1, N//i + 1))
    ans += divsum*i
print(ans)


Fixed submission:
N = int(input())
ans = 0
for i in range(1, N+1):
    til = N//i
    divsum = int(til*(til+1)/2)
    ans += divsum*i
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
f = [1] * (N+1)
for i in range(2, N+1):
    for j in range(N//i + 1):
        f[i*j] += 1
ans = 0
for i, fk in enumerate(f):
    ans += i*fk
print(ans)


Fixed submission:
N = int(input())
ans = 0
for i in range(1, N+1):
    til = N//i
    divsum = int(til*(til+1)/2)
    ans += divsum*i
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

x = input()
print('A' if ord(x)<97 else 'a')

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

x = input()
print('A' if x.isupper() else 'a')
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = np.sort(np.array(list(map(int, input().split()))))
b = np.ones(N, dtype=bool)
for i, ai in enumerate(A):
    if b[i] == 0:
        continue
    b[b] = (A[b] % ai != 0)
    b[i] = (i==N-1) or (A[i]!=A[i+1])
print(b.sum())


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np

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

def main():
    ans = 0
    for i, ai in enumerate(A):
        ans += ((ai % np.delete(A, i)).min() != 0)
    print(ans)

main()


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

def main():
    ans = N
    for i, ai in enumerate(A):
        for aj in A[:i]+A[i+1:]:
            if ai % aj == 0:
                ans -= 1
                break
    print(ans)

main()


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = map(int, input().split())
ans = 1
for a in A:
  ans *= a
  if ans == 0:
    break
print(ans if ans<=10**18 else -1)



Fixed submission:
import sys

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
    sys.exit()

for a in A:
    ans *= a
    if ans > 1e18:
        print(-1)
        sys.exit()
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
  ans *= a
print(ans if ans<=10**18 else -1)


Fixed submission:
import sys

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
    sys.exit()

for a in A:
    ans *= a
    if ans > 1e18:
        print(-1)
        sys.exit()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, S = map(int, input().split())
A = list(map(int, input().split()))
P = 998244353
table = [[0 for _ in range(S+1)] for _ in range(N)]
table[0][0] = 2
if A[0]<=S:
    table[0][A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    for j in range(S+1):
        table[i][j] += (2*table[i-1][j])
        if j+Ai<=S:
            table[i][j+Ai] += table[i-1][j] 

print(table[N-1][S]%P)


Fixed submission:
import numpy as np

N, S = map(int, input().split())
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S+1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
    table[0, A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    table[i] += 2*table[i-1]
    if Ai <= S:
        table[i][Ai:] += table[i-1][:S-Ai+1]
    table[i] = table[i]%P

print(table[N-1][S])
Buggy python submission (verdict: Runtime Error):
H1, M1, H2, M2, K = map(int, input())
m1 = 60*H1 + M1
m2 = 60*H2 + M2
print(m2-m1-K)


Fixed submission:
H1, M1, H2, M2, K = map(int, input().split())
m1 = 60*H1 + M1
m2 = 60*H2 + M2
print(m2-m1-K)
Buggy python submission (verdict: Runtime Error):
import math
X = int(input())
for a in range(1, math.ceil(X ** (1 / 4)) + 1):
    tmp = abs(a ** 5 - X)**(1/5)
    if tmp % 1 == 0:
        A = a
        if a ** 5 - X > 0:
            B = int((a ** 5 - X)**(1 / 5))
        else:
            B = int((X - a ** 5)**(1 / 5)) * -1
print(A, B)


Fixed submission:
import math
X = int(input())
A, B = 1, 1


def is_ok(i, x):
    return pow(i, 5) >= x


def bisect(ng, ok, x):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, x):
            ok = mid
        else:
            ng = mid
    return ok


ss = math.ceil(X ** (1 / 4)) + 10
for a in range(1, math.ceil(X ** (1 / 4)) + 10):
    tmp = abs(pow(a, 5) - X)
    b = bisect(-1, ss, tmp)
    if tmp == pow(b, 5):
        A = a
        if a ** 5 - X > 0:
            B = b
        else:
            B = -1 * b
        break
print(A, B)
Buggy python submission (verdict: Runtime Error):
flg = len(set(input())) == 1:
print('Yes' if flg else 'No')

Fixed submission:
flg = len(set(input())) == 2
print('Yes' if flg else 'No')
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())
arange = set(range(math.ceil(A*100/8), math.ceil((A+1)*100/8)))
brange = set(range(math.ceil(B*100/10), math.ceil((B+1)*100/10)))
print(min(arange & brange))


Fixed submission:
import math
A, B = map(int, input().split())
arange = set(range(math.ceil(A*100/8), math.ceil((A+1)*100/8)))
brange = set(range(math.ceil(B*100/10), math.ceil((B+1)*100/10)))
ans_range = arange & brange
if len(ans_range) == 0:
    print(-1)
else:
    print(min(ans_range))
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque

input = sys.stdin.readline

S = deque(input()[:-1])
reverse_flg = 0
Q = int(input())
qs = [input().split() for _ in range(Q)]
for q in qs:
    if q[0] == '1':
        reverse_flg = reverse_flg ^ 1
    else:
        flg = (int(q[1]) + reverse_flg) % 2
        if flg == 1:
            S.appendleft(q[2])
        else:
            S.append(q[2])

if reverse_flg:
    S = S[::-1]
print(''.join(S))


Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

S = deque(input()[:-1])
reverse_flg = 0
Q = int(input())
qs = [input().split() for _ in range(Q)]
for q in qs:
    if q[0] == '1':
        reverse_flg = reverse_flg ^ 1
    else:
        flg = (int(q[1]) + reverse_flg) % 2
        if flg == 1:
            S.appendleft(q[2])
        else:
            S.append(q[2])

if reverse_flg:
    S.reverse()
print(''.join(S))
Buggy python submission (verdict: Time Limit Exceeded):
import collections, sys
N, P = map(int, input().split())
S = input()
s_mod = [0]*(N+1)

ans = 0
if P == 2:
    for i in range(N):
        ans += ((int(S[-(i+1)])%2) ^ 1) * (N-i)
    print(ans)
    sys.exit()
elif P == 5:
    for i in range(N):
        ans += ((int(S[-(i + 1)]) % 5)==0) * (N - i)
    print(ans)
    sys.exit()


for i in range(N):
    s_mod[i+1] = (10**i*int(S[-(i+1)])+s_mod[i]) % P
c = collections.Counter(s_mod)
for v in c.values():
    ans = (ans + v*(v-1)//2)
print(ans)


Fixed submission:
import collections, sys
N, P = map(int, input().split())
S = input()
s_mod = [0]*(N+1)

ans = 0
if P == 2:
    for i in range(N):
        ans += ((int(S[-(i+1)])%2) ^ 1) * (N-i)
    print(ans)
    sys.exit()
elif P == 5:
    for i in range(N):
        ans += ((int(S[-(i + 1)]) % 5) == 0) * (N - i)
    print(ans)
    sys.exit()


for i in range(N):
    s_mod[i+1] = (pow(10, i, P) * int(S[-(i+1)])+s_mod[i]) % P
c = collections.Counter(s_mod)
for v in c.values():
    ans = (ans + v*(v-1)//2)
print(ans)
Buggy python submission (verdict: Runtime Error):
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch

    def cal(self):
        if len(self.ch) == 0:
            return 2
        return reduce(lambda a, b: (a * b) % P, [ch.cal() for ch in self.ch]) + 1


hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] < x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.cal() for x, node in hq])
print(ans)




Fixed submission:
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch
        if len(self.ch) == 0:
            self.score = 2
        else:
            self.score = reduce(lambda a, b: (a * b) % P, [ch.score for ch in self.ch]) + 1

hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] < x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.score for x, node in hq])
print(ans)

Buggy python submission (verdict: Runtime Error):
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch

    def cal(self):
        if len(self.ch) == 0:
            return 2
        return reduce(lambda a, b: (a * b) % P, [ch.cal() for ch in self.ch]) + 1


hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] <= x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.cal() for x, node in hq])
print(ans)




Fixed submission:
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch
        if len(self.ch) == 0:
            self.score = 2
        else:
            self.score = reduce(lambda a, b: (a * b) % P, [ch.score for ch in self.ch]) + 1

hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] < x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.score for x, node in hq])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math


n, a, b = map(int, input().split())
P = int(1e9+7)
ans = pow(2, n, P) - 1  # 1本以上の花束の種類


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


ans = (ans - combinations_count(n, a)) % P
ans = (ans - combinations_count(n, b)) % P
print(ans)


Fixed submission:
from operator import mul
from functools import reduce


def combinations_count(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P



n, a, b = map(int, input().split())
P = int(1e9+7)
ans = pow(2, n, P) - 1  # 1本以上の花束の種類


ans = (ans - combinations_count(n, a, P))
ans = (ans - combinations_count(n, b, P))
print(ans%P)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 0
for i in range(0, k + 1):
    ans = (ans + cmb(n - 1, i, P) * cmb(n, i, P)) % P
print(ans)


Fixed submission:
import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 1
comb1 = 1
comb2 = 1
for i in range(1, k + 1):
    iinv = pow(i, P-2, P)
    comb1 = ((comb1 * (n - i)) * (iinv)) % P
    comb2 = ((comb2 * (n - i + 1)) * (iinv)) % P
    ans = (ans + comb1*comb2) % P
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
sys.setrecursionlimit(10000000)


def count(N, X):
    cnt = sum(map(int, str(X))) + sum(map(int, str(X - N)))
    return cnt


def solve_naive_first(N):
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive(N), 1+solve_naive(p*10-N))


def solve_naive(N):
    if N < 10:
        return min(N, 10-N+1)
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive((N // p + 1) * p - N) + (N // p + 1), solve_naive(N % p) + N // p)


def solve(N):
    l = list(map(int, str(N)[::-1]))
    n_0, n_1 = 0, 1  # 0: その桁で処理, 1: 次の桁に1タス
    for i in l:
        if i == 9:
            n_0, n_1 = n_0 + i, min(n_0 + 10 - i, n_1 + 10 - i - 1)
        else:
            n_0, n_1 = min(n_0 + i, n_1 + i + 1), min(n_0 +
                                                      10 - i, n_1 + 10 - i - 1)
    return min(n_0, n_1+1)


if __name__ == '__main__':
    N = int(input())
    ans = solve(N)
    print(ans)


Fixed submission:
import math


def count(N, X):
    cnt = sum(map(int, str(X))) + sum(map(int, str(X - N)))
    return cnt


def solve_naive_first(N):
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive(N), 1+solve_naive(p*10-N))


def solve_naive(N):
    if N < 10:
        return min(N, 10-N+1)
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive((N // p + 1) * p - N) + (N // p + 1), solve_naive(N % p) + N // p)


def solve(N):
    n_0, n_1 = 0, 1  # 0: その桁で処理, 1: 次の桁に1タス
    for i in N[::-1]:
        i = int(i)
        if i == 9:
            n_0, n_1 = n_0 + i, min(n_0 + 10 - i, n_1 + 10 - i - 1)
        else:
            n_0, n_1 = min(n_0 + i, n_1 + i + 1), min(n_0 +
                                                      10 - i, n_1 + 10 - i - 1)
    return min(n_0, n_1+1)


if __name__ == '__main__':
    N = input()
    ans = solve(N)
    print(ans)