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

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

m, a, b = mi()

P = 10**9+7
N = 2*(10**5)+1
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

mca = mcb = 1

for i in range(1, a+1):
    mca *= (m-i+1) * inv_t[i]
    mca %= P

for i in range(1, b+1):
    mcb *= (m-i+1) * inv_t[i]
    mcb %= P

print(((2**m)-mca-mcb-1)%P)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

m, a, b = mi()

P = 10**9+7
N = 2*(10**5)+1
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

mca = mcb = 1

for i in range(1, a+1):
    mca *= (m-i+1) * inv_t[i]
    mca %= P

for i in range(1, b+1):
    mcb *= (m-i+1) * inv_t[i]
    mcb %= P

print(((2**m)-mca-mcb-1)%P)
### BUGGY CODE ###

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

sa = sorted(a,reverse=True)
ans = 0
ls = [sa[0]]
for v in sa[1:]:
  i = ls.index(max(ls))
  ans+= ls[i]
  new_min = min(ls[i], v)
  ls = ls[:i] + [new_min, new_min] + ls[i+1:]
  #print(ls)

print(ans)


### FIXED CODE ###

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

sa = sorted(a,reverse=True)
ans = sa[0]
i = 2
for v in sa[1:]:
  if i >= n:
    break
  #print("i:{} ans:{}".format(i,ans))
  ans += v
  i += 1
  if i >= n:
    break
  #print("i:{} ans:{}".format(i,ans))
  ans += v
  i += 1

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

N,HP=map(int,input().split())
listK=[]
listN=[]
 
for i in range(N):
    k,n=map(int,input().split())
    listK.append(k)
    listN.append(n)
listK.sort(reverse=True)
listN.sort(reverse=True)
cnt=0
for i in range(N):
    if listN[i]>=max(listK):
        HP-=listN[i]
        cnt+=1
        if HP<=0:
            print(cnt)
            exit()
    else:
        break
 
cnt+=int((HP+listK[0]-1)/(listK[0]))
print(cnt)

### FIXED CODE ###

n,h=map(int,input().split())
slash=[]
throw=[]
for i in range(n):
    x,y=map(int,input().split())
    slash.append(x)
    throw.append(y)
 
slash.sort(reverse=True)
throw.sort(reverse=True)
attack=0
for i in range(n):
    if throw[i]>=slash[0]:
        h-=throw[i]
        attack+=1
        if h<=0:
            print(attack)
            exit()
    else :
        break
 
attack+=int((h+slash[0]-1)/(slash[0]))
print(attack)
### BUGGY CODE ###

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

total = 0
for i in range(N):
    for j in range(i+1, N):
        total += nums[i] * nums[j]

print(total % (1000000000+7))

### FIXED CODE ###

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

total = 0
sums = []
tmp = 0

for i in range(1, N):
    tmp += nums[N-i]
    sums.append(tmp)

for i in range(N-1):
    a = nums[i]
    b = sums[N-(i+2)]
    total += a*sums[N-(i+2)]

print(total % (1000000000+7))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read

K, S = map(int, read().split())
count = 0

for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z == S:
                count += 1

print(count)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read

K, S = map(int, read().split())
count = 0

for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count += 1

print(count)
### BUGGY CODE ###

def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    return res


n, p = map(int, input().split())
res = prime_factorization(p)
ans = [1 for _ in range(n)]
for p in res:
    k = p[1]
    while k:
        for i in range(n):
            if k == 0:
                break
            ans[i] *= p[0]
            k -= 1

print(min(ans))


### FIXED CODE ###

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

res = []
for i in range(2, int(pow(p, 0.5)) + 1):
    if p % i == 0:
        ex = 0
        while p % i == 0:
            ex += 1
            p //= i
        res.append([i, ex])
if p != 1:
    res.append([p, 1])

ans = 1
for p in res:
    k = p[1]
    while k:
        if k < n:
            k = 0
        else:
            ans *= p[0]
            k -= n
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        load[a-1].append([b-1,c])
        load[b-1].append([a-1,c])
cost =[[L*N+1]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                newc = (gas//L+1)*L+c
            else:
                newc = gas+c
            if newc < cost[i][t]:
                cost[i][t] = newc
                queue.append(t)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans > L*N:
        print(-1)
    else:
        print((ans-1)//L)
     


### FIXED CODE ###

import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)
### BUGGY CODE ###

def main():
    R, C, K = list(map(int, input().split()))
    # dp[r][c][n]: r行目でn個のアイテムを拾う場合の(r, c)でのアイテムの価値の合計の最大
    dp = [[[0 for _ in range(4)] for _ in range(C)] for _ in range(R)]
    V = [[0 for _ in range(C)] for _ in range(R)]
    for _ in range(K):
        r, c, v = list(map(int, input().split()))
        V[r - 1][c - 1] = v
    dp[0][0][1] = V[0][0]
    for r in range(R):
        for c in range(C):
            if r == c == 0:
                continue
            v_rc = V[r][c]
            max_dp_before_row = 0 if r == 0 else max(dp[r - 1][c])
            # dp[r][c][0]
            v1 = 0 if c == 0 else dp[r][c - 1][0]
            dp[r][c][0] = max(v1, max_dp_before_row)
            # dp[r][c][1]
            v1 = 0 if c == 0 else max(dp[r][c - 1][1], dp[r][c - 1][0] + v_rc)
            v2 = 0 if r == 0 else (max_dp_before_row + v_rc)
            dp[r][c][1] = max(v1, v2)
            # dp[r][c][2], dp[r][c][3]
            for n in range(2, 4):
                dp[r][c][n] = 0 if c == 0 else max(dp[r][c - 1][n], dp[r][c - 1][n - 1] + v_rc)
    print(max(dp[R-1][C-1]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    R, C, K = list(map(int, input().split()))
    # dp[r][c][n]: r行目でn個のアイテムを拾う場合の(r, c)でのアイテムの価値の合計の最大
    dp_0 = [[0 for _ in range(C)] for _ in range(R)]
    dp_1 = [[0 for _ in range(C)] for _ in range(R)]
    dp_2 = [[0 for _ in range(C)] for _ in range(R)]
    dp_3 = [[0 for _ in range(C)] for _ in range(R)]
    V = [[0 for _ in range(C)] for _ in range(R)]
    for _ in range(K):
        r, c, v = list(map(int, input().split()))
        V[r - 1][c - 1] = v
    dp_1[0][0] = V[0][0]
    for r in range(R):
        for c in range(C):
            if r == c == 0:
                continue
            v_rc = V[r][c]
            max_dp_before_row = 0 if r == 0 else max(dp_0[r - 1][c], dp_1[r - 1][c], dp_2[r - 1][c], dp_3[r - 1][c])
            # dp[r][c][0]
            v1 = 0 if c == 0 else dp_0[r][c - 1]
            dp_0[r][c] = max(v1, max_dp_before_row)
            # dp[r][c][1]
            v1 = 0 if c == 0 else max(dp_1[r][c - 1], dp_0[r][c - 1] + v_rc)
            v2 = 0 if r == 0 else (max_dp_before_row + v_rc)
            dp_1[r][c] = max(v1, v2)
            # dp[r][c][2], dp[r][c][3]
            dp_2[r][c] = 0 if c == 0 else max(dp_2[r][c - 1], dp_1[r][c - 1] + v_rc)
            dp_3[r][c] = 0 if c == 0 else max(dp_3[r][c - 1], dp_2[r][c - 1] + v_rc)
    print(max(dp_0[R-1][C-1], dp_1[R-1][C-1], dp_2[R-1][C-1], dp_3[R-1][C-1]))


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

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = input()
d = defaultdict(list)
for i in range(N):
    for j in range(i + 1, N):
        w = S[i:j+1]
        if len(d[w]) == 0:
            d[w].append((i, j))
        elif d[w][-1][-1] < i:
            d[w].append((i, j))

ans = 0
for k, v in d.items():
    if len(v) <= 1:
        continue
    ans = max(ans, len(k))
print(ans)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = input()
dp = [[0] * 5005 for _ in range(5005)]

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j - i)
        ans = max(now, ans)
print(ans)
### BUGGY CODE ###

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

ans = 0

for i in range(n):
    ai = a[i]
    for j in range(n):
        if i == j:
            continue

        if ai % a[j] == 0:
            break

    else:
        ans += 1

print(ans)

### FIXED CODE ###

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)
### BUGGY CODE ###

n, k, q = tuple(map(int, input().split()))
scores = [k]*n
for i in range(q):
    answered = int(input()) - 1
    scores[answered] += 1
    scores = [v - 1 for v in scores]
for i in range(n):
    result = "Yes" if scores[i] > 0 else "No"
    print(result)

### FIXED CODE ###

n, k, q = tuple(map(int, input().split()))
answereds = [0]*n
for i in range(q):
    answered = int(input()) - 1
    answereds[answered] += 1
for i in range(n):
    result = "Yes" if q-answereds[i] < k else "No"
    print(result)
### BUGGY CODE ###

S = input()
N = len(S)

tmp = S
a = 0
b = 0
c = 0
count = 0
if len(tmp)-1 == b:
    a = 1

while a == 0:
    if tmp[b] != tmp[b+1]:
        count += 1
        #print('取り除くもの')
        #print(tmp[b:b+2])
        tmp = tmp[:b] + tmp[b+2:]
        #print('取り除いた後')
        #print(tmp)
        b = 0
        c += 1
        if len(tmp)-1 == b or len(tmp) == 0: 
            a = 1

    else:
        b += 1
        if len(tmp)-1 == b or len(tmp) == 0: 
            a = 1

print(str(count*2))

### FIXED CODE ###

S = input()
N = len(S)
c0 = S.count("0")
c1 = S.count("1")
 
print(2*min(c0, c1))
### BUGGY CODE ###

num = input()
str_list = input().split(" ")
 
yes = True
 
for index, s in enumerate(str_list):
	if s in str_list[:index]:
		yes = False
		break
if yes:
	print("YES")
else:
	print("NO")

### FIXED CODE ###

num = input()
str_list = input().split(" ")
 
yes = True
num_dict = {}
for s in str_list:
	if s in num_dict:
		yes = False
		break
	else:
		num_dict[s] = 1
if yes:
	print("YES")
else:
	print("NO")
### BUGGY CODE ###

k=int(input())
ans=0
import itertools
import math
from functools import reduce
s=list(range(1,k+1))
s=s+s+s
def gcd(*numbers):
    return reduce(math.gcd, numbers)
from  itertools import combinations
q=[]
for i in range(1,k+1):
    for j in range(1,k+1):
        q.append(gcd(i,j))
for i in q:
    for j in range(1,k+1):
        ans+=gcd(i,j)
    
print(ans)

### FIXED CODE ###

k=int(input())
ans=0
import itertools
import math
from functools import reduce
s=list(range(1,k+1))
s=s+s+s
def gcd(*numbers):
    return reduce(math.gcd, numbers)
from  itertools import combinations
q=[]
for i in range(1,k+1):
    for j in range(1,k+1):
        q.append(gcd(i,j))
for i in q:
    for j in range(1,k+1):
        ans+=gcd(i,j)
    
print(ans)
### BUGGY CODE ###

from scipy.misc import comb
n=int(input())
A=list(map(int,input().split()))

A.sort()
max_,num=0,0
for a in A:
  if max_<comb(A[-1],a):
    max_=comb(A[-1],a)
    num=a
print(A[-1],num)

### FIXED CODE ###

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

A.sort()
num=float('inf')
for i in range(n-1):
  if abs(num-A[-1]/2)>abs(A[i]-A[-1]/2):
    num=A[i]
print(A[-1],num)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[N-1]

is_prime = [True] * (A_max+1)
is_prime[0] = False

for i in range(1, A_max):
    if i not in A_list:
        is_prime[i] = False


for i in A_list:
    if not is_prime[i]:
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    if A_list.count(i) >= 2:
        is_prime[i] = False

print(is_prime.count(True))


### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[N-1]

is_prime = [False] * (A_max+1)


for i in A_list:
    is_prime[i] = True

x = -1
for i in A_list:
    if not is_prime[i]:
        continue
    elif x == i:
        is_prime[i] = False
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    x = i

count = 0
for i in A_list:
    if is_prime[i]:
        count += 1


print(count)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])
### BUGGY CODE ###

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=1000000000000000000

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
        if multi_sum > LIMIT:
            multi_sum=-1
else:
    multi_sum=0

print(multi_sum)


### FIXED CODE ###

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=1000000000000000000

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
        if multi_sum > LIMIT:
            multi_sum=-1
            break
else:
    multi_sum=0

print(multi_sum)
### BUGGY CODE ###

def ehand(n,a):
    for i in range(n):
        print max(a[:i]+a[(i+1):])
 
if __name__ == '__main__':
    n = int(raw_input())
    a = []
    a = [raw_input() for i in range(n)]

    ehand(n,map(int,a))

### FIXED CODE ###

import copy
def calcmax(a,b,fst,scd,n):
    for i in xrange(n):
        if fst == a[i]:
            count = i

    for i in xrange(n):
        if count == i:
            print scd
        else:
            print fst

if __name__ == '__main__':
    n = int(raw_input())
    a = [int(raw_input()) for i in xrange(n)]
    print("")

    fst = max(a)

    b = copy.deepcopy(a)
    b.remove(fst)

    scd = max(b)

    calcmax(a,b,fst,scd,n)
### BUGGY CODE ###

ss = input().split()
N = int(ss[0])
K = int(ss[1])
Q = int(ss[2])
As = []

SCORE = [K] * N

for i in range(Q):
  XX = map(lambda x: x - 1, SCORE)
  SCORE = list(XX)
  SCORE[int(input())-1] += 1
for i in range(N):
  if(SCORE[i]<1):
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

ss = input().split()
N = int(ss[0])
K = int(ss[1])
Q = int(ss[2])
As = []

SCORE = [0] * N

for i in range(Q):
  SCORE[int(input())-1] += 1
for i in range(N):
  if(SCORE[i]<= Q-K):
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
MOD = 998244353

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

n = int(input())
xd = [tuple(map(int, input().split())) for _ in range(n)]
xd.sort()
x, d = zip(*xd)

s = SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
for i in range(n)[::-1]:
    r = bisect_left(x, x[i]+d[i])
    s.update(i, max(r-1, s.query(i, r)))

dp = [[0] * 2 for _ in range(n)]
dp[-1][0], dp[-1][1] = 1, 1

for i in range(n-1)[::-1]:
    dp[i][0] = dp[i+1][0] + dp[i+1][1] % MOD
    dp[i][1] = dp[s.get(i)][0]

print(sum(dp[0]) % MOD)


### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right
input = lambda: sys.stdin.readline()
MOD = 998244353

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def get(self, i):
        return self.data[self.n + i]

n = int(input())
xd = [tuple(map(int, input().split())) for _ in range(n)]
xd.sort()
x, d = zip(*xd)

s = SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
for i in range(n)[::-1]:
    r = bisect_left(x, x[i]+d[i])
    s.update(i, max(r-1, s.query(i, r)))

dp1, dp2 = [0] * n, [0] * n
dp1[-1], dp2[-1] = 1, 1

for i in range(n-1)[::-1]:
    dp1[i] = dp1[i+1] + dp2[i+1] % MOD
    dp2[i] = dp1[s.get(i)]

print((dp1[0] + dp2[0]) % MOD)
### BUGGY CODE ###

#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

def main():
    s = input()
    K = int(input())
    c = Counter(s)

    se = set()
    for k, v in sorted(c.items()):
        for i in range(len(s)):
            if s[i] == k:
                for j in range(i + 1, len(s) + 1):
                    se.add(s[i:j])
        if len(se) > K:
            break

    print(list(sorted(list(se)))[K - 1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

def main():
    s = input()
    K = int(input())
    c = Counter(s)

    se = set()
    for k, v in sorted(c.items()):
        for i in range(len(s)):
            for n in range(1, 6):
                if s[i] == k and i + n <= len(s):
                    se.add(s[i:i+n])
        if len(se) > K:
            break

    print(list(sorted(list(se)))[K - 1])

if __name__ == '__main__':
    main()