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

import math
import heapq

def dijkstra(v,s,path):
    inf = float('inf')

    # 距離をinfで初期化
    d = [inf for i in range(v)]
    d[s] = 0

    # sへの距離は0
    q = [[0,s]]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば
    # p[1]から行ける
    while q:
        p = heapq.heappop(q)

        # 頂点p[1]までの距離がheapないのp[1]までの距離より小さい場合、continue
        if d[p[1]]<p[0]:
            continue

        # 頂点p[1]から伸びる、全ての辺の距離を確認
        for i in range(len(path[p[1]])):
            # 頂点p[1]から行ける頂点の距離がp[1]までの距離とp[1]からの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d

xs,ys,xt,yt = map(int,input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]

barrier = [[xs,ys,0]] + barrier + [[xt,yt,0]]
n+=2

path = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        length = max(math.sqrt((barrier[i][0]-barrier[j][0])**2 + (barrier[i][1]-barrier[j][1])**2)-barrier[i][2]-barrier[j][2],0)
        path[i].append([length,j])
        path[j].append([length,i])

d = dijkstra(n,0,path)

print(d[-1])

### FIXED CODE ###

import math
import heapq

def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

xs,ys,xt,yt = map(int,input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]

barrier = [[xs,ys,0]] + barrier + [[xt,yt,0]]
n+=2

path = [[] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        length = max(math.sqrt((barrier[i][0]-barrier[j][0])**2 + (barrier[i][1]-barrier[j][1])**2)-barrier[i][2]-barrier[j][2],0)
        path[i].append([length,j])
        path[j].append([length,i])

d = dijkstra(0,path)

print(d[-1])
### BUGGY CODE ###

n = int(input())
b = {}
for i in range(n):
    temp = input()
    if temp not in b:
        b[temp] = 1
    else:
        b[temp] += 1

list1 = sorted(b.items(), key=lambda x: x[1], reverse=True)

a = 0
list2=[]
while a<len(list1) and list1[0][1] == list1[a][1]:
    list2.append(list1[a][0])
    list2.sort()
    a += 1

for a in list2:
    print(a)


### FIXED CODE ###

n = int(input())
b = {}
for i in range(n):
    temp = input()
    if temp not in b:
        b[temp] = 1
    else:
        b[temp] += 1

list1 = sorted(b.items(), key=lambda x: x[1])

a = len(list1)-1
temp = len(list1)-1
list2 = []
while a >= 0 and list1[temp][1] == list1[a][1]:
    list2.append(list1[a][0])
    a -= 1
list2.sort()

for a in list2:
    print(a)
### BUGGY CODE ###

N,D,A = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort()
ans = 0
for i in range(N):
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = i+1
    while j < N and L[j][0] <= L[i][0]+2*D:
        L[j][1] -= num*A
        j += 1

print(ans)

### FIXED CODE ###

N,D,A = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
L.sort()
X = []
for i in range(N):
    X.append(L[i][0])

import bisect
ans = 0
for i in range(N):
    L[i][1] -= bit.sum(N)-bit.sum(i)
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = bisect.bisect_right(X, L[i][0]+2*D)
    if j > i:
        bit.add(j, num*A)
    
print(ans)
### BUGGY CODE ###

H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)
for q in range(int(input())):
    l, r = [int(x) for x in input().split()]
    m = 0
    while l != r:
        m += abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
        l = l + D
    print(m)


### FIXED CODE ###

H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [0] * (H * W + 1)
for i in range(D):
    x = H * W - i - D
    r = 0
    while x > 0:
        table[x] = abs(A[x][0] - A[x+D][0]) + abs(A[x][1] - A[x+D][1]) \
                   + r
        r = table[x]
        x -= D
for q in range(int(input())):
    l, r = [int(x) for x in input().split()]
    print(table[l] - table[r])
### BUGGY CODE ###

N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    C[p] += x

stack = [1]
list = []
while len(stack) > 0:
    a = stack.pop(0)
    list.append(a)
    for b in G[a]:
        if b not in list:
            stack.append(b)
            C[b] += C[a]
C.pop(0)
print(*C)

### FIXED CODE ###

N,Q = map(int,input().split())
G = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*(N)
for i in range(Q):
    p,x = map(int,input().split())
    C[p-1] += x
from collections import deque
d=deque()
d.append(0)
t = [False]*(N)
t[0] = True
while d:
    a = d.popleft()
    for b in G[a]:
        if not t[b]:
            t[b] = True
            d.append(b)
            C[b] += C[a]
print(*C)
### BUGGY CODE ###

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

b=0
r=0
while N>0:
    N-=A
    b+=A
    if N<=0:
        b+=N
        break

    N-=B
    r+=B
    if N<=0:
        break

print(b)

### FIXED CODE ###

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

C=A+B
d=N//C
N -= C*d

b=0
r=0
while N>0:
    N-=A
    b+=A
    if N<=0:
        b+=N
        break

    N-=B
    r+=B
    if N<=0:
        break

print(b+d*A)
### BUGGY CODE ###

N,M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]

for i in range(M):
  index = A.index(max(A))
  A[index] = A[index]//2

print(sum(A))


### FIXED CODE ###

import heapq

N,M = (int(i) for i in input().split())
A = [int(i) * (-1) for i in input().split()]
heapq.heapify(A)

for i in range(M):
  tmp = heapq.heappop(A)
  tmp = ((tmp * -1)//2) * -1
  heapq.heappush(A,tmp)

print((-1)*sum(A))
### BUGGY CODE ###

list = input().split(" ")
N = int(list[0])
K = int(list[1])
list_hp = input().split(" ")
list_hp = [int(i) for i in list_hp]
list_hp = sorted(list_hp,reverse=True)

if K < N:
    for i in range(K):
        list_hp.pop(0)
    print(sum(list_hp))
    
else:
    print(0)

### FIXED CODE ###

list = input().split(" ")
N = int(list[0])
K = int(list[1])
list_hp = input().split(" ")
list_hp = [int(i) for i in list_hp]
list_hp = sorted(list_hp)

if K < N:
    sum = 0
    for i in range(N-K):
        sum = sum + list_hp[i]
    print(sum)
else:
    print(0)
### BUGGY CODE ###

import sys
import math
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = np.array([last - x for x in X[:-1]]) #最後までの距離
Y = np.array([limit // i for i in range(1, N)])
Z = (X * Y)%MOD
answer = Z.sum()%MOD
print(answer)

### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
v=[list(map(int,input().split())) for i in range(q)]
count=0
for i in range(q):
    for j in range(v[i][0]-1,v[i][1]-1):
        if s[j]=='A':
            if s[j+1]=='C':
                count+=1
            else:
                pass
    print(count)
    count=0

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
v=[list(map(int,input().split())) for i in range(q)]
r=[0]*n
count=0
a=0
for i in range(n-1):
    r[i]=a
    if s[i]=='A':
        if s[i+1]=='C':
            a+=1
        else:
            pass
r[n-1]=a
for i in range(q):
    print(r[v[i][1]-1]-r[v[i][0]-1])
### BUGGY CODE ###

import numpy as np
import itertools

N, A, B = list(map(int, input().split()))
V = np.array(list(map(int, input().split())))
V.sort()
V[:] = V[::-1]

def nCp(n, p):
    return(len(list(itertools.combinations(np.arange(n), p))))

d = V[A-1]
# unless all equal, we only need A
if d == V.max():
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    print(V[:A].mean())
    res = nCp(d_eq_cnt, A)
    res_sum = nCp(d_eq_cnt, A)
    for k in range(1, min(B, d_eq_cnt) + 1 - A):
        res = res * (d_eq_cnt - (A+k-1)) // (A+k)
        res_sum += res
    print(res_sum)
    
    
else:
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    d_lq_cnt = np.count_nonzero(V > d)
    print(V[:A].mean())
    print(nCp(d_eq_cnt, A - d_lq_cnt))



### FIXED CODE ###

import numpy as np

N, A, B = list(map(int, input().split()))
V = np.array(list(map(int, input().split())))
V.sort()
V[:] = V[::-1]

def fac(n):
    return 1 if n<=1 else n*fac(n-1)
        
def nCr(n, r):
    return fac(n) // fac(n-r) // fac(r)

d = V[A-1]
# unless all equal, we only need A
if d == V.max():
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    res = nCr(d_eq_cnt, A)
    res_sum = res
    for k in range(1, min(B, d_eq_cnt) + 1 - A):
        res = res * (d_eq_cnt - (A+k-1)) // (A+k)
        res_sum += res
    print(V[:A].mean())
    print(res_sum)
    
    
else:
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    d_lq_cnt = np.count_nonzero(V > d)
    print(V[:A].mean())
    print(nCr(d_eq_cnt, A - d_lq_cnt))
### BUGGY CODE ###

N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = [[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
	a = A[i-1]
	for j in range(0, S+1):
		if a > j:
			dp[i][j] = 2*dp[i-1][j] % MOD
		else:
			dp[i][j] = (2*dp[i-1][j] + dp[i-1][j-a]) % MOD
print(dp[N][S])

### FIXED CODE ###

N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = [[0 for j in range(S+1)] for i in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
	a = A[i-1]
	for j in range(0, S+1):
		if a > j:
			dp[i][j] = 2*dp[i-1][j] % MOD
		else:
			dp[i][j] = (2*dp[i-1][j] + dp[i-1][j-a]) % MOD
print(dp[N][S])
### BUGGY CODE ###

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

if 0 in A:
  sum = 0
sum = 1
ans = 0
for x in A:
  sum *= x
  if sum > 1000000000000000000:
    ans = -1
  if sum == 0:
    ans = 0
    break

if ans < 0:
  print(ans)
else:
  print(sum)

### FIXED CODE ###

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

sum = 1
if 0 in A:
  sum = 0
ans = 0
for x in A:
  sum *= x
  if sum > 1000000000000000000:
    ans = -1
    break
  if sum == 0:
    ans = 0
    break

if ans < 0:
  print(ans)
else:
  print(sum)
### BUGGY CODE ###

def mygets():
    return list(map(int, input().strip().split()))

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

xt = 0
for _ in range(1, n):
    xt += x
    bsum = 0
    for j in range(n):
        b2[j] = min(a[j], b1[(j + n - 1) % n])
        bsum += b2[j]
    ans = min(ans, bsum + xt)
    b1, b2 = b2, b1

print(ans)

### FIXED CODE ###

def mygets():
    return list(map(int, input().strip().split(' ')))

n, x = mygets()
a = mygets()

b1 = a

ans = sum(a)

def f(k, u):
    j = k - 1
    if j < 0:
        j = n - 1
    w = b1[j]
    if u < w:
        return u
    return w

for i in range(1, n):
    b2 = [f(k, u) for k, u in enumerate(a)]
    ans = min(ans, sum(b2) + i * x)
    b1 = b2

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

import sys
def check(S):
    stop = True
    if len(S) < 2:
        print(base_S_length - len(S))
        sys.exit()
    for i in range(len(S) - 1):
        if (S[i] + S[i + 1]) == 1:
            S[i] = S[i + 1] = 2
            stop = False    
    if stop:
        print(base_S_length - len(S))
        sys.exit()
    S = [i for i in S if i != 2]
    #S = list(filter(lambda a: a != 2, S))
    check(S)

S = list(map(int, list(input())))
base_S_length = len(S)
check(S)

### FIXED CODE ###

def main():
    S = list(map(int, list(input())))

    cnt1 = sum(S)
    cnt0 = len(S) - cnt1
    print(2 * min(cnt0, cnt1))


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

n,q = map(int,input().split())
s = input()
for i in range(1,q+1):
    l,r = map(int,input().split())
    ss = list(s[l-1:r])
    ans = 0
    for i in range(len(ss)-1):
        if ss[i] == "A" and ss[i+1] == "C":
            ans+=1
    print(ans)


### FIXED CODE ###

N,Q = map(int,input().split())
S = list(input())
cum_sum = [0]*N
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l,r = map(int,input().split())
    print(cum_sum[r-1] - cum_sum[l-1])
### BUGGY CODE ###

N, K = map(int, input().split())
P = [list(input().split()) for i in range(N)] # list of [x, y, c] as string
ans = 0
for x0 in range(K * 2):
    for y0 in range(K):
        count = 0
        for i in range(N):
            x = int(P[i][0])
            y = int(P[i][1])
            c = P[i][2]
            f = 1 # 希望が叶うかどうかのフラグ
            if ((x - x0) % (K * 2)) in range(K):
                if ((y - y0) % (K * 2)) in range(K):
                    if c == "W":
                        f = 0
                else:
                    if c == "B":
                        f = 0
            else:
                if ((y - y0) % (K * 2)) in range(K):
                    if c == "B":
                        f = 0
                else:
                    if c == "W":
                        f = 0
            if f == 1:
                count += 1
        if count > ans:
            ans = count
print(ans)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
_3K = 3 * K
_2K = 2 * K
G = np.zeros((_2K, _3K), dtype='int64') # 後から 2K * K に圧縮する
for _ in range(N):
    x, y, c = input().split()
    x, y = int(x), int(y)
    # 2K * 2K の黒の希望に置き換え
    if c == 'B':
        x = x % _2K
        y = y % _2K
    else:
        x = (x + K) % _2K
        y = y % _2K
    # さらに、 2K * K の黒の希望に圧縮する
    if (y >= K) and (x >= K):
        x -= K
        y -= K
    if (y >= K) and (x < K):
        x += K
        y -= K
    # 塗り方は右下がどのマスに来るかの 2K * K 通り
    # → 最終的に 2K * K のグリッドで表すことができる
    # 各希望を満たす塗り方は K * K 通り
    # → 2K * K のグリッド内の希望を満たす K * K マスに 1 を加算すれば、
    #   全希望の加算後には各マス＝各塗り方がいくつの希望を満たすかがわかる
    # K * K マスに 1 を加算するには o(K^2) かかってしまう
    # → いもす法を使う
    # 塗り方を 3K * 2K の範囲で考えて累積和をとった後、 2K * K の範囲に圧縮する
    G[y, x] += 1
    G[y+K, x+K] += 1
    G[y+K, x] -= 1
    G[y, x+K] -= 1

# 3K * 2K の範囲の累積和をとる
G = G.cumsum(axis=1).cumsum(axis=0)
# 2K * K の範囲に圧縮
G = G[:K, :_2K] + G[K:_2K, K:_3K] + np.concatenate((G[:K, _2K:_3K], G[K:_2K, :K]), axis=1)
ans = G.max()
print(ans)
### BUGGY CODE ###

#!/usr/bin/python

import sys
from pprint import pprint

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2) % (10**9 + 7)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2) % (10**9 + 7)


def solve(n, a):

    zero_count = [0] * 60
    for a_i in a:
        binary = format(a_i, '060b')

        for j, b_j in enumerate(binary):
            zero_count[j] += int(b_j)

    ans = 0
    for i, count in enumerate(zero_count[::-1]):
        # ans += (2**i) * (count * (n - count)) 
        ans += pow(2, i) * (count * (n - count)) 
        ans %= 10**9 + 7
    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    a = map(int, sys.stdin.readline().strip().split(" "))
    
    solve(n, a)

### FIXED CODE ###

import sys
from pprint import pprint

mod = 10**9 + 7

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2) % mod
    else:
        return (x * pow_r(x ** 2, (n - 1) // 2)) % mod


def solve(n, a):

    zero_count = [0] * 60
    for a_i in a:
        # binary = format(a_i, '060b')
        # for j, b_j in enumerate(binary):
        #    zero_count[j] += int(b_j)
        for j in range(61):
            if a_i >> j & 1:
                zero_count[j] += 1

    ans = 0
    # for i, count in enumerate(zero_count[::-1]):
    for i, count in enumerate(zero_count):
        # ans += (2**i) * (count * (n - count)) 
        ans += pow_r(2, i) * (count % mod) * ((n - count) % mod) 
        ans %= mod
    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    a = map(int, sys.stdin.readline().strip().split(" "))
    
    solve(n, a)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

k = int(input())

s = 7
i = 1
if k % 2 != 0:
    while s % k != 0:
        s += 7*10**i
        i += 1
    print(i)    
if k %2 == 0: 
    print(-1)

### FIXED CODE ###

k = int(input())
a = 0
for i in range(k):
    a = (a*10+7)%k
    if a == 0:
        print(i+1)
        exit()
print(-1)
### BUGGY CODE ###

import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    facts = [m.factorial(i) % mod for i in range(n+1)]
    r = 0

    for i in range(1, n+1):
        if i != a and i != b:
            r += int((facts[n] / facts[n-i] / facts[i]))

    r %= mod
    return r

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

### FIXED CODE ###

import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    r = repeatSquare(2, n, mod) - 1
    r -= factMod(n, n - a + 1, mod) * repeatSquare(factMod(a, 1, mod), mod - 2, mod)
    r -= factMod(n, n - b + 1, mod) * repeatSquare(factMod(b, 1, mod), mod - 2, mod)
    r %= mod
    return r

def repeatSquare(n, p, m):
    if p == 0:
        return 1

    if p % 2 == 0:
        tmp = repeatSquare(n, p/2, m) % m
        return tmp * tmp % m

    return n * repeatSquare(n, p-1, m) % m

def factMod(n, r, m):
    res = n

    while n > r:
        n -= 1
        res *= n
        res %= m

    return res

if __name__ == "__main__":
    
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)
### BUGGY CODE ###

def make_prime_table(n):
    sieve = [True] * (n + 1)
    sieve[0] = False
    sieve[1] = False
    for i in range(4, n + 1, 2):
        sieve[i] = False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if not sieve[i]:
            continue
        for j in range(i * i, n + 1, i * 2):
            sieve[j] = False
    return sieve


def f(X):
    t = []
    a = X
    while a != 1:
        if len(t) != 0 and t[-1][0] == prime_table[a]:
            t[-1][1] += 1
        else:
            t.append([prime_table[a], 1])
        a //= prime_table[a]
    result = 1
    for _, n in t:
        result *= n + 1
    return result


N = int(input())

prime_table = make_prime_table(N)
result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)


### FIXED CODE ###

# エラトステネスの篩
N = int(input())

sieve = [0] * (N + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, N + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, N + 1, i):
        if sieve[j] == 0:
            sieve[j] = i


def f(K):
    t = []
    a = K
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    result = 1
    for _, n in t:
        result *= (n + 1)
    return result


result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
rain = [0]*n
sign = [1, -1]
for i in range(n):
    s = 0
    for j in range(n):
        rain[i] += sign[s] * a[(i+j)%n]
        s = (s+1)%2
print(*rain)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
rain = [0]*n
rain[0] += sum([a[i] for i in range(n) if i%2 == 0]) - sum([a[i] for i in range(n) if i%2 == 1])
for i in range(n-1):
    rain[i+1] = 2 * (a[i] - rain[i]//2)
print(*rain)
### BUGGY CODE ###

import bisect

N,K = map(int,input().split())
src = [int(input()) for i in range(N)]
if N == 1:
    print(int(src[0]>=K))
    exit()

cums = [0]
for a in src:
    cums.append(cums[-1] + a - K)

s_cums = sorted(cums)
cmp = []
for a in cums:
    i = bisect.bisect(s_cums, a)
    cmp.append(i-1)

bit = [0] * (N+1)
def bit_add(a,w):
    x = a
    while x <= N:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

ans = 0
for a in cmp:
    ans += bit_sum(a)
    bit_add(a, 1)
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
src = [int(input()) for i in range(N)]

cums = [(0,1)]
for i,a in enumerate(src):
    cums.append((cums[-1][0] + a - K, i+2))

bit = [0] * (N+2)
def bit_add(a,w):
    x = a
    while x <= N:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

ans = 0
for i,a in sorted(cums):
    ans += bit_sum(a-1)
    bit_add(a, 1)
print(ans)