Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
ans = N
V = [i for i in range(N)]
inp = []
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)





Fixed submission:
import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
V = [i for i in range(N)]
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        if visited[e]:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
ans = N
V = [i for i in range(N)]
inp = []
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)





Fixed submission:
import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
V = [i for i in range(N)]
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        if visited[e]:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)
Buggy python submission (verdict: Runtime Error):
# 明らかにdp、あるマスに乗っているときそれまでの履歴とかが全く意味をなさないから
# dp[i]: マス目iにいるときのそこまでの移動方法の合計
# dp[i+1] = dp[i]
# 最悪N*K掛かりそうな気がするけどnumpyなら早いんかなぁ？だとしたら簡単すぎる問題な気もするけど。。。？

N,K = map(int,input().split())
L = 998244353
LR = [0] * K
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]
import numpy as np
dp = np.array([0] * (N+1))

dp[1] = 1
for i in range(1,N+1):
    for l,r in LR:
        dp[i+l:i+r+1] += dp[i]
        dp[i+l:i+r+1] %= L

print(dp[N])





Fixed submission:
N,K = map(int,input().split())
L = 998244353
LR = [0] * K
# 累積和をとっていく。累積和の表を予め作っておき、どんどん足しておく
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]

AS = [0] * (N+2)
#for l,r in LR:
#    AS[l] += 1
#    AS[r+1] -= 1

A = [0] * (N+2)
A[1] = 1
A[2] = -1
for i in range(1,N+1):
    AS[i] = (AS[i-1] + A[i])%L
    rest = AS[i]
    for l,r in LR:
        if i+l>N:
            continue
        right = min(N+1,i+r+1)
        A[i+l] += rest
        A[right] += -rest

print(sum(A[1:N+1])%L)

Buggy python submission (verdict: Time Limit Exceeded):
# 明らかにdp、あるマスに乗っているときそれまでの履歴とかが全く意味をなさないから
# dp[i]: マス目iにいるときのそこまでの移動方法の合計
# dp[i+1] = dp[i]
# 最悪N*K掛かりそうな気がするけどnumpyなら早いんかなぁ？だとしたら簡単すぎる問題な気もするけど。。。？

N,K = map(int,input().split())
L = 998244353
LR = [0] * K
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]
import numpy as np
dp = np.array([0] * (N+1))

dp[1] = 1
for i in range(1,N+1):
    for l,r in LR:
        dp[i+l:i+r+1] += dp[i]
        dp[i+l:i+r+1] %= L

print(dp[N])





Fixed submission:
N,K = map(int,input().split())
L = 998244353
LR = [0] * K
# 累積和をとっていく。累積和の表を予め作っておき、どんどん足しておく
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]

AS = [0] * (N+2)
#for l,r in LR:
#    AS[l] += 1
#    AS[r+1] -= 1

A = [0] * (N+2)
A[1] = 1
A[2] = -1
for i in range(1,N+1):
    AS[i] = (AS[i-1] + A[i])%L
    rest = AS[i]
    for l,r in LR:
        if i+l>N:
            continue
        right = min(N+1,i+r+1)
        A[i+l] += rest
        A[right] += -rest

print(sum(A[1:N+1])%L)
Buggy python submission (verdict: Runtime Error):
X,K,D = map(int,input().split())

if K*D<=X:
    print(abs(X)-K*D)
    exit()
move_num_before = abs(X)//D
move_num_after = move_num_before+1
if (K - move_num_after)%2 == 0:
    print(abs(abs(X)-move_num_after*D))
    exit()
print(min(abs(X)-move_num_before*D))




Fixed submission:
X,K,D = map(int,input().split())
if K*D<=abs(X):
    print(abs(X)-K*D)
    exit()

move_num_before = abs(X)//D
move_num_after = move_num_before+1
if (K - move_num_after)%2 == 0:
    print(abs(abs(X)-move_num_after*D))
    exit()
print(abs(X)-move_num_before*D)
Buggy python submission (verdict: Time Limit Exceeded):
# どう考えてもK>5000でループが起きるので，
# dp[k][i]:= k回まで，移動したときの最大の値とすればよい
# -infで初期化
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

dp = [[-float('inf') for _ in range(N)] for __ in range(5000)]
for i,c in enumerate(C):
    dp[0][i] = 0
max_val = -float('inf')
if K<(5000-1):
    for i in range(K):
        for j in range(N):
            next_cell = P[j] - 1
            dp[i + 1][next_cell] = max(dp[i][j] + C[next_cell], dp[i + 1][next_cell])
            max_val = max(dp[i + 1][next_cell], max_val)
    print(max_val)
    exit()

for i in range(5000-1):
    for j in range(N):
        next_cell = P[j]-1
        dp[i+1][next_cell] = max(dp[i+1][next_cell] + C[next_cell], dp[i+1][next_cell])
        max_val = max(dp[i+1][next_cell],max_val)
print(max_val)



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

LC = [-1] * N
# Pが順列なので，結局それぞれのマスはループのどれかにいる事がわかる．あとは，ループの長さとループ1回分のコスト(a->a)を計算しておく
# ループ1回分のコストが正の場合はループをなるべく回す．負の場合は1回もループしないほうがいい．ただし最初のa->aは考慮する.
# 1回は最低でも動かないといけないから
max_score = -float('inf')
for i in range(N):
    Loop_len = 0
    Loop_cost =[]
    Loop_cost_sum = 0
    now = i
    while True:
        now = P[now] - 1
        Loop_len += 1
        Loop_cost_sum += C[now]
        Loop_cost.append(Loop_cost_sum)
        if now == i:
            break
    # それぞれのマスへのループによるコストのゲインと,最短でそこへいくまでの移動コストを計算してコストを決定する
    for i,lc in enumerate(Loop_cost):
        if K-(i+1)<0: # 行けないので
            continue
        possible_loop_num = (K-(i+1))//Loop_len
        cost = lc + max(0,Loop_cost_sum) * possible_loop_num
        max_score = max(cost,max_score)

print(max_score)
Buggy python submission (verdict: Runtime Error):
# Kこの街について，それぞれ横に串刺しにするか縦に串刺しにするかを選んでDFS
N = int(input())

L = [0] * N
for i in range(N):
    X,Y,P = map(int,input().split())
    L[i] = [X,Y,P]

def dfs(XL,YL,PL,K):
    # もう残りのやつがなかったら，０になる
    if not PL:
        return 0
    # 残りがあるけど，全部線を引き終えたら，残りのポイントたちについて距離を計算
    if len(XL)+len(YL)==K+2:
        score = 0
        for x,y,p in PL:
            x_dis = min([abs(x-xl) for xl in XL])
            y_dis = min([abs(y-yl) for yl in YL])
            min_dis = min(x_dis,y_dis)
            score += min_dis*p

        return score
    # それ以外のときは線を引いていく
    score = []
    for i, pl in enumerate(PL):
        x,y,_ = pl
        x = [x]
        y = [y]
        score.append(min(dfs(XL+x,YL,PL[:i]+PL[i+1:],K),dfs(XL,YL+y,PL[:i]+PL[i+1:],K)))
    return min(score)


for i in range(N+1):
    print((dfs([0],[0],L,i)))








Fixed submission:
N = int(input())
A = list(map(int,input().split()))
# 今の株価が前の日より上がるなら売る，次の日より下がるなら買う．
max_money = 1000
kabu = 0
money = 1000
for i in range(N):
    if i == 0:
        if A[i]<A[i+1]:
            kabu = int(1000/A[i])
            money -= kabu*A[i]
        continue
    if i == N-1:
        if A[i-1]<A[i]:
            money += kabu * A[i]
            kabu = 0
            max_money = max(max_money,money)
        break

    if A[i-1]<A[i]:
        money += kabu * A[i]
        kabu = 0
        max_money = max(max_money,money)
    if A[i]<A[i+1]:
        kabu += int(money/A[i])
        money -= A[i]*int(money/A[i])

print(max_money)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
print(A[0] + sum(A[1:1+(N-2)//2])*2 + ((N-2)%2)*A[1+1+(N-1)//2])

Fixed submission:
# 貪欲に大きい順に入れていって，入れる場所はもっとも周りが大きくなる場所
# この方針は正しいただし，値の取り出しだけではなく挿入が起こるので，優先度付きキュー（heap）を使う必要があるっ
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
import heapq
C = []
# heapは最小値しか取り出せないことに注意
heapq.heapify(C)
ans = 0
# 初期条件として2つの値を挿入する
heapq.heappush(C,-A[0])
for i in range(1,N):
    tmp = heapq.heappop(C)
    ans += -tmp
    heapq.heappush(C, -A[i])
    heapq.heappush(C, -A[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
# 全探索だったらだめだったN^2になるから
# まずAを最大限選ぶ，次にその時選べる最大のBを選ぶ
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 累積和
sumb = 0
Bs = [0]*M
for i,b in enumerate(B):
    sumb += B[i]
    Bs[i] = sumb
sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
import bisect
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=sum(A[:i])
        count += i
    if sum_time>K:
        continue
    ind = bisect.bisect_right(Bs,K-sum_time)
    count += ind
    max_count = max(max_count,count)

print(max_count)

Fixed submission:
# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
# 全探索だったらだめだったN^2になるから
# まずAを最大限選ぶ，次にその時選べる最大のBを選ぶ
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 累積和
suma = 0
sumb = 0

As = [0]*N
for i,a in enumerate(A):
    suma += A[i]
    As[i] = suma

Bs = [0]*M
for i,b in enumerate(B):
    sumb += B[i]
    Bs[i] = sumb
sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
import bisect
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=As[i-1]
        count += i
    if sum_time>K:
        continue
    ind = bisect.bisect_right(Bs,K-sum_time)
    count += ind
    max_count = max(max_count,count)

print(max_count)

Buggy python submission (verdict: Time Limit Exceeded):
# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
N,M,K = map(int,input().split())

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

sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=sum(A[:i])
        count += i

    for j in range(M+1):
        if j == 0:
            sum_time += 0
        else:
            sum_time += sum(B[:j])
            count += j
        if sum_time > K:
            break
        max_count = max(max_count,count)
        sum_time -= sum(B[:j])
        count -= j

print(max_count)

Fixed submission:
# 解法 全探索をする，上から読んでる冊数をi,jとしてKを超えない範囲で最大のものを週つ力すれば良い
# 全探索だったらだめだったN^2になるから
# まずAを最大限選ぶ，次にその時選べる最大のBを選ぶ
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
# 累積和
suma = 0
sumb = 0

As = [0]*N
for i,a in enumerate(A):
    suma += A[i]
    As[i] = suma

Bs = [0]*M
for i,b in enumerate(B):
    sumb += B[i]
    Bs[i] = sumb
sum_time=0
max_count = 0
count = 0
# i,jは実際に読んでいる数とする
import bisect
for i in range(N+1):
    count = 0
    if i ==0:
        sum_time=0
    else:
        sum_time=As[i-1]
        count += i
    if sum_time>K:
        continue
    ind = bisect.bisect_right(Bs,K-sum_time)
    count += ind
    max_count = max(max_count,count)

print(max_count)
Buggy python submission (verdict: Time Limit Exceeded):
# (1,2,3,4,5..,N) + (1,2,3,4,...,N/2) * 2 + (1,2,...,N/3) * 3 + ...+(1,) * N
# 累積和を使うことでO(1)でそれぞれの計算をする．N回ループをするので，合計O(N)の計算量で終了する

N = int(input())

S=[0]*(N+1)
for i in range(1,N+1):
    S[i] = S[i-1] + i

ans = 0
for i in range(1,N+1):
    ind = int(N/i)
    ans += S[ind] * i

print(ans)



Fixed submission:
# (1,2,3,4,5..,N) + (1,2,3,4,...,N/2) * 2 + (1,2,...,N/3) * 3 + ...+(1,) * N
# 累積和を使うことでO(1)でそれぞれの計算をする．N回ループをするので，合計O(N)の計算量で終了する

N = int(input())

S=[0]*(N+1)
for i in range(1,N+1):
    S[i] = S[i-1] + i

ans = 0
for i in range(1,N+1):
    ind = int(N/i)
    ans += S[ind] * i

print(ans)

Buggy python submission (verdict: Runtime Error):
# 170Dと同じような方法g使える．ただしN=10^7なので，うまくわからないけどなぁ...
N = int(input())
Res = [0] * (N+1)
import numpy as np
Res = np.array(Res)
for i in range(1,N+1):
    Res[::i] += 1
Range = np.arange(N+1)
Res = Res * Range
print(np.sum(Res))


Fixed submission:
# (1,2,3,4,5..,N) + (1,2,3,4,...,N/2) * 2 + (1,2,...,N/3) * 3 + ...+(1,) * N
# 累積和を使うことでO(1)でそれぞれの計算をする．N回ループをするので，合計O(N)の計算量で終了する

N = int(input())

S=[0]*(N+1)
for i in range(1,N+1):
    S[i] = S[i-1] + i

ans = 0
for i in range(1,N+1):
    ind = int(N/i)
    ans += S[ind] * i

print(ans)
Buggy python submission (verdict: Runtime Error):
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()
first = True
for a in A:
    if L[a] ==2:
        continue
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)







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

for i,x in enumerate(X):
    if x == 0:
        print(i+1)
Buggy python submission (verdict: Time Limit Exceeded):
# なんか身長順でソートすればいいんじゃない？
# 身長差でありえるのは1〜Nなので，身長差が1になるエージェントの組み合わせをだして，それぞれの身長差について調べる
# でも結局全探索になるか？やっぱり配列を作ると同時に答えが独立してうまく求まるようなのがいいよね
# j-i = Aj+Ai となるのが求めるもの，これを変換してiとjの式のみに分離すると，うまく配列を作るだけでうまくいくようになる
# j-Aj = Ai+i となる．こうすると独立しているので,X=i-Ai,Y=Ai+iを作り，setもしくはdictで探索すればすぐです！
# i==jのときはi-i == Ai+Ai が絶対に成立しないので問題ない

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

X=[i+1-A[i] for i in range(N)]
Y=[i+1+A[i] for i in range(N)]
#Y=set(Y) # set使うと同じ要素が減るのでだめ！！！
dicY=dict()
for y in Y:
    if not y in dicY:
        dicY[y]=1
    else:
        dicY[y]+=1
count=0
for x in X:
    if x in Y:
        count+=dicY[x]
print(count)


Fixed submission:
# なんか身長順でソートすればいいんじゃない？
# 身長差でありえるのは1〜Nなので，身長差が1になるエージェントの組み合わせをだして，それぞれの身長差について調べる
# でも結局全探索になるか？やっぱり配列を作ると同時に答えが独立してうまく求まるようなのがいいよね
# j-i = Aj+Ai となるのが求めるもの，これを変換してiとjの式のみに分離すると，うまく配列を作るだけでうまくいくようになる
# j-Aj = Ai+i となる．こうすると独立しているので,X=i-Ai,Y=Ai+iを作り，setもしくはdictで探索すればすぐです！
# i==jのときはi-i == Ai+Ai が絶対に成立しないので問題ない

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

X=[i+1-A[i] for i in range(N)]
Y=[i+1+A[i] for i in range(N)]
#Y=set(Y) # set使うと同じ要素が減るのでだめ！！！
dicY=dict()
for y in Y:
    if not y in dicY:
        dicY[y]=1
    else:
        dicY[y]+=1
count=0
for x in X:
    if x in dicY:
        count+=dicY[x]
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
P = []
for _ in range(N):
    prize = input()
    if not prize in P:
        P.append(prize)
print(len(P))



Fixed submission:
N=int(input())
P = []
# 26進数で表していこう
for _ in range(N):
    prize = input()
    prize_num = 0
    for i,p in enumerate(prize[::-1]):
        prize_num += 26**i * ord(p)
    P.append(prize_num)

P.sort()
now=-1
count = 0
for p in P:
    if not p==now:
        now=p
        count+=1

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N=len(S)
M = [0 for _ in range(2019)]
# 0は予め右端に一個あるとする
M[0]+=1
for i,s in enumerate(S):
    new = int(S[i:])%2019
    M[new] += 1
count = 0
for m in M:
    count += int(m*(m-1)/2)
print(count)


Fixed submission:
S = input()
N=len(S)
M = [0 for _ in range(2019)]
# 0は予め右端に一個あるとする
M[0]+=1
old = 0
for i in range(N):
    new_s = int(S[N-1-i])*pow(10,i,2019)
    new = (new_s + old) % 2019
    M[new] += 1
    old = new
count = 0
for m in M:
    count += int(m*(m-1)/2)
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N,P = map(int, input().split())
S = list(map(int,input()))

if P == 2 or P==5:
    # 左端が2,5となる文字列を見つけてくる
    ans=0
    for i,s in enumerate(S):
        if s%P==0:
            ans+=i+1
    print(ans)
else:
    # mod P の和を足していく
    ans = 0
    from collections import deque
    U=deque()
    U_sum=deque()
    ten = 1
    for i,s in enumerate(S[::-1]):
        new = (s*ten) % P
        U.appendleft(s*10**i % P)
        ten *= 10
        ten %= P
    same_p = [0 for _ in range(P)]
    for i in range(len(U)):
        u = U[-i-1]
        if i == 0:
            U_sum.appendleft(u)
            same_p[u]+=1
            continue
        new = (U_sum[-i]+u) % P
        U_sum.appendleft(new)
        same_p[new] += 1

    for i,p in enumerate(same_p):
        if i == 0:
            # 自分だけでも選択できるから
            ans += p
        ans += int(p*(p-1) / 2)
    print(ans)

















Fixed submission:
import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read

n, p = [int(i) for i in readline().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i, c in enumerate(s):
        if int(c) % p == 0:
            ans += i + 1
    print(ans)
    exit()

res = [0] * p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i * t
    now %= p
    res[now] += 1
    t = t * 10 % p

ans = 0
for i in res:
    ans += i * (i - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# k本の花束の作り方は正直わからない
# 2**n-1通りのはなの選び方があるのは間違いない
# その中からごうけいがa,bになるものは除く
# nCa+nCb何じゃない？
# 組み合わせ数を計算するだけならめんどくさいライブラリを使わなくてもmathのfactorialで階乗を計算すれば良い
from functools import lru_cache
import math
n,a,b = map(int,input().split())


# これはfactorialの計算がやばいことになるので(10**9+7)で割りながらやっていこう
# ホントはここの10^9のループが重いみたいだなぁ
# なんか２分累乗法を使わないといけないらしい．．．実はpythonではmathのpowに標準でついています！
Big = 10**9 + 7
@lru_cache()
def cal_pow(num,w):
    if num==1:
        return w
    elif num==0:
        return 1
    else:
        half = num // 2
        rest = num % 2
        res = cal_pow(half,w) **2 * cal_pow(rest,w)
        res %= Big
        return res
all = cal_pow(n,2)-1

a_comb = 1
for i in range(a):
    # 逆元
    inv_a = cal_pow(Big-2,a-i)
    a_comb *= (n-i)*inv_a
    a_comb %= Big
b_comb = 1
for i in range(b):
    # 逆元
    inv_b = cal_pow(Big-2,b-i)
    b_comb *= (n-i)*inv_b
    b_comb %= Big
res = (all - a_comb - b_comb)
while res<0:
    res += Big
print(res)

# また出たぞ！！逆元だぁ...
# 1/x の mod p(素数) は x^(p-2)になるらしい．(フェルマーの小定理より...)
# mod(1/x) = mod(x^(p-2))






Fixed submission:
# k本の花束の作り方は正直わからない
# 2**n-1通りのはなの選び方があるのは間違いない
# その中からごうけいがa,bになるものは除く
# nCa+nCb何じゃない？
# 組み合わせ数を計算するだけならめんどくさいライブラリを使わなくてもmathのfactorialで階乗を計算すれば良い
from functools import lru_cache
import math
n,a,b = map(int,input().split())


# これはfactorialの計算がやばいことになるので(10**9+7)で割りながらやっていこう
# ホントはここの10^9のループが重いみたいだなぁ
# なんか２分累乗法を使わないといけないらしい．．．実はpythonではmathのpowに標準でついています！
Big = 10**9 + 7
#@lru_cache()
def cal_pow(num,w):
    if num==1:
        return w
    elif num==0:
        return 1
    else:
        half = num // 2
        rest = num % 2
        res = cal_pow(half,w) **2 * cal_pow(rest,w)
        res %= Big
        return res
#all = cal_pow(n,2)-1
all = pow(2,n,Big)-1

a_comb = 1
for i in range(a):
    # 逆元
    # inv_a = cal_pow(Big-2,a-i)
    inv_a = pow(a-i,Big-2,Big)
    a_comb *= (n-i)*inv_a
    a_comb %= Big
b_comb = 1
for i in range(b):
    # 逆元
    #inv_b = cal_pow(Big-2,b-i)
    inv_b = pow(b-i,Big-2,Big)
    b_comb *= (n-i)*inv_b
    b_comb %= Big
res = (all - a_comb - b_comb)
while res<0:
    res += Big
print(res)

# また出たぞ！！逆元だぁ...
# 1/x の mod p(素数) は x^(p-2)になるらしい．(フェルマーの小定理より...)
# mod(1/x) = mod(x^(p-2))
Buggy python submission (verdict: Time Limit Exceeded):
# 難易度 484
# 800~
# 解法805,pi~pjの合計が最大となる区間を求める
# Kの区間が固定されているので0~K-1 -> N-K~N-1を足していイケば良い
# 2~10^5こしかNがないので，せいぜいO(N)で終わるので十分
# 期待値の計算をいちいちしていたら，計算量がもタンクなるかも？最初から計算しておくか

N, K = map(int,input().split())
P = list(map(int,input().split()))
P_MAX = 10**3
E = [0]*(P_MAX+1)
for i in range(1,P_MAX+1):
    E[i] = sum([1/i * j for j in range(1,i+1)])

ans = 0
for i in range(0,N-K+1):
    ans = max(sum([E[l] for l in P[i:i+K]]), ans)
print(ans)




Fixed submission:
# 難易度 484
# 800~
# 解法805,pi~pjの合計が最大となる区間を求める
# Kの区間が固定されているので0~K-1 -> N-K~N-1を足していイケば良い
# 2~10^5こしかNがないので，せいぜいO(N)で終わるので十分
# 期待値の計算をいちいちしていたら，計算量がもタンクなるかも？最初から計算しておくか
# なぜTLEが起こるのかがよくわからない

N, K = map(int,input().split())
P = list(map(int,input().split()))
P_MAX = 10**3
E = [0]*(P_MAX+1)
for i in range(1,P_MAX+1):
    E[i] = sum([1/i * j for j in range(1,i+1)])

ans = 0
for i in range(0,N-K+1):
    if i == 0:
        old = sum([E[l] for l in P[0:0+K]])
        ans = old
        continue
    new = old - E[P[i-1]] + E[P[i+K-1]]
    ans = max(ans,new)
    old = new
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
P=list(map(int,input().split()))
import math
min_num = math.inf
count=0
for p in P:
    if p <= min_num:
        min_num = p
        count += 1
print(count)


Fixed submission:
N=int(input())
P=list(map(int,input().split()))
count=0
for i,p in enumerate(P):
    if i ==0:
        min_num=p
        count += 1
        continue
    if p <= min_num:
        min_num = p
        count += 1
print(count)

Buggy python submission (verdict: Runtime Error):
N=int(input())
P=list(map(int,input().split()))
import math
min_num = math.inf
count=0
for p in P:
    if p <= min_num:
        min_num = p
        count += 1
print(count)



Fixed submission:
N=int(input())
P=list(map(int,input().split()))
count=0
for i,p in enumerate(P):
    if i ==0:
        min_num=p
        count += 1
        continue
    if p <= min_num:
        min_num = p
        count += 1
print(count)