Harryxun/stf_run huggingface dataset:
#幅優先探索による全探索
from collections import deque

def bfs(N):
    S = "abcdefghij"
    result = []
    deq = deque(["a"])

    while deq:
        s = deq.popleft()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in S[:len(set(s))+1]:
                deq.append(s + i)
    return result

N = int(input())
ans = bfs(N)
for a in ans:
    print(a)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
Flag = True
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        Flag = False if Flag else True
    else:
        if Flag:
            if q[1] == '1':
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if q[1] == '1':
                S.append(q[2])
            else:
                S.appendleft(q[2])

if Flag:
    print(''.join(S))
else:
    print(''.join(reversed(S)))
def lcs_size():
  X = input()
  Y = input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      else:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()

### FIXED CODE ###

def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      elif z2[j+1] < z2[j]:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()
s=int(input())
if s[2]==s[3] and s[4]==s[5]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s=input()
if s[2]==s[3] and s[4]==s[5]:
  print('Yes')
else:
  print('No')
n = int(input())
h = list(map(int,input().split()))
dp_ = [-1]*n

def dp(i):
    if dp_[i]!=-1:
        return dp_[i]
    if i == 0:
        return 0
    elif i == 1:
        return abs(h[1]-h[0])
    else:
        return min(dp(i-2)+abs(h[i]-h[i-2]),dp(i-1)+abs(h[i]-h[i-1]))

print(dp(n-1))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 

n = int(input())
h = list(map(int,input().split()))
dp_ = [-1]*n

def dp(i):
    if dp_[i]!=-1:
        return dp_[i]
    if i == 0:
        dp_[i] = 0
    elif i == 1:
        dp_[i] = abs(h[1]-h[0])
    else:
        dp_[i] = min(dp(i-2)+abs(h[i]-h[i-2]),dp(i-1)+abs(h[i]-h[i-1]))
    return dp_[i]

print(dp(n-1))
a,b,c = [int(i) for i in input().split()]
i=0
for i in list(range(a,b+1,1)):
    if c % i == 0:
        i = i+1
    else:
        
print(i)


### FIXED CODE ###

a,b,c = [int(i) for i in input().split()]
i=0
for num in range(a,b+1,1):
    if c % num == 0:
        i = i+1
    else:
        pass
print(i)
import math
from sympy import primerange
inn = n = int(input())
num = int(math.sqrt(n)) + 1
primlist = list(primerange(2,num)) 

for i in primlist:
    if inn % i == 0:
        while inn % num != 0:
            num -= 1
        else:
            print(num+ inn//num -2)
            break
        
else:
    print(inn-1)

### FIXED CODE ###

n = int(input())
ans = 0
t = int(n**(1/2)+1)


for i in range(t, 0, -1):
    if n%i == 0:
        ans += i
        ans += n//i
        break

print(ans-2)
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    print(H*W-path_area-black)
                
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    return -1

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    if path_area:
        print(H*W-path_area-black)
    else:
        print(-1)
                
    
    
if __name__ == "__main__":
    main()
n,k = map(int,input().split())
import math
print(int(math.log(n,k))+1)

### FIXED CODE ###

N,R = map(int,input().split())
if N > 10:
    print(R);
else:
    print(R + 100 * (10 - N))
a, b, c = map(int, input().split())
print(max(0, c - (a - b))

### FIXED CODE ###

a, b, c = map(int, input().split())
print(max(0, c - (a - b)))
import sys
sys.setrecursionlimit(100000000)

def main():
    S = input()
    N = len(S)
    ans = 0
    before = 0
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            ans = max(ans,min(i + 1,N - before))
            before = i + 1
    ans = max(ans,min(i + 1,N - before))
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    S = input()
    N = len(S)
    ans = 0
    before = 0
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            ans = max(ans,min(N - before,i + 1))
            before = i + 1
    ans = max(ans,N - before)
    print(ans)
if __name__ == '__main__':
    main()
import sys
import itertools
import numpy as np

rm = lambda: map(int, sys.stdin.readline().split())

h, w, k = rm()
cnt = 0
def f(x):
  if x == '#':
    return 1
  else:
    return 0
li = np.array([np.array(list(map(f, sys.stdin.readline().split()))) for _ in range(h)])
lih = list(itertools.product(list(range(2)), repeat=h))
liw = list(itertools.product(list(range(2)), repeat=w))

for i in lih:
  a = list(itertools.compress(li, i))
  a.T()
  for j in liw:
    b = list(itertools.compress(a, j))
    if np.sum(b) == k:
      cnt += 1
print(cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import numpy as np

rm = lambda: map(int, sys.stdin.readline().split())
rr = lambda: sys.stdin.readline().rstrip()

h, w, k = rm()
li = np.array([np.array(list(rr())) for _ in range(h)])
cnt = 0

for i in range(h+1):
    for a in np.array(list(combinations(li, i))):
        a = a.T
        for j in range(w+1):
            for b in np.array(list(combinations(a, j))):
                t = np.count_nonzero(b == '#')
                if t == k:
                    cnt += 1
print(cnt)
K, S = map(str, input().split())
K = int(K)

if len(S) <= K:
    print(S)
else:
    print(S[0:K]+"...")

### FIXED CODE ###

K = int(input())
S = input()

if len(S) <= K:
    print(S)
else:
    S = S[0:K]+"..."
    print(S)
N = int(input())
A = list(map(int,input()))

ans = 0
high = 0
for i in range(1,N):
    if high < A[i-1]:
        high = A[i-1]
    if high > A[i]:
        ans += high - A[i]

print(ans)

### FIXED CODE ###

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

ans = 0
high = 0
for i in range(1,N):
    af = A[i]
    bf = A[i-1]
    if bf > high:
        high = bf
    if high > af:
        ans += high - af

print(ans)
n=input()
print(n//3)

### FIXED CODE ###

print(int(input())//3)
N, M = map(int, input().split())

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

X1 = list(set(X))

print(N-len(X1))

### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,N):
    d = [float('inf')] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist, a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N = int(input())
    edge = [[] for i in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append([w,v])
        edge[v].append([w,u])

    D = dijkstra_heap(0,edge,N)
    first = D[0]
    for d in D:
        if abs(d - first) % 2 == 0:
            print(0)
        else:
            print(1)

main()
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reversed()
print(sum(a[:m]))

### FIXED CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reverse()
print(sum(a[:m]))
n, k = map(int, input().split())

stayed = [0] * (n+1)

A = list(map(int, input().split()))
start = 0
stayed[0] = 1
roops = 0
ANS = []
for i in range(n+1):
    if stayed[A[start] - 1] == 0:
        stayed[A[start] - 1] = 1
        start = A[start] - 1
        ANS.append(start)
        roops += 1
    else:
        break
index_ = ANS.index(start - 1)
before_roop = index_ + 1
if index_ == 0:
    before_roop = 0
true_roop = len(ANS) - index_

if true_roop + before_roop >= k:
    ANS = [0] + ANS + [start -1]
    print(ANS[k] + 1)
else:
    k = k - before_roop
    k = k % true_roop
    ANS = ANS[index_:]
    print(ANS[k] + 1)

### FIXED CODE ###

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

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

check = [0] * n

start = 0
path = []
for i in range(n):
    if check[start] == 0:
        check[start] = 1
        path.append(start)
        start = A[start] - 1
path.append(start)

before_roop = path[:path.index(path[-1])]
B = before_roop
if before_roop == []:
    before_roop = 0
else:
    before_roop = len(before_roop)

roop = len(path) - before_roop - 1

if k <= before_roop:
    print(path[:before_roop+1][k] + 1)
else:
    k -= before_roop
    k = k % roop
    print(path[before_roop+1:][k-1] + 1)
n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

for i in range(n):
  if i == l[skip]:
    res[0] = res[1]
    res[1] = 0
    if skip < m-1:
      skip += 1
  else:
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
    
print(res[1])

### FIXED CODE ###

n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

if m != 0:
  for i in range(n):
    if i == l[skip]:
      res[0] = res[1]
      res[1] = 0
      if skip < m-1:
        skip += 1
    else:
      tmp = res[1]
      res[1] += res[0]
      res[0] = tmp
      res[1] %= 10**9 + 7
      res[0] %= 10**9 + 7
else:
  for i in range(n):
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])
a, b ,c = map(input().split(" "))
print(c+" "+a+" "+b)

### FIXED CODE ###

input = input().split(" ")
print(input[2] + " " + input[0] + " " + input[1])
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
  break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
s,w = map(int,input().split())
if w>=s:
  print("unsafe")
else:
  print("safe)

### FIXED CODE ###

s,w = map(int,input().split())
if w>=s:
  print("unsafe")
else:
  print("safe")
import numpy as np

S = raw_input()
N = len(S)
T = np.zeros([N,N], dtype=bool)
for i in xrange(0, N):
    if (i-1)>=0 and S[i-1] == "R":
        T[i, i-1] = True
    if (i+1) <N and S[i+1] == "L":
        T[i, i+1] = True
    
Even = np.ones(N, dtype=int) # Last even times status
Stat = np.ones(N, dtype=int) # Current status

for i in xrange(1, 1000):
    Stat = np.dot(T, Stat)
    if i % 2 == 0:
        if np.all(Stat == Even):
            break
        else:
            Even = Stat

print " ".join([str(i) for i in Stat])

### FIXED CODE ###

S = raw_input()
N = len(S)

ans = [0 for _ in xrange(N)]
for i in xrange(0,N-1):
    if S[i] == "R" and S[i+1] == "L":
        # Positon of "RL"
        ans[i] = 1
        ans[i+1] = 1
        # Search the Left wind
        j = 1
        while (i-j) >=0 and S[i-j] == "R":
            if j %2 == 1:
                ans[i+1] += 1
            else:
                ans[i] += 1
            j += 1
        # Search the right wind
        j = 2
        while (i+j) <N and S[i+j] == "L":
            if j %2 == 1:
                ans[i+1] += 1
            else:
                ans[i] += 1
            j += 1
        
print " ".join([str(i) for i in ans])
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            bit_add2(bit, j0, j, N1, 1)
            #bit_add(bit, j0, N1, 1)
            #bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list[0] == 1:
    Dp_list = [1,0]
else:
    Dp_list = [1,1]
for i in range(2, N + 1):
    if i not in A_list:
        Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
    elif i in A_list and i-1 in A_list:
        Dp_list = [0] * (N + 1)
        break
    else:
        Dp_list.append(0)
    if Dp_list[i-1] > 1000000007:
        Dp_list[i-1] -= 1000000007
        Dp_list[i] -= 1000000007
print(Dp_list[N]%1000000007)

### FIXED CODE ###

N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)
N, K = map(int, input().split())
lst = []
for i in range(N):
    lst.append(int(input()))
lst.sort()
dif = 10**9
for i in range(K):
    if lst[i+K-1] - lst[i] < dif:
        dif = lst[i+K-1] - lst[i]
print(dif)

### FIXED CODE ###

N, K = map(int, input().split())
lst = []
for i in range(N):
    x = int(input())
    lst.append(x)
lst.sort()
L = []
for i in range(N - K + 1):
    L.append(lst[i + K -1] - lst[i])
L.sort()
print(L[0])
A,B,K = map(int,input().split())

a = A
b = B

def cal_divisor(num):
    prime = [2,3,5,7,11,13]
    ans_list = []
    for i in range(len(prime)):
        ans_list.append([prime[i],0])
    for i in range(len(prime)):
        while True:
            if num % prime[i] == 0:
                num //= prime[i]
                ans_list[i][1] += 1
            if num % prime[i] != 0:
                break
    return ans_list

q = cal_divisor(a)
w = cal_divisor(b)

ans = []
for i in range(len(q)):
    ans.append([q[i][0],min(q[i][1],w[i][1])])
    
ans1 = []
for i in range(len(ans)):
    if ans[i][1] != 0:
        times = ans[i][1]
        for j in range(times+1):
            ans1.append(ans[i][0] ** j)

ans1.sort()

if K != 1:
    print(ans1[K-1])
if K == 1:
    print(1)

### FIXED CODE ###

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

n = min(a,b)

count = 0
for i in reversed(range(1,n+1)):
    if a % i == 0 and b % i == 0:
        count += 1
    if count == k:
        print(i)
        break
n = int(input())
li = [int(z) for z in input().split()]

l2 = [""] * n

c = 0
for i in li:
  l2[c] = i
  c += 1
print(l2)

### FIXED CODE ###

N = int(input())

odd = 0
even = 0
for i in range(N):
	if i % 2 == 0:
		odd += 1
	else:
		even += 1

print(odd/(odd + even))
import sys

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[None for _ in range(4)] for _ in range(len(S) + 1)]


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

def dp(i, j):
    if not cache[i][j] == None:
        return cache[i][j]

    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            cache[i][j] = (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
            return cache[i][j]
        else:
            cache[i][j] = dp(i + 1, 3)
            return cache[i][j]
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            cache[i][j] = (pre + lat) % DEVIDER
            return cache[i][j]
        if check(S[i], j):
            cache[i][j] = (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
            return cache[i][j]
        cache[i][j] = dp(i + 1, j)
        return cache[i][j]


ret = dp(0, 0)
print(ret)





### FIXED CODE ###

import sys

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
cache[0][0] = 1


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False


for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            cache[i + 1][j] += 3 * cache[i][j]
        else:
            cache[i + 1][j] += cache[i][j]
        if j > 0:
            if check(S[i], j-1) or S[i] == '?':
                cache[i+1][j] += cache[i][j - 1]
        cache[i+1][j] %= DEVIDER

print(cache[len(S)][3])
a,b,c,d=map(int,input().split())
if abs(a-b)<=d and abs(b-c)<=d:
  if abs(a-c)<=d:
    print("Yes")
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

a,b,c= map(int,input().split())
if a+b>=c:
  print("Yes")
else:
  print("No")
s = input()
a=0
b=0
def sakana():
  for j in range(len(s)//2):
    if s[j] != s[(len(s)//2)+j]:
      break
    else:
      a=a+1
  if a==len(s)//2:
    return 0
  else:
    return 1

for i in range(len(s)):
  s.rstrip(s[-1])
  if len(s)%2==0 and sakana()==0:
    break
  else:
    b=b+1
print(len(s)-b-1)
    


### FIXED CODE ###

s = input()
t=s
b=0
def sakana(sak, u):
  a=0
  for j in range(len(u)//2):
    if u[j] != u[(len(u)//2)+j]:
      break
    else:
      a=a+1
  if a==len(u)//2:
    return 0
  else:
    return 1

for i in range(len(t)):
  s=s[:-1]
  if len(s)%2==0 and sakana(i, s)==0:
    break
  else:
    b=b+1
print(len(t)-b-1)
c = [500,100,50,10,5,1]
while True:
    e = int(raw_input())
    if e == 0: break
    i,m = 0,0
    while e > 0:
        if e >= c[i]:
            e -= c[i]
            count += 1
        else:
            i += 1
    print count

### FIXED CODE ###

c = [500,100,50,10,5,1]
while True:
    e = int(raw_input())
    if e == 0: break
    e = 1000-e
    i,m = 0,0
    while e > 0:
        if e >= c[i]:
            e -= c[i]
            m += 1
        else:
            i += 1
    print m
# from .myutil import Combination


class Combination:
    mod = 0
    N = 0
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]

    def __init__(self, mod=10 ** 9 + 7, N=10 ** 6):
        self.mod = mod
        self.N = N
        for i in range(2, self.N + 1):
            self.g1.append((self.g1[-1] * i) % self.mod)
            self.inverse.append((-self.inverse[self.mod % i] * (self.mod // i)) % self.mod)
            self.g2.append((self.g2[-1] * self.inverse[-1]) % self.mod)

    def cmb(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % self.mod


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

total = (2 ** n) - comb.cmb(n, a) - comb.cmb(n, b) - 1

print(total)


### FIXED CODE ###

# from .myutil import Combination
from math import factorial

MOD = 10 ** 9 + 7
def Combination2(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) % MOD
    return ret * pow(factorial(r), MOD - 2, MOD) % MOD

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

total = pow(2, n, MOD) - Combination2(n, a) - Combination2(n, b) - 1
total %= MOD

print(total)