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

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

lst = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
#        print ('i, j=', i, j)
        lst += [s[i:j]]

lst.sort()
#print (lst)
k = 0
flag = 0
ans = str()
check = True
while check:
    if ans != lst[flag]:
        #print ('k', k)
        k += 1
    ans = lst[flag]
    #print ('ans=', ans)
    flag += 1
    if k == K:
        ans = ''.join(ans)
        print(ans)
        check = not check


### FIXED CODE ###

#全探索-->len(s) = 50程度までしか通らない
s = list(input())
K = int(input())

lst = []
for i in range(len(s)):
    for j in range(i+1, min(len(s)+1, i+1+K)):
#        print ('i, j=', i, j)
        lst += [s[i:j]]

lst.sort()
#print (lst)
k = 0
flag = 0
ans = str()
check = True
while check:
    if ans != lst[flag]:
        #print ('k', k)
        k += 1
    ans = lst[flag]
    #print ('ans=', ans)
    flag += 1
    if k == K:
        ans = ''.join(ans)
        print(ans)
        check = not check
### BUGGY CODE ###

if __name__=="__main__":
    count = 0
    idx = int(input())
    n = list(map(int,input().split(" ")))
    while True:
        for i in range(idx):
            if n[i]|1 ==n[i]:
                print(count)
                exit()
        count+=1

### FIXED CODE ###

if __name__=="__main__":
    count = 0
    idx = int(input())
    n = list(map(int,input().split(" ")))
    while True:
        for i in range(idx):
            if n[i]|1==n[i]:
                print(count)
                exit()
            else:
                n[i]=n[i]>>1
        count+=1
### BUGGY CODE ###

h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
# C[hCX][w]
ans = 10 ** 20
for s in range(2 ** (h - 1)):
    yoko = bin(s).count("1")
    white = [0] * (yoko + 2)
    cnt = 0
    # 横分割を足しておく
    cnt += yoko
    outflag = 0
    for j in range(w):
        now = 0
        for i in range(h):
            if outflag:
                break
            white[now] += int(C[i][j])
            if white[now] > k:
                # 縦分割をする時はkを超えた時。
                # kを超えたら1つ前で割ったことにするので、
                # その列をもう1回やり直す必要あり
                cnt += 1
                # 同じjのところをi=[0,i]までやり直す
                # 初期化
                white = [0] * (yoko + 2)
                now = 0
                # 0からiまでやり直す
                for t in range(i + 1):
                    white[now] += int(C[t][j])
                    if white[now] > k:
                        outflag = 1
                        break
                    if (s >> t) & 1 == 1:
                        now += 1
                continue
            if (s >> i) & 1 == 1:
                now += 1
        if outflag:
            break
    if outflag:
        outflag = 0
        continue
    ans = min(cnt, ans)
print(ans)


### FIXED CODE ###

h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
# C[hCX][w]
ans = 10 ** 20
for s in range(2 ** (h - 1)):
    yoko = bin(s).count("1")
    white = [0] * (yoko + 2)
    cnt = 0
    # 横分割を足しておく
    cnt += yoko
    outflag = 0
    for j in range(w):
        now = 0
        for i in range(h):
            if outflag:
                break
            white[now] += int(C[i][j])
            if white[now] > k:
                # 縦分割をする時はkを超えた時。
                # kを超えたら1つ前で割ったことにするので、
                # その列をもう1回やり直す必要あり
                cnt += 1
                # 同じjのところをi=[0,i]までやり直す
                # 初期化
                white = [0] * (yoko + 2)
                now = 0
                # 0からiまでやり直す
                for t in range(i + 1):
                    white[now] += int(C[t][j])
                    if white[now] > k:
                        outflag = 1
                        break
                    if (s >> t) & 1 == 1:
                        now += 1
                continue
            if (s >> i) & 1 == 1:
                now += 1
        if outflag:
            break
    if outflag:
        outflag = 0
        continue
    ans = min(cnt, ans)
print(ans)
### BUGGY CODE ###

a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
else:
    for i in range(1,n+1):
        t = int(a*i/b)-a*int(i/b)
        score = max(score,t)
    print(score)

### FIXED CODE ###

a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
elif(b==1):
    print(0)
else:
    c = int(n/b)
    score = 0
    for i in range(1,c+1):
        n_ = b*i-1
        t = int(a*n_/b)-a*int(n_/b)
        score = max(score,t)
    t = int(a*n/b)-a*int(n/b)
    score = max(score,t)
    print(score)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
b=[]
for i in range(0,n):
  b.append(a[i])
  if min(b)==a[i]:
    ans=ans+1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
m=a[0]
for i in range(0,n):
  if a[i]<=m:
    m=a[i]
    ans=ans+1
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
sign=0
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        if s[j]==s[i+sign] and i+2*sign<j:
            sign+=1

        else:
            ans=max(sign,ans)
            sign=0
ans=max(sign,ans)
print(ans)

### FIXED CODE ###

def main():

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

    i,j=0,1
    ans=0
    while j<n:
        if s[i:j] in s[j:]:
            if j-i>ans: ans=j-i
            j+=1
        else:
            i+=1
            j+=1

    print(ans)

            

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

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf


n,x,y = imap()
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        dist.append(min(abs(i-j), abs(i-x)+abs(j-y)+1, abs(i-y)+abs(j-x)+1))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])


### FIXED CODE ###

import collections as col


n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [float("inf")] * (N)
dp[0] = 0

for n in range(1, N):
    k = max(0, n - K)
    dp[n] = min(abs(h[n] - h[i]) + dp[i] for i in range(k, n))

print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf') for _ in range(n)]
dp[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        if i+j <= n-1:
            temp = dp[i] + abs(l[i+j] - l[i])
            if temp < dp[i+j]:
                dp[i+j] = temp

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

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

def closest(x):
    res = None
    min_diff = None
    for k in a:
        if k == m:
            continue
        diff = abs(k - x)
        if res is None or min_diff > diff:
            min_diff = diff
            res = k
    return res

def comb(n, k):
    if n-k < k:
        return comb(n, n-k)
    res = 1
    for i in range(n, n-k):
        res *= i
    for i in range(2, k):
        res //= i
    return res


if m % 2 == 0:
    print(m, closest(m // 2))
else:
    x1 = closest(m // 2)
    x2 = closest(m // 2 + 1)
    if comb(m,x1) > comb(m,x2):
        print(m, x1)
    else:
        print(m, x2)


### FIXED CODE ###

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

def closest(x):
    res = None
    min_diff = None
    for k in a:
        if k == m:
            continue
        diff = abs(k - x)
        if res is None or min_diff > diff:
            min_diff = diff
            res = k
    return res

print(m, closest(m // 2))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

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

if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

if 0 in a:
    print(0)
    exit()

for i in range(1,n):
    ans *= a[i]
    if ans > 10 ** 18:
        print(-1)
        exit()

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

R, C, K = map(int, input().split())
# = int(input())
p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point = [[[0, 0, 0] for _ in range(C)] for _ in range(R)]

point[0][0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point[r][c][0], point[r][c][1], point[r][c][2]  
    if c < C - 1:
      x = maps[r][c+1]
      y = point[r][c+1]
      y[0] = max(y[0], x, a)
      y[1] = max(y[1], a + x, b)
      y[2] = max(y[2], b + x, d)
      point[r][c+1] = y
    if r < R - 1:
      point[r+1][c][0] = max(point[r+1][c][0], maps[r+1][c] + max(a, b, d))     


print(max(point[-1][-1][0:3]))

### FIXED CODE ###

R, C, K = map(int, input().split())
# = int(input())
p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point1 = [[0 for _ in range(C)] for _ in range(R)]
point2 = [[0 for _ in range(C)] for _ in range(R)]
point3 = [[0 for _ in range(C)] for _ in range(R)]

point1[0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point1[r][c], point2[r][c], point3[r][c]  
    if c < C - 1:
      x = maps[r][c+1]
      point1[r][c+1] = max(point1[r][c+1], x, a)
      point2[r][c+1] = max(point2[r][c+1], a + x, b)
      point3[r][c+1] = max(point3[r][c+1], b + x, d)
    if r < R - 1:
      point1[r+1][c] = maps[r+1][c] + max(a, b, d)


print(max(point1[-1][-1], point2[-1][-1], point3[-1][-1]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
m0 = 10**9+7
for i in range(0,N-1):
    sumtemp = 0
    for j in range(i+1,N):
        sumtemp += A[j]
    ans = (ans + A[i] * sumtemp) % m0
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = 0
    m0 = 10**9+7
    Ar = [0]*N
    sum0 = 0
    for i in reversed(range(N)):
        sum0 = (sum0 + A[i]) % m0
        Ar[i] = sum0

    for i in range(N-1):
        ans = (ans + A[i] * Ar[i+1]) % m0
    print(ans)

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

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 24 16:22:35 2019
 
@author: Owner
"""
 
N, K = map(int, input().split())
 
h = list(map(int, input().split()))
 
dp = [0]
 
for n in range(1, N):
    temp = float("inf")
    for k in range(1,K+1):
        if n-k < 0:
            continue
        temp = min(temp, dp[n-k] + abs(h[n]-h[n-k]))
    dp.append(temp)
#print(dp)
print(dp[N-1])

### FIXED CODE ###

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

import numpy as np

N, K = map(int, input().split())
 
h = np.array(list(map(int, input().split())))
 
dp = np.zeros(N)
 
for n in range(1, N):
    k = min(K, n)
    temp = np.min(dp[n-k:n] + np.abs(h[n]-h[n-k:n]))
    dp[n] = temp
print(int(dp[-1]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 998244353
half = pow(2, mod - 2, mod)
maxA = max(A)


def main():
    cnt = [0] * (maxA + 1)
    for Ai in A:
        cnt[Ai] += 1

    w = [pow(i, mod-2, mod) for i in range(maxA + 1)]
    for i in range(1, maxA + 1):
        for j in range(i * 2, maxA + 1, i):
            w[j] = (w[j] - w[i]) % mod

    def sum_cross(arr):
        s = 0
        s2 = 0
        for a in arr:
            s += a
            s2 += a ** 2
            s %= mod
            s2 %= mod
        return ((((s ** 2) % mod - s2) % mod) * half) % mod

    ans = 0
    for i in range(1, maxA + 1):
        Ai = []
        for j in range(i, maxA + 1, i):
            for k in range(cnt[j]):
                Ai.append(j)
        ans += w[i] * sum_cross(Ai)
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 998244353
half = pow(2, mod - 2, mod)
maxA = max(A) + 1


def main():
    cnt = [0] * maxA
    for Ai in A:
        cnt[Ai] += 1

    w = [pow(i, mod-2, mod) for i in range(maxA)]
    for i in range(1, maxA):
        for j in range(i * 2, maxA, i):
            w[j] = (w[j] - w[i]) % mod

    ans = 0
    for i in range(1, maxA):
        s = s2 = 0
        for j in range(i, maxA, i):
            s = (s + (j * cnt[j])) % mod
            s2 = (s2 + (j * j * cnt[j])) % mod
        ans += w[i] * ((((s ** 2) % mod - s2) % mod) * half) % mod
        ans %= mod
    print(ans)


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

S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3

	dp[i][1]%=mod
	dp[i][2]%=mod
	dp[i][3]%=mod
	all%mod


print dp[-1][-1]%mod


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

N = input()
a = list(map(int, input().split()))
ans = 0
count = 1
for i in range(len(a)):
    if a[i] != 0:
        for j in range(i + 1, len(a)):
            if a[j] == a[i]:
                count += 1
                a[j] = 0
        if a[i] > count: ans += count
        elif a[i] < count: ans += (count - a[i])
        a[i] = 0
        count = 1
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
i = 1
cnt = 1
key = a[0]
ans = 0
while True:
    if i >= len(a):
        break
    if key == a[i]:
        cnt += 1
    else:
        if key != cnt:
            if cnt > key:
                ans += cnt - key
            else:
                ans += cnt
        cnt = 1
        key = a[i]
    
    i += 1

if key != cnt:
    if cnt > key:
        ans += cnt - key
    else:
        ans += cnt

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

N = int(input())
print(sum([i for i in range(N)]))

### FIXED CODE ###

N = int(input())

if N % 2 == 0:
  print(int((N // 2) * (N - 1)))
else:
  print(int(N * ((N - 1) // 2)))
### BUGGY CODE ###

from sys import stdin, setrecursionlimit
import collections


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    input = stdin.buffer.readline
    s = input()[:-1].decode()
    N = len(s)
    mod = [0] * N
    for i in range(N):
        mod[i] = int(s[i:N]) % 2019

    fac, finv = initialize_cmb(N)

    counter = collections.Counter(mod)

    ans = 0

    for k, v in counter.items():
        if k == 0:
            ans += v
        elif v > 1:
            ans += cmb(v, 2, fac, finv)

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.readline
    s = list(input()[:-1])[::-1]
    N = len(s)
    p10 = [1]
    tmp = 1
    for _ in range(N - 1):
        tmp = tmp * 10 % 2019
        p10.append(tmp)
    mod = []
    tmp = 0
    for num, p in zip(s, p10):
        tmp = (tmp + int(num) * p) % 2019
        mod.append(tmp)

    mod.sort()
    mod.insert(0, 0)

    ans = 0
    count = 1
    for i in range(1, N + 1):
        if mod[i] == mod[i - 1]:
            count += 1
        else:
            ans += count * (count - 1) // 2
            count = 1
    ans += count * (count - 1) // 2
    print(ans)


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

m = int(input())
a = []
for _ in range(m):
  a.append(int(input()))

cs = [0]*m
c_maxs = [a[0]]

for i in range(1, m):
  cont = False
  for c, c_max in enumerate(c_maxs):
    if c_max < a[i]:
      cs[i] = c
      c_maxs[c] = a[i]
      cont = True
      break
  
  if not cont:
    cs[i] = len(c_maxs)
    c_maxs.append(a[i])

print(len(c_maxs))

### FIXED CODE ###

import bisect
m = int(input())
a = []
for _ in range(m):
  a.append(int(input()))

a = list(map(lambda x: -x, a))
m = len(a)

lis = [float('inf')]*m

for x in a:
  lis[bisect.bisect_right(lis, x)] = x

print(len([x for x in lis if not (x == float('inf'))]))
### BUGGY CODE ###

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


ave = sum(al) // len(al)
start = ave
ans = float("inf")
while True:
    tmp = 0
    for idx, a in enumerate(al):
        tmp += abs(start+ idx - a)
    if ans >= tmp:
        ans = tmp
    else:
        break
    start += 1

start = ave
while True:
    tmp = 0
    for idx, a in enumerate(al):
        tmp += abs(start +idx - a)
    if ans >= tmp:
        ans = tmp
    else:
        break
    start -= 1

print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
al = list(map(int,input().split()))

for i in range(n):
    al[i] -= i + 1

med = np.median(np.array(al))

ans = 0
for a in al:
    ans += abs(a-med)
print(int(ans))
### BUGGY CODE ###

N, M = map(int,input().split())
A = sorted(list(map(int, input().split())))
BC = [list(map(int, input().split())) for _ in range(M)]
li = []
cnt = 0
for b, c in sorted(BC, key=lambda x:x[1], reverse=True):
  cnt += b
  for _ in range(b):
    li.append(c)
for i in range(min(N,cnt)):
  if A[i] < li[i]:
    A[i] = li[i]
  else:
    break
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = sorted(list(map(int, input().split())))
BC = [list(map(int, input().split())) for _ in range(M)]
li = []
cnt = 0
for b, c in sorted(BC, key=lambda x:x[1], reverse=True):
  cnt += b
  for _ in range(b):
    li.append(c)
  if cnt >= N:
    break
for i in range(min(N,cnt)):
  if A[i] < li[i]:
    A[i] = li[i]
print(sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0]*(n+1)
            self.depth = n.bit_length()

        def __iter__(self):
            psum = 0
            for i in range(self.size):
                csum = self.sum(i+1)
                yield csum - psum
                psum = csum
            raise StopIteration()

        def __str__(self):  # O(nlogn)
            return str(list(self))

        def sum(self, i):
            # [0, i) の要素の総和を返す
            if not (0 <= i <= self.size): raise ValueError("error!")
            s = 0
            while i>0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            if not (0 <= i < self.size): raise ValueError("error!")
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, x):
            """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
            sum_ = 0
            pos = 0
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += 1 << i
            return pos + 1, sum_

        def __getitem__(self, key):
            if not (0 <= key < self.size): raise IndexError("error!")
            return self.sum(key+1) - self.sum(key)

        def __setitem__(self, key, value):
            # 足し算と引き算にはaddを使うべき
            if not (0 <= key < self.size): raise IndexError("error!")
            self.add(key, value - self[key])

    class BitImos:
        """
        ・範囲すべての要素に加算
        ・ひとつの値を取得
        の2種類のクエリをO(logn)で処理
        bit = BitImos(len(li))
        """
        def __init__(self, n):
            self.bit = Bit(n+1)

        def add(self, s, t, x):
            # [s, t)にxを加算
            self.bit.add(s, x)
            self.bit.add(t, -x)

        def get(self, i):
            return self[i]

        def __getitem__(self, key):
            # 位置iの値を取得
            return self.bit.sum(key+1)

    for i in range(k):
        bit = BitImos(n)
        for i in range(n):
            bit.add(max(0, i-a[i]), min(n, i+a[i]+1), 1)
        for i in range(n):
            a[i] = min(n, bit.get(i))
        if all((a[i]==n for i in range(n))):
            break

    for i in a:
        print(i, end = ' ')

if __name__ == '__main__':
    main()


### FIXED CODE ###

from copy import copy
import sys
input = sys.stdin.readline

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    for i 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(n):
            imos[i+1] += imos[i]
        a = copy(imos[:-1])
        if all((a[i]==n for i in range(n))):
            break

    for i in a:
        print(i, end = ' ')

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

from functools import reduce
n, *a = map(int, open(0).read().split())
ans = reduce(lambda x, y: x * y, a)
print([ans, -1, 0][10**18 < ans + 2*(ans == 0)])

### FIXED CODE ###

import sys
n = int(input())
a = sorted(map(int,input().split()))
ans = 1
if a[0] == 0:
  print(0)
else:
  for i in a:
    ans *= i
    if 1000000000000000000<ans:
      print(-1)
      sys.exit()
  print(ans)
### BUGGY CODE ###



S = str(input())
b = len(S)
n = (10**b+7)//13
a = str("")
ans = int(0)

for i in range(n):
    a = str(int(5) + int(13*i))
    a =a.zfill(b)
#    print(str(a))
    ans += 1
    for j in range(b):
        if S[j]!=a[j] and S[j]!="?":
            ans -=1
            break


print(ans%1000000007)



### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()