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

n,a,b=map(int,input().split())
mod=10**9+7
def C(n,r,mod):
    r=min(r,n-r)
    bunsi=bunbo=1
    for i in range(1,r+1):
        bunsi*= (n+1-i) %mod
        bunbo*= i %mod
    return bunsi * pow(bunbo,mod-2,mod) %mod
print(pow(2,n,mod)-1-C(n,a,mod)-C(n,b,mod) %mod)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def C(n,r,mod):
    r=min(r,n-r)
    bunsi=bunbo=1
    for i in range(1,r+1):
        bunsi*= (n+1-i)%mod ;bunsi%=mod
        bunbo*= i %mod  ;bunbo%=mod
    return bunsi * pow(bunbo,mod-2,mod) %mod
print((pow(2,n,mod)-1-C(n,a,mod)-C(n,b,mod)) %mod)
### BUGGY CODE ###

import collections

N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
c=collections.Counter(A)
x=2*c[A[0]]-1
if x>N-1:
    print(sum(A)-A[0])
    exit()
ans=A[0]*(2*c[A[0]]-1)
while x<N-1:
    A=A[c[A[0]]:]
    x+=2*c[A[0]]
    ans+=A[0]*2*c[A[0]]
y=x-N+1
ans-=y*A[0]
print(ans)






        




    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
ans=0
for i in range(1,N):
    ans+=A[i//2]
print(ans)
### BUGGY CODE ###

import heapq

X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
heapq.heapify(P)
heapq.heapify(Q)

while(True):
    if P[0] >= R[0] and Q[0] >= R[0]:
        break
    if P[0] > Q[0]:
        if Q[0] < R[0]:
            heapq.heappop(Q)
            heapq.heappush(Q, R[0])
    else:
        if P[0] < R[0]:
            heapq.heappop(P)
            heapq.heappush(P, R[0])
    R = R[1:]
    if len(R) == 0:
        break
print(sum(P) + sum(Q))

### FIXED CODE ###

import heapq
 
X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
heapq.heapify(P)
heapq.heapify(Q)
i = 0
while(True):
    if P[0] >= R[i] and Q[0] >= R[i]:
        break
    if P[0] > Q[0]:
        if Q[0] < R[i]:
            heapq.heappop(Q)
            heapq.heappush(Q, R[i])
    else:
        if P[0] < R[i]:
            heapq.heappop(P)
            heapq.heappush(P, R[i])
    i += 1
    if i == len(R):
        break
print(sum(P) + sum(Q))
### BUGGY CODE ###

N = int(input())

if N == 1:
    print(0)
else:
    print(sum([i for i in range(1, N)]))


### FIXED CODE ###

N = int(input())
print(N * (N-1) // 2)
### BUGGY CODE ###

#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if pt > dijk[dr][x][y]:
    continue
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] > pt+1:
      dijk[dr][x-1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] > pt+1:
      dijk[dr][x+1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] > pt+1:
      dijk[dr][x][y-1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] > pt+1:
      dijk[dr][x][y+1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

### FIXED CODE ###

#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)
### BUGGY CODE ###

import math
from itertools import accumulate

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

printed_lst = []
for _ in range(K):
    s = [0]*N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right+1 <= N-1:
            s[right+1] -= 1
        #print(left,right)
    al = list(accumulate(s))
    #print(al)
    if al in printed_lst:
        print(' '.join([str(i) for i in al]))
        #print('end')
        exit()
    else:
        printed_lst.append(al)

print(' '.join([str(i) for i in al]))

### FIXED CODE ###

import math
from itertools import accumulate

N, K = map(int, input().split())
al = list(map(int, input().split()))
syusoku = [N] * N

for _ in range(K):
    s = [0] * N
    for i in range(N):
        left = i - al[i]
        right = i + al[i]
        if left < 0:
            left = 0
        s[left] += 1
        if right + 1 <= N - 1:
            s[right + 1] -= 1
        # print(left,right)
    al = list(accumulate(s))
    # print(al)
    if al == syusoku:
        print(*al)
        #print('end')
        exit()

print(*al)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def solve(S, query):
    flag = False
    S = list(S)
    for q in query:
        command = q.split()
        T = int(command[0])
        if T == 1:
            flag = not flag
        elif T == 2:
            F = int(command[1])
            C = command[2]
            if (not flag and F == 1) or (flag and F == 2):
                S.insert(0, C)
            else:
                S.append(C)
    if flag:
        S.reverse()
    return ''.join(S)


def main():
    S = input()
    Q = int(input())
    query = [input() for n in range(Q)]
    print(solve(S, query))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    S = input()
    Q = int(input())
    flag = False
    head = []
    tail = []
    for n in range(Q):
        query = input()
        if query[0] == '1':
            flag = not flag
        elif query[0] == '2':
            command = query.split()
            F = int(command[1])
            C = command[2]
            if (not flag and F == 1) or (flag and F == 2):
                head.append(C)
            else:
                tail.append(C)
    result = ''.join(reversed(head)) + S + ''.join(tail)
    if flag:
        result = result[::-1]
    print(result)


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

import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
dp=np.full(k+1,False)
calted=np.full(k+1,False)
# dp[i]:残り石i個で自分のターンになった時、勝てるならTrue
# dp[0]=False,dp[a]=True,求めるのはdp[k]
mi=np.min(a)
ma=np.max(a)
dp[a]=True
calted[a]=True
# dp[i]={dp[i-a]の中にFalseがあればTrue、すべてTrueならFalse}
for i in range(mi+1,k+1):
      if calted[i]:
            continue
      il=i-a
      li=[j for j in il if j>=0]
      f=np.prod(dp[il])
      if f == 0:
            dp[i]=True
      else:
            dp[i]=False
print('First' if dp[k] else 'Second')
#print(dp)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100,100000
#a=range(1,101)

dp=[False for _ in range(k+1)]
calted=[False for _ in range(k+1)]
# dp[i]:残り石i個で自分のターンになった時、勝てるならTrue
# dp[0]=False,dp[a]=True,求めるのはdp[k]
mi=min(a)
ma=max(a)
for ai in a:
	dp[ai]=True
	calted[ai]=True
# dp[i]={dp[i-a]の中にFalseがあればTrue、すべてTrueならFalse}
for i in range(mi+1,k+1):
      if calted[i]:
            continue
      il=[i-ai for ai in a if i-ai>=0]
      f=1
      for l in il:
        f*=dp[l]
      if f == 0:
            dp[i]=True
      else:
            dp[i]=False
print('First' if dp[k] else 'Second')
#print(dp)
#print(datetime.datetime.now())
### BUGGY CODE ###

import sys
from heapq import *

input = sys.stdin.readline

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

A.sort()
F.sort(reverse=True)

cost = []
for i in range(N):
	ai, fi = A[i], F[i]
	heappush(cost,(ai*fi*-1,ai,fi))

while K>0:
	cmax, ai, fi = heappop(cost)
	if cmax==0: break
	csec = min(cost[0][0],cost[1][0])
	count = (csec-cmax)//ai + 1
	if count>K: count = K
	# print(count)
	aj = ai-count
	fj = fi
	cj = aj*fj*-1
	heappush(cost,(cj,aj,fj))
	K -= count

ans = cost[0][0]*-1
print(ans)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline

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

A.sort()
F.sort(reverse=True)

cost = []
for ai, fi in zip(A,F):
	cost.append([ai*fi,fi])
cost.sort(reverse=True)

thmin = -1
thmax = cost[0][0]+1

while thmax-thmin!=1:
	# print(thmin,thmax)
	th = (thmin+thmax)//2
	ktmp = 0
	ind = 0
	judge = True
	while True:
		ci, fi = cost[ind]
		if ci<=th: break
		ktmp += math.ceil((ci-th)/fi)
		if ktmp>K:
			judge = False
			break
		ind += 1
		if ind==N: break
	if judge:
		thmax = th
	else:
		thmin = th

print(thmax)
### BUGGY CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]

mx=0
for i in range(N-K+1):
  mx=max(mx,sum(p[i:i+K]))
print((mx+K)/2)

### FIXED CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in p]
ruiseki=[0]
ans=0

for i in range(N):
  ruiseki.append(ruiseki[i]+ex[i])


for i in range(N+1-K):
  if ans<ruiseki[i+K]-ruiseki[i]:
    ans=ruiseki[i+K]-ruiseki[i]
print(ans)
### BUGGY CODE ###

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

res = 0
for j in range(n):
    for i in range(j):
        res = res + (a[j] * a[i])
print(res % ((10 **9)+7))

### FIXED CODE ###

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

res = 0
ruiseki = 0
for j in range(n):
    if j == 0:
        continue
    ruiseki += a[j-1]
    res = res + a[j]*ruiseki
print(res % ((10 **9)+7))
### BUGGY CODE ###

H, W = [int(i) for i in input().split(" ")]
S = []
for i in range(H):
  S.append(input())

import numpy as np
mat = np.full([H,W,2], -1)
  
def calc_c(S,r,c):
  count = 0
  c1 = c
  while True:
    c1 -= 1
    if c1 >=0 and S[r][c1]==".":
      count += 1
    else: break
      
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      count += 1
    else: break
      
  mat[r,c]=count
  return count

def calc_r(S,r,c):
  count = 0
  r1 = r
  while True:
    r1 -= 1
    if r1 >= 0 and S[r1][c]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      count += 1
    else: break
   
  mat[r,c]=count
  return count

ans = 0
  
for r in range(H):
  for c in range(W):
    target = S[r][c]
    if target == "#":
      continue
      
    rc, cc = mat[r,c]
    if rc == -1:
    	rc = calc_r(S,r,c)
    if cc == -1:
    	cc = calc_c(S,r,c)
        
    ans = max(rc+cc+1, ans) 

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

a,b,x=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%x==0:
        ans+=1
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())
ans=0
ans+=b//x
ans-=(a-1)//x
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
A += A    
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[B[i]] = i+1
i = 0
ans = []
while i < N:
    ok = True
    for j in range(N):
        if B[N-j-1] != A[N-j-1+i]:
            if d[B[N-j-1]] == 0:
                i += N
                ok = False
                break
            else:
                i += N - d[B[N-j-1]] + 1
                ok = False
                break
    if ok:
        ans.append((i,a[i]^b[0]))
        i += 1
for x in ans:
    print(*x)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B == [A[0]]*N:
    for i in range(N): 
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)
### BUGGY CODE ###

N,K = map(int, input().split())
a_list = list(map(int, input().split()))
counter_list = []
for i in range(1,N+1):
    if a_list.count(i) > 0:
        counter_list.append(a_list.count(i))

counter_list.sort()

count = 0
for i in range(len(counter_list) - K):
    count += counter_list[i]

print(count)


### FIXED CODE ###

N,K = map(int, input().split())
a_list = list(map(int, input().split()))
counter_list = [0]*N
for i in a_list:
    counter_list[i-1] += 1

counter_list.sort(reverse=True)

ans = N - sum(counter_list[:K])    

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

import numpy as np

k = int(input())
s = list(input())
mod = 10 ** 9 + 7

nagasa = len(s)

n = nagasa + k
N = 1500 ** 2
Nsq = 1500
fact = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fact[0, 0] = 1
for n in range(1, Nsq):
    fact[:, n] *= fact[:, n - 1]
    fact[:, n] %= mod
for n in range(1, Nsq):
    fact[n] *= fact[n - 1, -1]
    fact[n] %= mod
fact = fact.ravel()
fact_inv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
fact_inv[0, 0] = pow(int(fact[N - 1]), mod - 2, mod)
for n in range(1, Nsq):
    fact_inv[:, n] *= fact_inv[:, n - 1]
    fact_inv[:, n] %= mod
for n in range(1, Nsq):
    fact_inv[n] *= fact_inv[n - 1, -1]
    fact_inv[n] %= mod
fact_inv = fact_inv.ravel()[::-1]


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    res = fact[n]
    res *= fact_inv[n - r]
    res %= mod
    res *= fact_inv[r]
    res %= mod
    return res


ans = 0
for i in range(k + 1):
    temp = 0
    temp += comb(nagasa - 1 + i, nagasa - 1) * pow(25, i, mod)
    temp %= mod
    temp *= pow(26, k - i, mod)
    temp %= mod
    ans += temp
    ans %= mod

print(ans)


### FIXED CODE ###

k = int(input())
s = list(input())
mod = 10 ** 9 + 7

nagasa = len(s)


ans = pow(26, k, mod)
bunbo = 1
bunshi = 1
for i in range(1, k + 1):
    bunbo *= nagasa - 1 + i
    bunshi *= pow(i, mod - 2, mod)
    bunbo %= mod
    bunshi %= mod
    temp = bunbo * bunshi
    temp %= mod
    temp *= pow(25, i, mod)
    temp %= mod
    temp *= pow(26, k - i, mod)
    temp %= mod
    ans += temp
    ans %= mod

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

N=int(input())
num = 7
plus = 70
i=1
a=[]
while num%N!=0:
    xx=num%N
    if xx in a:
        i=-1
        break
    a.append(xx)
    num=10*xx+7
    i+=1
print(i)

### FIXED CODE ###

N=int(input())
num = 7
i=1
a=[]
prir1=1
while i<=N:
    xx=num%N
    if xx==0:
        print(i)
        prir1=0
        break
    num=10*xx+7
    i+=1
if prir1:
    print(-1)
### BUGGY CODE ###

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

answer = [0] * len(S)
b_list = []
for idx, moji in enumerate(S):
    if moji == "a" and sum(answer) < A + B:
        answer[idx] = 1
    elif moji == "b":
        b_list.append(1)
        if sum(answer) < A + B and sum(b_list) <= B:
            answer[idx] = 1
    elif moji == "c":
        pass
    else:
        pass
for result in answer:
    if result == 1:
        print("Yes")
    elif result == 0:
        print("No")


### FIXED CODE ###

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

answer = 0
b_list = 0
for idx, moji in enumerate(S):
    if moji == "a" and answer < A + B:
        answer += 1
        print("Yes")
        continue
    elif moji == "b":
        b_list += 1
        if answer < A + B and b_list <= B:
            answer += 1
            print("Yes")
            continue
    print("No")
### BUGGY CODE ###

a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
    return True
b=0
for i in range(a):
    a=input()
    if ip(a):b+=1
print(str(b))

### FIXED CODE ###

a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
        i+=1
    return True
b=0
for i in range(int(a)):
    c=input()
    if ip(int(c)):b+=1
print(str(b))
### BUGGY CODE ###

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

cnt=[0]*100
p=10**9+7
for m in a:
    #print(m)
    kei=m
    for i in range(100):
        cnt[i]+=kei%2
        kei//=2
        if(kei==0):
            break

#print(cnt)

lis=[]
jou=1
for i in range(100):
    lis.append(jou)
    jou*=2
    jou%=p

ans=0

for i in range(100):
    ans+=(lis[i]%p)*(cnt[i]%p)*((n-cnt[i])%p)
    ans%=p

print(ans)

### FIXED CODE ###

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

cnt=[0]*60
p=10**9+7
for m in a:
    #b=bin(m)
    #l=len(b)-2
    #print(b)
    for i in range(60):
        if((m>>i) & 1):
            cnt[i]+=1
    #for i in range(l):
    #    cnt[i]+=int(b[-i-1])
    #kei=m
    #for i in range(100):
    #    cnt[i]+=kei%2
    #    kei//=2
    #    if(kei==0):
    #        break

#print(cnt)

lis=[]
jou=1
for i in range(60):
    lis.append(jou)
    jou*=2
    jou%=p

ans=0

for i in range(60):
    ans+=(lis[i]%p)*(cnt[i]%p)*((n-cnt[i])%p)
    ans%=p

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

# -*- coding: utf-8 -*-
N, a, b = map(int, input().split())

def get_combi_mod(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans = 1
mod_case = 1 if N % 1000 != 0 else 0
div_num = 10 ** 9 + 7
for i in range(N // 1000 + mod_case):
    ans = (ans * (2 ** 1000)) % div_num

print((2 ** N - 1 - get_combi_mod(N, a, div_num) - get_combi_mod(N, b, div_num)) % (10 ** 9 + 7))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, a, b = map(int, input().split())

def get_combi_mod(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans = 1
div_num = 10 ** 9 + 7
two_thou = (2 ** 1000) % div_num
for i in range(N // 1000):
    ans = (ans * two_thou) % div_num

ans = (ans * (2 ** (N % 1000))) % div_num
print((ans - 1 - get_combi_mod(N, a, div_num) - get_combi_mod(N, b, div_num)) % (10 ** 9 + 7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = set([int(input()) for i in range(m)])

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(n-3):
    for j in range(i+1, n-1):
        if s[i] == s[j]: continue
        for k in range(j+1, n):
            if (j - i) == (k - j): continue
            if s[i] == s[k] or s[j] == s[k]: continue
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = 0
g = 0
b = 0

for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    else:
        b += 1

ans = r * g * b

for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]: continue
        k = 2*j - i
        if k >=n: continue
        if s[i] == s[k] or s[j] == s[k]: continue
        ans -= 1

print(ans)