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

import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort(reverse = True)
    q = []
    ans = 0
    j = N-1
    for i in range(M-1, -1, -1):
        while j >=0 and AB[j][0] <= M-i:
            a, b = AB[j]
            heapq.heappush(q, -b)
            j -= 1
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import heapq
def main():

    N, M = map(int, input().split())
    task = []
    for _ in range(N):
        A, B = map(int, input().split())
        task.append([A, B])
    task.sort()

    hq = []
    ans = 0
    for i in range(1, M+1):
        while task and task[0][0]<= i:
            _, v = heapq.heappop(task)
            heapq.heappush(hq, -v)
        if hq:
            v = heapq.heappop(hq)
            ans += -v
    return ans

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

import sys
N,Y = map(int,input().split())
satu = [10000,5000,1000]
flag = 0
for a in range(N+1):
    for b in range(N+1):
        for c in range(N+1):
            if a+b+c == N:
                if satu[0]*a+satu[1]*b+satu[2]*c == Y:
                    print(a,b,c)
                    flag = 1
                    sys.exit()
if flag == 0:print(-1,-1,-1)

### FIXED CODE ###

N,Y = map(int,input().split())
flag = 0
for a in range(N+1):
    for b in range(N+1):
        if a+b > N:
            break
        elif (N-(a+b))*1000 == Y-(10000*a+5000*b):
            A,B,C = a,b,N-(a+b)
            flag = 1
if flag == 0:print(-1,-1,-1)
else:print(A,B,C)
### BUGGY CODE ###

N = int(input())

for n in range(1,N+1):
  ans = 0
  check = False
  for x in range(1,n):
    for y in range(x,n):
      for z in range(y,n):
        if (x**2 + y**2 + z**2 + x*y + y*z + z*x) == n:
          if x == y and y == x and z == x:
            ans += 1
          elif x == y  or z == x or y == z:
            ans += 3
          elif x != y and y != z and z != x:
            ans += 6
          check = True
          break
      if check:
        break
    if check:
      break
  print(ans)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10001)]

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

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

import math

def f(n):
  lx = math.ceil(math.sqrt(n))
  ans = 0

  for x in range(1, lx):
    x2 = x ** 2

    ly = math.ceil(math.sqrt(max(1, n - x2)))

    for y in range(1, ly):
      y2 = y ** 2
      lz = math.ceil(math.sqrt(max(1, n - x2 - y2 - (x * y))))

      for z in range(1, lz):
        z2 = z ** 2

        if x2 + y2 + z2 + x * y + y * z + z * x == n:
          ans += 1

  return ans

def main():
  N = int(input())

  for i in range(1, N+1):
    print(f(i))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import math


def main():
  N = int(input())

  dp = [0] * N

  lx = math.ceil(math.sqrt(N))

  for x in range(1, lx):
    x2 = x ** 2

    ly = math.ceil(math.sqrt(max(1, N - x2)))

    for y in range(1, ly):
      y2 = y ** 2
      lz = math.ceil(math.sqrt(max(1, N - x2 - y2 - (x * y))))

      for z in range(1, lz):
        z2 = z ** 2

        v = x2 + y2 + z2 + x * y + y * z + z * x
        if(v <= N):
          dp[v-1] += 1

  for v in dp:
    print(v)

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

K,S = map(int,input().split())
flag = 1
s = 0
for l in range(K+1):
  for m in range(K+1):
    for n in range(K+1):
      if l+m+n == S:
        s = s+1
print(s)

### FIXED CODE ###

K,S = map(int,input().split())
flag = 1
s = 0
for l in range(K+1):
  for m in range(K+1):
    if (0 <= S-l-m)and(S-l-m<=K):
      s = s+1
print(s)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

d = [k] * n
for i in a:
    tmp = d[i-1]
    d = [x-1 for x in d]
    d[i-1] = tmp

for x in d:
    if x > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

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


for _ in range(q):
    d[int(input())] += 1

for x in range(1, n+1):
    if k - q + d[x] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from itertools import product
while(True):
    H,W = map(int,input().split())
    if not H: break
    ma = 0
    for i in range(H):
        ma |= (int(input().replace(".","0").replace("*","1"),2) << ((H-i-1)*W))
    flag = False
    hw = [[h,w] for h,w in product(range(H,0,-1),range(W,0,-1))]
    hw = sorted(hw,key=lambda x: -x[1]*x[0])
    ans = 0
    for h,w in hw:
        for i,j in product(range(H-h+1),range(W-w+1)):
            b = (sum([((2**w-1) << j) << k*W for k in range(h)]) ) << i*W
            c = ma&b
            if not c :flag = True; ans = max(ans,h*w); break
        else:
            continue
        if flag: break
    print(ans)



### FIXED CODE ###

# ref: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=924554#1
from itertools import product
while(True):
    H,W = map(int,input().split())
    if not H: break
    ma = [list(map(int,input().replace(".","1").replace("*","0")))+[0] for _ in range(H)]
    for i,j in product(range(1,H),range(W)):
        if ma[i][j]: ma[i][j] += ma[i-1][j]
    ans = 0
    for i in range(H):
        stk = []
        for j in range(W+1):
            cur = ma[i][j]
            if (not stk) or stk[-1][1] < cur:
                stk.append([j,cur])
            elif stk[-1][1] > cur:
                idx = j
                while stk and stk[-1][1] >= cur:
                    idx = stk[-1][0]
                    ans = max(ans,stk[-1][1]*(j-stk[-1][0]))
                    stk.pop()
                stk.append([idx,cur])
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = set()
c = [0]*n

for i in range(n):
  if a[n-1-i] ^ c[n-1-i]%2:
    b.add(n-i)
    for j in range(1, int((n-i)**0.5)+1):
      if (n-i)%j == 0 and j**2 != n-i:
        c[j-1] += 1
        c[(n-i)//j -1] += 1
      elif j**2 == n-i:
        c[j-1] += 1

print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

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

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.zeros(N)
for i in range(1, N):
  j = max(0, i-K)
  dp[i] = min(dp[j:i]+np.abs(h[i]-h[j:i]))
print(int(dp[N-1]))

### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [1] * n
cnt = Counter(a)

for i in range(n - 1):
    if check[i] == 0:continue
    if cnt[a[i]] > 1:check[i] = 0
    for j in range(i + 1, n):
        if a[j] % a[i] == 0:check[j] = 0

ans = sum(check)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

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

import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        for u, c in links[v]:
            if u in visited:
                continue
            if c == e:
                q.appendleft((d, u, c))
            else:
                q.append((d + 1, u, c))
    return -1


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin:
    p, q, c = map(int, line.split())
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))


### FIXED CODE ###

import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c in links[v]:
                for u in links[v][c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))
### BUGGY CODE ###

N, K= map(int, input().split())
H=list(map(int, input().split()))
if K>=len(H):
    print(0)
else:
    if K==0:
        print(sum(H))
    else:
        for i in range(K):
            H=sorted(H)
            H.pop(-1)
        print(sum(H))

### FIXED CODE ###

N, K= map(int, input().split())
H=list(map(int, input().split()))
if K>=len(H):
    print(0)
else:
    if K==0:
        print(sum(H))
    else:
        H=sorted(H)
        print(sum(H[:-K]))
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    flag = True
    for j in range(0, i+1):
        if p[i] > p[j]:
            flag = False
            break

    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

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

m = p[0]
ans = 0
for i in range(n):
    if p[i] <= m:
        ans += 1
        m = min(m, p[i])

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

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

x = 0
now = 0
result = 0
for i in range(n+1):
    x = i
    now = (((a * x)//b)) - (a * (x//b))
    #now = math.ceil(((a * x)/b)) - (a * math.ceil(x/b))
    #print("now=",now,"x=",x)
   
    result = max(result,now)

print(result)
    



### FIXED CODE ###


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

x = min(b-1,n)

print((((a * x)//b)) )
### BUGGY CODE ###

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

list = 0
for i in range(N-K+1):
    p = pn[i:i+K]
    list = max(list, sum(p))

ans = (list+K)/2
print('{:.6f}'.format(ans))


### FIXED CODE ###

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)
### BUGGY CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = []
  B = []
  while a != pre[a]:
    a = pre[a]
    A.append(a)
  while b != pre[b]:
    b = pre[b]
    B.append(b)
  if a != b:
    pre[b] = a
    for aa in A:
      pre[aa] = a
    for bb in B:
      pre[bb] = a
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))
### BUGGY CODE ###

# ABC169 B Multiplication 2

n = int(input())

a_list = [int(x) for x in input().split()]

ans = 1
for i in range(n):
    ans *= a_list[i]

if ans > 10**18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

# ABC169 B Multiplication 2

from collections import deque

n = int(input())

a_list = [int(x) for x in input().split()]

if min(a_list) == 0:
    print("0")
else:
    a_dq = deque(a_list)
    ans = 1
    for i in range(n):
        ans *= a_dq.popleft()
        if ans > 10**18:
            break

    if ans > 10**18:
        print("-1")
    else:
        print(ans)
### BUGGY CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    import collections
    didx = collections.defaultdict(int)

    for c in t:
        if c not in d.keys():
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

### FIXED CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    import collections
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        # とり切っていない場合
        posidx = bisect.bisect_right(poslist, currentidx)

        if posidx >= len(poslist):
            # とれないなら次のループでとったことにする
            i_loop += 1
            currentidx = poslist[0]
        else:
            # 同じループでとれるなら取って、現在位置を更新
            pos = poslist[posidx]
            currentidx = pos

    print(len(s)*i_loop + currentidx + 1)

main()
### BUGGY CODE ###

h,n,*t=map(int,open(0).read().split())
d=[0]+[9e9]*h
for a,b in zip(*[iter(t)]*2):
 for j in range(h+1):d[j]=min(d[j],d[max(0,j-a)]+b)
print(d[h])

### FIXED CODE ###

h,n,*t=map(int,open(0).read().split())
dp=[10**18]*(h+1)
dp[0]=0
for a,b in zip(*[iter(t)]*2):
    for j in range(h+1):
        dp[j]=min(dp[j],dp[max(0,j-a)]+b)
print(dp[h])
### BUGGY CODE ###

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

B = [0] * (N + 1)
for i in range(1, N + 1):
    print(A.count(i))

### FIXED CODE ###

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

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

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

from collections import defaultdict
import math
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def is_prime(n):
  for prime in prime_table:
    if n % prime == 0:
      return False
  else:
    return True

N, M = map(int, input().split())
p = 10 ** 9 + 7
prime_table = []
primes = defaultdict(int)
primes[1] = 0
n = 2
while n <= M:
  if n > math.sqrt(M) or is_prime(n):
    prime_table.append(n)
    while M % n == 0:
      primes[n] += 1
      M //= n
  n += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)

### FIXED CODE ###

from collections import defaultdict
import math
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def eratosthenes(limit):
  E = [1] * (limit + 1)
  E[0], E[1] = 0, 0
  prime_table = []
  for i, e in enumerate(E):
    if e:
      prime_table.append(i)
      for j in range(i, limit + 1, i):
        E[j] = 0
  return prime_table

N, M = map(int, input().split())
p = 10 ** 9 + 7
limit = int(math.sqrt(M)) + 1
prime_table = eratosthenes(limit)
primes = defaultdict(int)
primes[1] = 0
for prime in prime_table:
  if prime > M:
    break
  while M % prime == 0:
    primes[prime] += 1
    M //= prime
if M > 1:
  primes[M] += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)
### BUGGY CODE ###

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

tmp = []
for i in range(0, N-K+1):
    res = 1
    for j in range(K):
        res *= A[i+j]
    tmp.append(res)

for i in range(len(tmp) - 1):
    if tmp[i] - tmp[i+1] < 0:
        print('Yes')
    else:
        print('No')



### FIXED CODE ###

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

for i in range(N-K):
    if A[i] < A[i+K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n, K = map(int, input().split())
a = list(map(int, input().split()))
for k in range(min(K, 100)):
    an = [0] * n
    for i in range(n):
        if an[i] < n:
            an[i] += 1
        for j in range(1, a[i]+1):
            if i - j >= 0 and an[i-j] < n:
                an[i-j] += 1
            if i + j < n and an[i+j] < n:
                an[i+j] += 1
    else:
        a = an
print(*a)


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(k):
        imos = [0] * (n + 1)
        for i in range(n):
            imos[max(0, i - a[i])] += 1
            imos[min(n, i + a[i] + 1)] -= 1
        for i in range(1, n):
            imos[i] += imos[i-1]
        imos.pop()
        a = imos
        if min(a) == n:
            break 
    print(*a)
main()
### BUGGY CODE ###

s = input()
k = int(input())
ans_list = []

for i in range(len(s)):
    s_list = [s[j:j+i+1] for j in range(len(s)-i)]
    s_set_list = list(set(s_list))
    for m in range(len(s_set_list)):
        ans_list.append(s_set_list[m])

ans_list.sort()
print(ans_list[k-1])
# print(ans_list)


'''
ans_list = []
s_list = [s[i] for i in range(len(s))]
s_set_sorted = sorted(set(s_list))
for i in range(len(s_set_sorted)):
    ans_list.append(s_set_sorted[i])
if k <= len(ans_list):
    ans_list.sort()
    print(ans_list[k-1])
    exit()

s_queue = []
for i in range(len(s)-1):
    s_queue.append(s[i:i+2])
s_queue_set_sorted = sorted(set(s_queue))
for i in range(len(s_queue_set_sorted)):
    ans_list.append(s_queue_set_sorted[i])
if k <= len(ans_list):
    ans_list.sort()
    print(ans_list[k-1])
    exit()

print(s_set_sorted)
'''

### FIXED CODE ###

s = input()
k = int(input())
ans_list = []

for i in range(5):
    s_list = [s[j:j+i+1] for j in range(len(s)-i)]
    s_set_list = list(set(s_list))
    for m in range(len(s_set_list)):
        ans_list.append(s_set_list[m])

ans_list.sort()
print(ans_list[k-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])

B = []
for _ in range(M):
    b, c = map(int, input().split())
    B += [c] * b
    
B.sort(reverse = True)

x = min(N, len(B))

for i in range(x):
    A[i] = max(A[i], B[i])
    
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])
C = sorted([[int(i) for i in input().split()] for i in range(M)], reverse = True, 
           key = lambda x: x[1])

cnt = 0
B = []
for i in range(M):
    if cnt > N:
        break
    B += [C[i][1]] * C[i][0]
    cnt += C[i][0]
    
B.sort(reverse = True)

x = min(N, len(B))

for i in range(x):
    A[i] = max(A[i], B[i])
    
print(sum(A))
### BUGGY CODE ###

d=[0]*13
d[0]=1
mul=1
mulmod=1
t=input()[::-1]
mod=10**9+7
zero=[0]*13

for c in t:
    e=zero[:]
    if c=="?":
        for i in range(10):
            for j in range(13):
                k=(i*mulmod+j)%13
                e[k]+=d[j]
                e[k]%=mod
    else:
        for j in range(13):
            k=(int(c)*mulmod+j)%13
            e[k]+=d[j]
            e[k]%=mod
    d=e[:]
    mul*=10
    mulmod=mul%13
print(d[5])



### FIXED CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)