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

from collections import deque
q = deque()
for _ in range(int(input())):
    c, *k = input().split()
    k = k[0] if k else None
    if c == 'insert':
        q.appendleft(k)
    elif c == 'delete':
        if k in q:
            q.remove(k)
    elif c == 'deleteFirst':
        q.popleft()
    else:
        q.pop()
print(*q)


### FIXED CODE ###

from collections import deque
from sys import stdin
q = deque()
input()
for s in stdin:
    if s == '\n':
        break
    c, *k = s.split()
    k = k[0] if k else None
    if c == 'insert':
        q.appendleft(k)
    elif c == 'delete':
        if k in q:
            q.remove(k)
    elif c == 'deleteFirst':
        q.popleft()
    else:
        q.pop()
print(*q)
### BUGGY CODE ###

# See:
# https://qiita.com/suecharo/items/30f5d817da4c948c3be6
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right


if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))

    for i in range(n):
        mod_x = list(x)
        tmp = mod_x.pop(i)
        mod_x = quick_sort(mod_x)
        print(mod_x[(n // 2) - 1])


### FIXED CODE ###

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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    sorted_x = sorted(x)

    low = sorted_x[(n // 2) - 1]
    high = sorted_x[(n // 2)]

    for i in range(n):
        if x[i] < high:
            print(high)
        else:
            print(low)
### BUGGY CODE ###

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

max_num = 0
j = 0
j_max = M + 1
for i in range(N + 1):
    j = 0
    while j < j_max:
        if sum(A[:i]) + sum(B[:j]) > K:
            j_max = j
            break

        max_num = max(max_num, i + j)
        j += 1
print(max_num)


### FIXED CODE ###

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

max_num = 0
j = 0
j_max = M
A_sums=[0]
B_sums=[0]
for i in range(N):
    A_sums.append(A_sums[i]+A[i])
for i in range(M):
    B_sums.append(B_sums[i]+B[i])


for i in range(N + 1):
    j = 0
    if A_sums[i]>K:
        break
    while A_sums[i]+B_sums[j_max] > K:
        j_max -=1

    max_num = max(max_num, i + j_max)
print(max_num)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

ans = []
lines_dict =None
d=None
def main():
    global AB, PX, T
    if 'LOCAL' in os.environ:
        N = 2* 10** 5
        Q = 2 * 10 ** 5
        AB = [[i, i + 1] for i in range(1, N)]
        PX = [[i, 10] for i in range(Q)]
    else:
        N, Q = LI()
        AB = tuple()
        T = [[] for _ in range(N+1)]
        PX = [0] * (N+1)
        for i in range(1, N+1):
            PX[i] = 0
        for i in range(N-1):
            a, b = LI()
            AB += (a, b)
            T[a] += [b]
            T[b] += [a]

        for i in range(Q):
            p, x = LI()
            PX[p] += x
        perr(AB)
        perr(PX)
        dfs(1, -1)
        for i in PX[1:]:
            print(i, end=' ')
        #  ans = [0 for _ in range(N)]

def dfs(parent, parent_parent):
    perr(PX)
    for node in T[parent]:
        if node != parent_parent:
            perr(node)
            PX[node] += PX[parent]
            dfs(node, parent)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
for a, b in AB:
    if b not in d.keys():
        d[b] = 0
    if a not in d.keys():
        d[a] = 0
    d[b] += d[a]
for i in range(1, N+1):
    print(d[i], end=' ')
### BUGGY CODE ###

s=input()
ls=len(s)
m=[0]*(2019)
m[0]+=1

cnt = 0
b=0
for i in range(ls):
  a = (b + int(s[ls - i -1])*10**cnt) % 2019
  m[a] += 1
  b = a
  cnt += 1

ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

print(ans)


### FIXED CODE ###

s=input()
ls=len(s)
m=[0]*(2019)
m[0]+=1

cnt = 0
b = 0
for i in range(ls):
  a = (b + pow(10,cnt,2019)*int(s[ls - i -1])) % 2019
  m[a] += 1
  b = a
  cnt += 1

ans = 0
for i in m:
  if i <= 1:
    continue
  ans += i*(i-1)//2

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

N, Q = map(int,input().split())
S = input()
for i in range(Q):
  L, R = map(int,input().split())
  ps = S[L-1:R]
  print(ps.count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        
        if sum(ANS[a[1]:a[1]+L]) < MAX + len(ANS[a[1]:a[1]+L]) - 1 : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == MAX:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == MAX : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == MAX : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.9997
MAX = 10**9+1
ANS = [MAX]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    for i in range(N):
        for j in range(M):
            if((i-1)*k/N+1 == (j-1)*k/M+1):
                if(S[i-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1


### FIXED CODE ###

input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N,M))
x = 1
count = 0
while True:
    k = L*x
    flag = 1
    starti = 0
    startj = 0
    for i in range(starti, N):
        for j in range(startj, M):
            hoge = i*k/N+1
            fuga = j*k/M+1
            if(hoge < fuga):
                startj = j - 1
                break
            elif(hoge == fuga):
                if(S[i] != T[j]):
                    flag = 0
                    count += 1
                    break
        if(flag == 0):
            break
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
comp = []
for _ in range(M):
    B, C = map(int, input().split())
    for i in range(B):
        comp.append(C)

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

zeros = [0] * N
comp.extend(zeros)
comp = comp[:N]

for i in range(N):
    if A[i] < comp[i]:
        A[i] = comp[i]

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [int(a) * (-1) for a in input().split()]

B_array = []
for _ in range(M):
    B, C = map(int, input().split())
    B_array.append([C * (-1), B])
B_array.sort()

cnt = 0
i = 0
B_list = []
while cnt < N and i < M:
    B_list.extend([B_array[i][0]] * B_array[i][1])
    cnt += B_array[i][1]
    i += 1

A.extend(B_list)
heapq.heapify(A)

ans = 0
for _ in range(N):
    ans += heapq.heappop(A)
        
print(ans * (-1))
### BUGGY CODE ###

input()
A=map(int,input().split())
r=1
for a in A:
  r*=a
if r>10e17:
  print(-1)
else:
  print(r)

### FIXED CODE ###

input()
A=list(map(int,input().split()))
r=1
if 0 not in A:
  for a in A:
    r*=a
    if r>10e17:
      print(-1)
      break
  else:
    print(r)
else:
  print(0)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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

h = [int(readline()) for i in range(N)]

C = A-B
ng = 0 #条件を常に満たさない
ok = INF #条件を常に満たす

def judge(mid):
    ans = 0
    for hi in h:
        ans += max(0,(hi-mid*B+C-1)//C)
    if ans <= mid:
        return True
    return False

while ok - ng > 1:
    mid = (ok + ng) // 2
    if judge(mid):
        ok = mid
    else:
        ng = mid
    #okが答えとなる
print(ok)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**9
eps = 10**-7

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

h = [int(readline()) for i in range(N)]

C = A-B
ng = 0 #条件を常に満たさない
ok = INF #条件を常に満たす

def judge(mid):
    ans = 0
    for hi in h:
        ans += max(0,(hi-mid*B+C-1)//C)
    if ans <= mid:
        return True
    return False

while ok - ng > 1:
    mid = (ok + ng) // 2
    if judge(mid):
        ok = mid
    else:
        ng = mid
    #okが答えとなる
print(ok)
### BUGGY CODE ###

N,M,*a=map(int,open(0).read().split())
dp=[1]*(N+1)
for i in a:
    dp[i]=0
for i in range(2,N+1):
    if i in a:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])    

### FIXED CODE ###

N,M=map(int,input().split())
dp=[1]*(N+1)
for i in range(M):
    dp[int(input())]=0
for i in range(2,N+1):
    if dp[i]!=0:
        dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%1000000007)
### BUGGY CODE ###

s = input()
K = int (input())


def sort_here(ll):  # バブルソート
    for m in range(len(ll)):
        for n in range(len(ll)-1-m):
            A, B = compare(ll[n], ll[n+1])
            ll[n] = A
            ll[n + 1] = B
    return ll


def compare_(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    a = len(A)
    b = len(B)

    if a > b:
        if A[:b] == B:
            return B, A
    elif b > a:
        if B[:a] == A:
            return A, B

    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

def compare(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

    if len(A) < len(B):
        return A, B
    elif len(B) < len(A):
        return B, A
    else:
        raise Exception


# まずは長さが5以下で存在しうるsubstringを準備
i_list = []
for i in range(1, 6):
    # i文字数のsutringをまずは作る
    for j in range(len(s) - i + 1):
        cand = s[j:j+i]
        if cand not in i_list:
            i_list.append(s[j:j+i])

#print(i_list)

# 並び替え
i_list = sort_here(i_list)
#print(i_list)


# 出力
print(i_list[K-1])








### FIXED CODE ###

s = input()
l = len(s)
k = int(input())


def compare(a, b):
    ll = [a, b]
    ll = sorted(ll)
    return ll[0] == a


db = []
for length in range(1, k + 1):
    for start in range(l + 1 - length):
        candidate = s[start:start+length]
        if len(db) >= 5:
            if compare(candidate, db[-1]):
                if candidate not in db:
                    db.append(candidate)
                    db = sorted(db)
                    db = db[:5]
        else:
            if candidate not in db:
                db.append(candidate)
                db = sorted(db)

print(sorted(db)[k-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
count = [0]*N
for i in range(1, N): #i番目までに何個の'AC'があったかをリスト格納
    count[i] += count[i-1]
    if S[i-1:i+1] == 'AC':
        count[i] += 1
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = a[i]
for l in range(1, n):
    for s in range(n - l):
        dp[s][s + l] = max(a[s] - dp[s + 1][s + l], a[s + l] - dp[s][s + l - 1])
print(dp[0][n - 1])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = a[i]
for l in range(1, n):
    for s in range(n - l):
        dp[s][s + l] = max(a[s] - dp[s + 1][s + l], a[s + l] - dp[s][s + l - 1])
print(dp[0][n - 1])
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
 
N=int(input())
 
A=[]
for i in range(99):
    A.append(i+1)
 
D=list(itertools.combinations_with_replacement(A, 3))
S = []
#print(len(D))
for i in range(len(D)):
    if D[i][0]+D[i][1]+D[i][2]<123:
        S.append(D[i])

     


#print(len(D))
for j in range(1,N+1):
    count=0
    for sa in S:
        if (sa[0]+sa[1]+sa[2])**2-sa[0]*sa[1]-sa[1]*sa[2]-sa[2]*sa[0]==j:
            if sa[0]!=sa[1] and sa[1] !=sa[2]:
                
                count+=6
            elif sa[0]==sa[1] and sa[1]==sa[2]:
                count+=1
            else:
                count+=3
 
    print(count)


### FIXED CODE ###

import sys

import itertools
input = sys.stdin.readline
 
N=int(input())

ans=[0]*10050

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            v=i*i+j*j+k*k+i*j+i*k+j*k
            if v<10050:
                ans[v]+=1

for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)

    n = ni()
    a = na()
    # a.sort()

    lcm = lcm_list(a)

    ans = 0
    for ai in a:
        ans += lcm // ai
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)

    n = ni()
    a = na()

    lcm = a[0]
    for i in a:
        lcm = lcm // math.gcd(lcm, i) * i
    lcm %= MOD

    ans = 0
    for ai in a:
        ans += lcm * pow(ai, MOD - 2, MOD) % MOD
        ans %= MOD

    print(ans)


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

n,m=map(int,input().split())
a=[0]*m
for i in range(m):
  a[i]=int(input())
temp=[0]*(n+1)
temp[0]=1
if 1 in a:
  temp[1]=0
else:
  temp[1]=1
for i in range(2,n+1):
  if i in a:
    temp[i]=0
  else:
    temp[i]=temp[i-2]+temp[i-1]
    temp[i]=temp[i]%(10**9+7)
print(temp[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*m
for i in range(m):
  a[i]=int(input())
a.append(0)
temp=[0]*(n+1)
temp[0]=1
if 1 in a:
  temp[1]=0
  j=1
else:
  temp[1]=1
  j=0
for i in range(2,n+1):
  if a[j]==i:
    temp[i]=0
    j=j+1
  else:
    temp[i]=temp[i-2]+temp[i-1]
    temp[i]=temp[i]%(10**9+7)
print(temp[n])
### BUGGY CODE ###

#Input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

DP = [[0 for j in range(W + 1)] for i in range(N + 1)]
# print(DP)
#Initialization
for i in range(W):
    DP[0][i] = 0

for i in range(1, N + 1):
    for j in range(W + 1):
        if w[i - 1] > j:
            DP[i][j] = DP[i - 1][j]
        else:
            # print("i, j:", i, j)
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - w[i - 1]] + v[i - 1])

# print(DP)
print(DP[N][W])


### FIXED CODE ###

#Input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    w[i], v[i] = map(int, input().split())

DP = [[0 for j in range(W + 1)] for i in range(N + 1)]
# print(DP)
#Initialization
for i in range(W):
    DP[0][i] = 0

for i in range(1, N + 1):
    for j in range(W + 1):
        if w[i - 1] > j:
            DP[i][j] = DP[i - 1][j]
        else:
            # print("i, j:", i, j)
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - w[i - 1]] + v[i - 1])

# print(DP)
print(DP[N][W])
### BUGGY CODE ###

import numpy as np
import math as m

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

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

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

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

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 ###

import collections

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

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[sequence1 + "-" + sequence1_inverse] += 1     
    s_2[sequence2 + "-" + sequence2_inverse] += 1
ans = 0
for i in dict(s_1):
    '''
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
print(ans)


### FIXED CODE ###

import collections

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

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)

strlist = []

for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[sequence1 + "-" + sequence1_inverse] += 1     
    s_2[sequence2 + "-" + sequence2_inverse] += 1
ans = 0

for i in dict(s_1):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)
### BUGGY CODE ###


def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


K = int(input())
total = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        tmp = gcd(a, b)
        for c in range(1, K+1):
            total += gcd(tmp, c)

print(total)


### FIXED CODE ###

from math import gcd

K = int(input())
total = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        tmp = gcd(a, b)
        for c in range(1, K+1):
            total += gcd(tmp, c)

print(total)