Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import heapq
def gijkstra(n,E,key=1,s=1):
    T, HQ = [[float('inf'), -1] for i in range(n+1)], [(0,s)]
    T[s][0] = 0
    while HQ:
        u = heapq.heappop(HQ)[1]
        for e in E[u]:
            d, v = T[u][0] + e[key], e[0]
            if T[v][0] > d:
                T[v] = [d, u]
                heapq.heappush(HQ,(d,v))
    return T

n, m, s, t =  map(int,input().split())
E = [[] for i in range(n+1)]
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append(e[1:2]+e[2:])
    E[e[1]].append(e[0:1]+e[2:])
T1 = gijkstra(n,E,key=1,s=s)
T2 = gijkstra(n,E,key=2,s=t)
T = [T1[v][0]+T2[v][0] for v in range(n+1)]
for i in range(n):
    print(10**15 - min(T[i+1:]))

### FIXED CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]
### BUGGY CODE ###

# 入力
N, K = map(int, input().split())
H = [int(i) for i in input().split()]

# DPテーブルを用意
dp = [float("inf") for i in range(N)]
# 初期値をセット
dp[0] = 0

# 足場0から順次最小コストを決定する
for i in range(1, N):
    # for j in range(1, K+1):
        # if i + j < N:
            # dp[i+j] = min(dp[i+j], (dp[i] + abs(H[i] - H[i+j])))
    dp[i] = min([dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, K+1) if i-j >= 0])

# 足場NのインデックスはN-1
print(dp[N-1])

### FIXED CODE ###

import numpy as np

# 入力
N, K = map(int, input().split())
H = np.array([int(i) for i in input().split()])

# ndarray型のDPテーブルを生成
dp = np.zeros(N, dtype=int)
# 初期値をセット
dp[0] = 0

# 各足場へたどり着く最小コストを調べる
for i in range(1, N):
    s = max(0, i-K)
    dp[i] = min(dp[s:i] + np.abs(H[i] - H[s:i])) # iより前の足場のコストに足す

print(dp[N-1])
### BUGGY CODE ###

def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def main():
    H,W,D = map(int,input().split())
    index  = [(0,0) for i in range(H*W+1)]
    A = []
    for i in range(H):
        temp = list(map(int, input().split()))
        for t in temp:
            index[t] = (i,temp.index(t))
        A.append(temp)
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        ans = 0
        prepoint = index[L]
        while(L != R):
            L += D
            nextpoint = index[L]
            ans += calc(prepoint, nextpoint)
            prepoint = nextpoint
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def main():
    H,W,D = map(int,input().split())
    index  = [(0,0) for i in range(H*W+1)]
    A = []
    for i in range(H):
        temp = list(map(int, input().split()))
        for t in temp:
            index[t] = (i,temp.index(t))
        A.append(temp)
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    dp = [0 for i in range(H*W+1)]
    for i in range(D, H*W+1):
        dp[i] = dp[i-D] + calc(index[i], index[i-D])
    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        print(dp[R]-dp[L])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
length = list(set(A))
dict = {}
count = 0
if len(length) > K:
  for i in length:
    if i not in dict:
      dict[i] = A.count(i)
  dict=sorted(dict.items(),key=lambda x:-x[1])
  for i in reversed(range(K,len(length))):
    count += dict[i][1]
print(count)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
count = [0]*max(A)
for i in A:
  count[i-1] += 1
print(sum(sorted(count,reverse=True)[K:]))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

def is_satisfied(s):
    ln = len(s)
    check = [s.count(i) == 2 for i in range(ln - 1, 1, -2)]
    if ln % 2 == 0:
        check.append(s.count(1) == 2)
    else:
        check.append(s.count(0) == 1)

    return all(check)


ans = 2 ** (n // 2) if is_satisfied(a) else 0
print(ans)


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

def is_satisfied(s):
    ln = len(s)
    check = sorted(list(range(ln - 1, 1, -2)) * 2)
    if ln % 2 == 0:
        check.insert(0, 1)
        check.insert(0, 1)
    else:
        check.insert(0, 0)

    return sorted(s) == check

    # for i in range(ln - 1, 1, -2):
    #     if not s.count(i) == 2:
    #         return False
    # if ln % 2 == 0:
    #     if not s.count(1) == 2:
    #         return False
    # else:
    #     if not s.count(0) == 1:
    #         return False

    # return True


ans = 2 ** (n // 2) % (10 ** 9 + 7)
print(ans if is_satisfied(a) else 0)
### BUGGY CODE ###

count = 0

N = int(input())
A = list(map(int, input().split()))
for start in range(0, N):
    for i in range(start, N):
        # 操作すべきリストを作成
        nums = A[start:i + 1]
        sum = 0
        binary = 0
        for s in range(len(nums)):
            sum += nums[s]
            binary = binary^nums[s]

        if sum == binary:
            count += 1

print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
my_sum = 0
count = 0
r, l = 0, 0

while r < N:
    boo = my_sum + A[r]
    foo = my_sum ^ A[r]
    if boo == foo:
        my_sum += A[r]
        r += 1
        count += (r - l)
    else:
        my_sum -= A[l]
        l += 1

print(count)
### BUGGY CODE ###

# cook your dish here
n=int(input())
arr=list(map(int,input().split()))
for i in range(0,n):
    temp=0
    for j in range(len(arr)):
        if i+1==arr[j]:
            temp+=1
    print(temp)

### FIXED CODE ###

# cook your dish here
n=int(input())
arr=list(map(int,input().split()))
blank=[0]*n
for i in range(len(arr)):
    blank[arr[i]-1]+=1
for i in blank:
    print(i)
### BUGGY CODE ###

def main():
    INF = 10 ** 20
    n, ma, mb = map(int, input().split())
    dp = [[INF] * 401 for _ in range(401)]
    dp[0][0] = 0
    for _ in range(n):
        a, b, c = map(int, input().split())
        for i in range(400 - a, -1, -1):
            for j in range(400 - b, -1, -1):
                dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)
    
    ans = INF
    for i in range(1, 400):
        if ma * i > 400 or mb * i > 400:
            break
        ans = min(ans, dp[ma * i][mb * i])
    if ans >= INF:
        print(-1)
    else:
        print(ans)

main()

### FIXED CODE ###

def main():
    INF = 10 ** 5
    n, ma, mb = map(int, input().split())
    dp = [[INF] * 401 for _ in range(401)]
    dp[0][0] = 0
    for _ in range(n):
        a, b, c = map(int, input().split())
        for i in range(400 - a, -1, -1):
            dpi = dp[i]
            dpia = dp[i + a]
            for j in range(400 - b, -1, -1):
                if dpia[j + b] > dpi[j] + c:
                    dpia[j + b] = dpi[j] + c
    
    ans = INF
    for i in range(1, 400):
        if ma * i > 400 or mb * i > 400:
            break
        ans = min(ans, dp[ma * i][mb * i])
    if ans >= INF:
        print(-1)
    else:
        print(ans)

main()
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()

for i in range(m):
  a = aaa.pop(-1) // 2
  insert_index = bisect.bisect_right(aaa, a)
  aaa.insert(insert_index, a)
  if a == 0:
    print(0)
    break
else:
  print(sum(aaa))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
aaa = [-1 * int(a) for a in input().split()]
heapq.heapify(aaa)

for i in range(m):
  a = -heapq.heappop(aaa) // 2
  heapq.heappush(aaa, -a)
  
print(-sum(aaa))
### BUGGY CODE ###

n, k, *A = map(int, open(0).read().split())
s = 1
for a in A[:k]:
    s *= a
B = [s]
for i in range(k, n):
    s *= A[i]
    s //= A[i-k]
    B.append(s)

for b0, b1 in zip(B, B[1:]):
    if b0 < b1:
        print('Yes')
    else:
        print('No')    


### FIXED CODE ###

n, k, *A = map(int, open(0).read().split())
for i in range(k, n):
    if A[i-k] < A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
n = int(input())
S = input()

i = S.find('#')
if i < 0:
    print(0)
    sys.exit()

Min = 200000
for j in range(i, n):
    if S[j:j+1] == '#':
        a = S[:j].count('#') 
        b = S[j:n].count('.')
        Min = min(Min, a+b)
        
print(Min)

### FIXED CODE ###

n = int(input())
S = input()

c = S.count('.')
Min = c


for j in range(n):
    if S[j] == '#':
        c += 1
    else:
        c -= 1
    Min = min(Min, c)
        
print(Min)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

check=dict()
N,z,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global z
    for i,j in z:
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    z=list(zip([2,3,5],b))
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

N=int(input())
P=1
for i in range (N):
	P*=i+1
P=P%(10**9+7)
print(P)

### FIXED CODE ###

N=int(input())
P=1
for i in range (N):
	P*=i+1
	P=P%(10**9+7)
print(P)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    h,n=map(int,input().split())
    a=[[int(i) for i in input().split()]for i in range(n)]
    
    dp=[float('inf')]*(h+1) #0-9
    dp[0]=0
    mini=float('inf')
    for i in range(h+1):
        if dp[i]==float('inf'):
            continue
        for ata,mp in a:
            if i+ata>=h:
                tmp=dp[i]+mp
                mini=min(mini,tmp)
                continue
            dp[i+ata]=min(dp[i+ata],dp[i]+mp)
    print(mini)

if __name__=='__main__':
    main()

### FIXED CODE ###


h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
inf=10**9
dp=[inf]*(h+1) #0-9
dp[0]=0
mini=inf
for i in range(h+1):
    if dp[i]==inf:
        continue
    for ata,mp in a:
        if i+ata>=h:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i+ata]=min(dp[i+ata],dp[i]+mp)
print(mini)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    if max(a) == a[i]:
        print(sorted(a)[-2])
    else:
        print(sorted(a)[-1])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
for i in a:
    print(a_second if i == a_first else a_first)
### BUGGY CODE ###

L, R = map(int, input().split())

mod = 2019
R = min(R, R + mod + 1)

ans = 100000000+5
for i in range(L, R):
    for j in range(i+1, R+1):
        ans = min(ans, i * j % mod)

print(ans)


### FIXED CODE ###

# [i, j] の中に2019の倍数があれば、その倍数を選択すれば最小値を0

import math

L, R = map(int, input().split())
mod = 2019

# (A * B) % mod = (A % mod) * (B % mod) % mod
l = L % 2019
r = R % 2019

ans = None
# mod以上差があれば2019の倍数を含んでいる (ex. 2 & 2025)
if R - L >= mod:
    ans = 0
else:
    # mod以上差がなくても、あまりが0をまたぐ (ex. 2018 & 2025 => 2018 & 6) 場合
    if l > r:
        ans = 0
    else:
        _min = 2019 * 2019
        for i in range(l, r):
            for j in range(i+1, r+1):
                _min = min(_min, i*j%mod)
        ans = _min

print(ans)
### BUGGY CODE ###

import numpy as np

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

a = []

for i in range(n[2]):
    a.append(int(input()))

if n[1] > n[2]:
    for c in range(n[0]):
            print('Yes')

else:
    m = [n[1]]*n[0]

    x = np.array(m)
    for j in range(n[2]):
        x -= 1
        x[a[j]-1] += 1

    for num in range(n[0]):
        if x[num] <= 0:
            print('No')
        else:
            print('Yes')



### FIXED CODE ###

import numpy as np

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

a = []

for i in range(n[2]):
    a.append(int(input()))

if n[1] > n[2]:
    for c in range(n[0]):
            print('Yes')

else:
    m = [n[1]]*n[0]

    x = np.array(m)
    x -= n[2]
    for j in range(n[2]):
        x[a[j]-1] += 1

    for num in range(n[0]):
        if x[num] <= 0:
            print('No')
        else:
            print('Yes')
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    left = [[None]*W for _ in range(H)]
    right = [[None]*W for _ in range(H)]
    up = [[None]*W for _ in range(H)]
    down = [[None]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1
            else:
                left[i][j] = -1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':        
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1
            else:
                right[-1-i][-1-j] = -1

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1
            else:
                up[i][j] = -1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            else:
                down[-1-i][-1-j] = -1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':        
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()
### BUGGY CODE ###

n, k= map(int, input().split())
l = list(map(int, input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(n-1):
    for j in range(1,min(k+1,(n-i))):
        dp[i+j]=min(dp[i]+(abs(l[i]-l[i+j])),dp[i+j])
print(dp[-1])

### FIXED CODE ###

n,k =map(int ,input().split())
l=list(map(int ,input().split()))

dp=[float("inf")]*n
dp[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,abs(n-i))):
        dp[i+j]=min(dp[i]+abs(l[i]-l[i+j]),dp[i+j])
print(dp[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]
for i in range(1, n):
    arr = []
    for j in range(1, k + 1):
        if 0 <= i - j <= n:
            arr.append(dp[i - j] + abs(h[i - j] - h[i]))
    dp[i] = min(arr)
print(dp[n - 1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]
for i in range(1, n):
    arr = []
    for j in range(1, k + 1):
        if 0 <= i - j <= n:
            arr.append(dp[i - j] + abs(h[i - j] - h[i]))
    dp[i] = min(arr)
print(dp[n - 1])
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline())
memo = []
for i in range(n):
    m = int(stdin.readline())
    if m in memo: memo.pop(memo.index(m))
    else: memo.append(m)
print(len(memo))

### FIXED CODE ###

memo = set()
for i in range(int(input())):
    a = input()
    if a in memo: memo.remove(a)
    else: memo.add(a)
print(len(memo))
### BUGGY CODE ###

x = input()
while "ST" in x:
    x = x.replace("ST", "")
print(len(x))

### FIXED CODE ###

X = input()
box = []

for i in range(len(X)):
  if X[i] == "S": box.append(X[i])
  elif X[i] == "T":
    if len(box) == 0 or box[-1] != "S":
      box.append(X[i])
    else: box.pop(-1)
print(len(box))
### BUGGY CODE ###

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

def powmod(x, n,mod):
  ans = 1
  while n:
      if n % 2:
          ans *= x
          ans %= mod
      x *= x
      n >>= 1
  return ans

def cmbmod(n, r,mod):
  a=mod-2
  b=1
  for i in range(r):
   b*=(i+1)
   b%=mod
  ans1 = 1
  while a:
      if a % 2:
          ans1 *= b
          ans1 %= mod
      b *= b
      n >>= 1
  ans2 = 1
  for i in range(n-r):
   ans2 *= (i+r+1)
   ans2%=mod
  return (ans1*ans2)%mod

def cmbmod(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result %= mod
    return result

n,a,b=map(int,input().split())
print((powmod(2, n,10**9+7)-cmbmod(n,a,10**9+7)-cmbmod(n,b,10**9+7)-1)%(10**9+7))


### FIXED CODE ###

def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了

def cmbmod(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = result*int(numerator[k])%mod
    return result

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

c=powmod(2, n,10**9+7)
d=cmbmod(n,a,10**9+7)
e=cmbmod(n,b,10**9+7)
print((c-d-e-1)%(10**9+7))
### BUGGY CODE ###

import numpy as np

n = int(input())
A = list(map(int, input().strip().split()))
l = max(A) + 1
c = np.zeros(max(A) + 1,dtype=np.int64)
for a in A:
    c[a] += 1
#print('c',c)
q = np.zeros(c.max() + 1,dtype=np.int64)
s = 0
for ci in c:
    if ci > 0:
        if q[ci] <= 0:
            q[ci] = ci * (ci - 1) // 2
        s += q[ci]
        if q[ci-1] <= 0:
            q[ci-1] = (ci - 1) * (ci - 2) // 2
    #print(ci,q)
#print(q)
        
#print(s)
for i in range(n):
    #print(A[i],q[max(0,c[A[i]]-1)],q[max(0,c[A[i]]-2)])
    print(s - q[max(0,c[A[i]])] + q[max(0,c[A[i]]-1)])

### FIXED CODE ###

import numpy as np
import collections

n = int(input())
A = list(map(int, input().strip().split()))
C = collections.Counter(A)
#print(C)
s = 0
for v in C.values():
    s += v * (v-1) // 2
#print(s)
#print()
for i in range(n):
    print(s - C[A[i]] + 1)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
n = int(input())
s = list(map(int,input().split()))
ans = {}
#各番号がいくつずつあるのかを整理
#keyに番号、valueにその番号が書かれてあるボールの数
for i in range(n):
    if not s[i] in ans.keys():
        ans[s[i]] = 1
    else:
        ans[s[i]] += 1
#iC2の総和
answer = 0
for i in ans.values():
    answer += i*(i-1)//2
#answer-nC2+(n-1)C2 = answer-n+1
#nはans[s[i]],よって以下の出力で求められる
for i in range(n):
    print(answer-ans[s[i]]+1)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
List={}
x=0
for i in range(n):
    if not a[i] in List:
        List[a[i]] = 1
    else:
        List[a[i]]+=1
    
sigma=0
 
for key,item in List.items():
    sigma += item*(item-1)//2
for i in range(n):
    print(sigma-List[a[i]]+1)
### BUGGY CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))
l = []
i=0
while (a[i]-1) not in l:
    l.append(i)
    i = a[i]-1 
l.append(i)

pre = l.index(a[i]-1)  
loop = len(l)-pre
if pre+loop<k:
    k=(k-pre)%loop+pre
i = 0
for _ in range(k):
    i = a[i]-1
print(i+1)

### FIXED CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))
l = [0]*n
i=0
cnt=0
while l[i]==0:
    l[i] = a[i]
    i = a[i]-1 
    cnt += 1
start = i+1
i = 0
pre = 0
while i+1!=start:
    i = a[i]-1
    pre += 1
loop = cnt-pre
if pre+loop<k:
    k=(k-pre)%loop+pre
i = 0
for _ in range(k):
    i = a[i]-1
print(i+1)
### BUGGY CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    S.append(sorted(input()))
S = sorted(S)
for j in range(1,N):
    for k in range(1,j+1):
        if S[j] != S[j-k]:
            break
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    S.append(sorted(input()))
S = sorted(S)
a = 'sing'
for j in range(N):
    if a != S[j]:
        f = 0
        a = S[j]
    else:
        f += 1
        count += f
print(count)