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

import copy
import collections

N = int(input())
A=[]
for j in range(N): 
    A.append(collections.deque(int(i) for i in input().split()))

day = 0
empty = [0] * N 
s = [i for i in range(N)]

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in s:
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = None
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][0])-1][0]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][0])-1)
                s = copy.copy(q)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if not(0 in empty):
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].popleft()

### FIXED CODE ###

import copy
import collections

N = int(input())
A=[]
for j in range(N): 
    A.append(collections.deque(int(i) for i in input().split()))

day = 0
empty = [0] * N 
s = [i for i in range(N)]

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in s:
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = None
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][0])-1][0]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][0])-1)
                s = copy.copy(q)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if not(0 in empty):
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].popleft()
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
res = 0
MOD = 10**9+7
nCk_2 = dict()
fact_t = [1]
for n in range(N):
    fact_t.append(fact_t[-1]*(n+1))
def comb(n, k):
    return (fact_t[n]//(fact_t[n-k]*fact_t[k]))%MOD
s = [1,-1]
for m in range(2):
    for i in range(K-1,N):
        res = (res + s[m]*int((A[i])*comb(i,K-1)))%MOD
    A = sorted(A, reverse=True)
print(res)


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
res = 0
MOD = 10**9+7
nCk_2 = dict()
fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n, k):
    return (fac[n]*((finv[k]*finv[n-k])%MOD))%MOD
s = [1,-1]
for m in range(2):
    for i in range(K-1,N):
        res = (res + s[m]*int((A[i])*comb(i,K-1)))%MOD
    A = sorted(A, reverse=True)
print(res)
### BUGGY CODE ###

from sys import stdin
import math
import itertools
import re
 
 
def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]
 
dp = {}
 
def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        l, r = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        cnt = cntAC(l, r, S[l-1:r])
        print(cnt)
    return
 
 
def cntAC(l, r, t):
    if l+r not in dp:
        dp[l+r] = len(re.findall(r'AC', t))
    return dp[l+r]
 
 
def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)
 
 
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

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

p = 0
for i in range(n):
    for j in range(i+1, n):
        if a[i] + a[j] == j-i:
            p += 1

print(p)

### FIXED CODE ###

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

d = {}
for i, ai in enumerate(a):
    l = ai + i+1
    if l in d:
        d[l] += 1
    else:
        d[l] = 1

p = 0
for i, ai in enumerate(a):
    r = i+1 - ai
    p += d.get(r, 0)

print(p)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(n**2):
    check = [1]*n
    flg = False
    i = -1
    while sum(check) != 0:
        i += 1
        if not check[i]:
            continue
        if len(a[i]) == 0:
            check[i] = 0
            continue
        (x,y) = a[i].popleft()
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            flg = True
            check[y-1] = 0
            a[y-1].popleft()
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    ans = 0
    l = []
    for i in range(K):
        l.append(p[i]+1)
    ans = sum(l)
    for i in range(K, N):
        l.append(p[i]+1)
        tmp = sum(l[-K:])
        if ans < tmp:
            ans = tmp
    print(ans/2)
resolve()

### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    l = [0]*N
    l[0] = p[0]+1
    for i in range(1, N):
        l[i] = l[i-1]+p[i]+1
    ans = l[K-1]
    for i in range(N-K):
        tmp = l[K+i]-l[i]
        if tmp > ans:
            ans = tmp
    print(ans/2)
resolve()
### BUGGY CODE ###

N, M = map(int, input().split())

ans = 1
for k in range(1, M + 1):
    if(0 == M % k):
        if((M // k) < k):
            break
        if((M // k) > N - 1):
            ans = max(ans, k)
#            print("k = {}, M/k = {}, ans = {}".format(k, M//k, ans))
#        else:
#            print("k = {}, M/k = {}, ans = {}, skip".format(k, M//k, ans))
        k_ = M // k
        if((M // k_) > N - 1):
            ans = max(ans, k_)
#            print("k = {}, M/k = {}, ans = {}".format(k_, M//k_, ans))
#        else:
#            print("k = {}, M/k = {}, ans = {}, skip".format(k_, M//k_, ans))
    else:
#        print("k = {}, M % k = {}, skip".format(k, M % k))
        continue

print(str(ans))


### FIXED CODE ###

N, M = map(int, input().split())

ans = 1
k = 1
while(k * k <= M):
    if(0 == M % k):
        if(M >= N * k):
            ans = max(ans, k)
        k_ = M // k
        if(M >= N * k_):
            ans = max(ans, k_)
    k += 1

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

S = input()
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
eo = 1
for q in query:
  if q == 1:
    eo = eo*(-1)
  else:
    eoq = eo*q[0]
    if eoq == 1 or eoq == -2:
      S = q[1] + S
    else:
      S = S + q[1]
if eo == -1:
  S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = input()
ds = deque(S)
Q = int(input())
query = []
for i in range(Q):
  tq = list(input().split())
  if (len(tq) == 1):
    query.append(1)
  if (len(tq) == 3):
    query.append([int(tq[1]),tq[2]])
eo = 1
for q in query:
  if q == 1:
    eo = eo*(-1)
  else:
    eoq = eo*q[0]
    if eoq == 1 or eoq == -2:
      ds.extendleft(q[1])
    else:
      ds.extend(q[1])
jds = "".join(ds)
if eo == -1:
  jds = jds[::-1]
print(jds)
### BUGGY CODE ###

N, A, B = map(int, input().split())
ABalls = ""
BBalls = ""
for a in range(A):
  ABalls += "B" 
for b in range(B):
  BBalls += "R"

Balls = ABalls + BBalls
AB = A + B
NumBBalls = 0

NumBBalls = N//AB * A

M = N%AB

for m in range(M):
  if Balls[m] == "B":
    NumBBalls += 1
  else:
    break

print(NumBBalls)

### FIXED CODE ###

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

AB = A + B
NumABalls = 0

NumABalls = N//AB * A
M = N%AB

if A - M >= 0:
  NumABalls += M
else:
  NumABalls += A

print(NumABalls)
### BUGGY CODE ###

import math
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
ans = 0
al = [ls[-1],ls[0]]
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(n):
    di = ls[:i]
    di.append(ls[i]//2)
    di.sort()
    ind = di.index(ls[i]//2)
    il,ir = ind,ind
    if ind > 0:
        il -= 1
    else:
        il = -1
    if ind < len(di)-1:
        ir += 1
    else:
        ir = -1
    c = 0
    if ir > 0:
        if il > 0:
            mx = max(combinations_count(ls[i],di[ir]),combinations_count(ls[i],di[il]))
            c = 1
        else:
            mx = combinations_count(ls[i],di[ir])
            c = 3
    else:
        if il > 0:
            mx = combinations_count(ls[i],di[il])
            c = 2
        else:
            mx = 0
    if mx > ans:
        ans = mx
    if ans == mx:
        if c == 1:
            if combinations_count(ls[i],di[ir]) >= combinations_count(ls[i],di[il]):
                al = [ls[i],di[ir]]
            else:
                al = [ls[i],di[il]]
        elif c == 2:
            al = [ls[i],di[il]]
        elif c == 3:
            al = [ls[i],di[ir]]
print(*al)

### FIXED CODE ###

import math
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
di = ls[:]
di.append(ls[-1]//2)
di.sort()
ind = di.index(ls[-1]//2)
il,ir = -1,-1
if ind > 0:
    il = ind - 1 
if ind < n-1:
    ir = ind + 1
if il < 0 or ir < 0:
    now = max(ir,il)
else:
    if ls[-1] % 2 == 0:
        if abs(ls[-1]//2 - di[ir]) < abs(ls[-1]//2 - di[il]):
            now = di[ir]
        else:
            now = di[il]
    else:
        if min(abs(ls[-1]//2 - di[ir]),abs(ls[-1]//2 + 1 - di[ir])) < min(abs(ls[-1]//2 - di[il]),abs(ls[-1]//2 + 1 - di[il])):
            now = di[ir]
        else:
            now = di[il]
print(ls[-1],now)
### BUGGY CODE ###

from collections import deque
import sys

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

def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while len(deq):
    y,x = deq.popleft()
    for dy,dx in move_a:
      ny,nx = y+dy,x+dx
      if 0<=ny<H and 0<=nx<W and S[ny][nx] and dist[ny][nx]>dist[y][x]:
        dist[ny][nx] = dist[y][x]
        deq.appendleft((ny,nx))
    for dy,dx in move_b:
      ny,nx = y+dy,x+dx
      if not (0<=ny<H and 0<=nx<W):
        continue
      if not S[ny][nx]:
        continue
      if dist[ny][nx] <= dist[y][x]+1:
        continue
      flag = False
      for ddy,ddx in move_a:
        nny,nnx = ny+ddy,nx+ddx
        if 0<=nny<H and 0<=nnx<W and S[nny][nnx] and dist[nny][nnx]==dist[y][x]:
          flag = True
          break
      if flag:
        continue
      dist[ny][nx] = dist[y][x] + 1
      deq.append((ny,nx))
    
  ans = dist[D_h][D_w]
  print(ans if ans!=INF else -1)


H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = [[c=='.' for c in readline()] for _ in range(H)]

solve(H,W,C_h,C_w,D_h,D_w,S)


### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-math.sqrt(n)//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = inp()
a = inpl()
g = 1
res = 0
d = defaultdict(int)
for i in a:
    arr = factorization(i)
    r = 1
    # print(arr)
    # for l in arr:
    #     r *= l[0] * l[1]
    # print(r)
    for l in arr:
        if d[l[0]] < l[1]:
            d[l[0]] = l[1]
# print(d)
for key in list(d):
    g *= key ** d[key]
for i in range(n):
    res += g//a[i]
    res %= mod
print(res)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in a:
    res += g//i
print(res%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
        print((ans+MOD)%MOD)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
        ans = (ans+MOD)%MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans = (ans+MOD)%MOD
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
            ans = (ans+MOD)%MOD
        print((ans+MOD)%MOD)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
            ans = (ans+MOD)%MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans = (ans+MOD)%MOD
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().split()))
array.sort()
ans = 0
for i in range(N):
    for k in range(i+1,N):
        for j in range(1,N):
            if (array[i] < array[k] + array[-j]) and (array[-j] < array[i] + array[k]) and (array[k] < array[i] + array[-j]):
                ans += N-j-k
                break
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(N):
    for k in range(i+1,N):
        tmp = bisect.bisect_left(a,a[i]+a[k])
        ans += tmp - k - 1
print(ans)
### BUGGY CODE ###

n=int(input())
s=list(input())
x=[]
y=[]
count=0

for i in range(n-2):
    y=[]
    if x.count(s[i])!=0:
        if len(x)==10:
            break
        continue
    
    else:
        x.append(s[i])
        for j in range(i+1,n-1):
                for k in range(j+1,n):
                    v=s[j]+s[k]
                    if y.count(v)!=0:
                        continue
                    else:
                        y.append(v)
                        count+=1
                        

                
                        
                
        
    
print(count)



### FIXED CODE ###

n=int(input())
s=list(input())
count=0

for i in range(1000):
    if len(str(i))==1:
        i=str(0)+str(0)+str(i)
    elif len(str(i))==2:
        i=str(0)+str(i)
    else:
        i=str(i)
    x=0
    for j in range(n):
        if s[j]==i[x]:
            x+=1
            if x==3:
                count+=1
                break
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(i) for i in input().split()]

dp = [0 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    dp[i] = min([dp[j] + abs(H[j] - H[i]) for j in range(max(0, i-K), i)])
print(dp[N-1])

### FIXED CODE ###

def main():    
    N, K = map(int, input().split())
    H = [int(i) for i in input().split()]

    dp = [0 for _ in range(N)]
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min([dp[j] + abs(H[j] - H[i]) for j in range(max(0, i-K), i)])
    print(dp[N-1])

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

n = int(input())
h = list(map(int, input().split()))
max = 0
for i in range(n-1):
    tmp = 0
    j = i
    while h[j]>=h[j+1]:
        j += 1
        tmp += 1
        if j == n-1:
            break
    if tmp>max:
        max = tmp
print(max)



### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
max = 0
tmp = 0
for i in range(n-1):
    if h[i] >= h [i+1]:
        tmp += 1
    else:
        tmp = 0
    if tmp > max:
        max = tmp
print(max)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = {i: 0 for i in range(13)}
  if s[-1] == '?':
    for i in range(10):
      sd[i] = 1
  else:
    sd[int(s[-1])] = 1
  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    tmpd = {r: 0 for r in range(13)}
    if _s != '?':
      rem = int(_s) * pow(10, i) % 13
      for j in range(13):
        tmpd[(j+rem)%13] = sd[j]
    else:
      for k in range(10):
        rem = k * pow(10, i) % 13
        for j in range(13):
          tmpd[(j+rem)%13] += sd[j]
          tmpd[(j+rem)%13] %= MOD
    sd = tmpd
  print(sd[5])


if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [[0 for _ in range(13)] for _ in range(len(s))]
  if s[-1] == '?':
    for i in range(10):
      sd[0][i] = 1
  else:
    sd[0][int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    if _s != '?':
      rem = int(_s) * pow(10, i, 13) % 13
      for j in range(13):
        sd[i][(j+rem)%13] = sd[i-1][j]
    else:
      for k in range(10):
        rem = k * pow(10, i, 13) % 13
        for j in range(13):
          sd[i][(j+rem)%13] += sd[i-1][j]
          sd[i][(j+rem)%13] %= MOD
  print(sd[len(s)-1][5])


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

def remove_01_10(S):
	S = S.replace('10', '')
	S = S.replace('01', '')
	return S	

S = input()
N = len(S)
while True:
	if '01' in S or '10' in S:
		S = remove_01_10(S)
	else:
		print(N - len(S))
		exit()

### FIXED CODE ###

S = list(input())
N = len(S)
num0 = 0
for i in range(N):
	if S[i] == '0':
		num0 = num0 + 1

num1 = 0
for i in range(N):
	if S[i] == '1':
		num1 = num1 + 1
print(N - abs(num0 - num1))
### BUGGY CODE ###

from math import factorial

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
P = factorial(n) // factorial(n-r) // factorial(r) % MOD

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P
        ans %= MOD

print(ans)


### FIXED CODE ###

from math import factorial

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
#P = factorial(n) // factorial(n-r) // factorial(r) % MOD
P = factorial(n) * pow(factorial(n-r) % MOD, MOD - 2, MOD) * pow(factorial(r) % MOD, MOD - 2, MOD)

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt

ans = (ans * P) % MOD
print(ans)
### BUGGY CODE ###

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

D=5000000000000000

tmp=0
for s in S:
  t=1
  for _ in range(D):
    t=t*int(s)
    if tmp+t>=K:
      print(s)
      break
  else:
    tmp+=t
    continue
  break

### FIXED CODE ###

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

D=5000000000000000

tmp=0
for s in S:
  if s=='1':
    tmp+=1
    if tmp>=K:
      print(s)
      break
    continue
    
  t=1
  for _ in range(D):
    t=t*int(s)
    if tmp+t>=K:
      print(s)
      break
  else:
    tmp+=t
    continue
  break