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

K = int(input())

i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    i += 1
    if ai == 0:
        break
print(i)

### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    i += 1
    if ai == 0:
        break
print(i)
### BUGGY CODE ###

#Partition
N,M = map(int,input().split())
n = 1
for i in range(M):
    if M % (i+1) == 0 and N*(i+1) <= M:
        n = i+1
print(n)

### FIXED CODE ###

#Partition
import math
N,M = map(int,input().split())
n = 1
rootM = int(math.sqrt(M))+1
for i in range(rootM):
    if M % (i+1) == 0 and N*(i+1) <= M:
        if N*(M/(i+1)) <= M and n <= (M/(i+1)):
            n = M/(i+1)
        elif n <= i+1:
            n = i+1
        else:
            continue
print(int(n))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    # まず、その瞬間のスコアを求める
    # L+R,R-L+H
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    for n in range(H+H+1):
        # R-L+H=n
        if n <= H:
            R0,L0 = 1,H-n+1
            R1,L1 = n,H
        else:
            L0,R0 = 1,n-H+1
            L1,R1 = H+H-n,H
        dp_1[n][L0+R0:L1+R1+2:2] = (col1[L0:L1+1] == col2[R0:R1+1])
    np.cumsum(dp_1,out=dp_1,axis=1)
#    for L in range(H+1):
#        for R in range(H+1):
#            x = col1[:L+1]
#            y = col2[:R+1]
#            n = min(L,R)
#            xr = x[::-1][:n+1]
#            yr = y[::-1][:n+1]
#            print(L,R,(xr==yr).sum(),dp_1[R-L+H,L+R])"""
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)

    def dequeue(self):
        return self.data.pop(0)

    def is_Empty(self):
        if len(self.data) == 0:
            return True
        else:
            return False


H, W = map(int, input().split())  # H行W列

gridgraph = [list(input()) for _ in range(H)]  # H行W列のグリッドグラフ
visited = [[False]*W for _ in range(H)]
cnt = [[0]*W for _ in range(H)]

queue = Queue()

for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == '#':
            queue.enqueue([i, j])  # 初期の時点で黒色のマスをqueueに追加する
            visited[i][j] = True

while not queue.is_Empty():
    cy, cx = queue.dequeue()

    for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if cy+dy >= H or cy+dy < 0 or cx+dx >= W or cx+dx < 0:
            continue
        if visited[cy+dy][cx+dx]:  # すでに訪問済みであればcontinue
            continue
        visited[cy+dy][cx+dx] = True  # 訪問済みにする
        cnt[cy+dy][cx+dx] = cnt[cy][cx] + 1
        queue.enqueue([cy+dy, cx+dx])


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, cnt[i][j])

print(ans)


### FIXED CODE ###

import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0

while len(q):
    cy, cx = q.popleft()

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)
### BUGGY CODE ###

N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = sorted(_x)
dis = [0 for z in range(N-1)]
count = 0
if N == 1:
    print(abs(x[0]-start))
else:
    for i in range(N-1):
        dis[i] = x[i+1] - x[i]
    D = min(dis)
    ans = 1
    for d in range(1,D+1):
        cite = start
        while True:
            if cite > x[N-1]:
                break
            if cite in x:
                count += 1
            cite += d
        cite = start
        while True:
            if cite < x[0]:
                break
            if cite in x:
                count += 1
            cite -= d
        if count == N:
            ans = d
        count = 0
    print(ans)


### FIXED CODE ###

import math
N,start = [int(x) for x in input().split()]
_x = [int(y) for y in input().split()]
x = [0 for y in range(N)]
for i in range(N):
    x[i] = abs(_x[i] - start)
g = x[0]
for i in range(N):
    g = math.gcd(g,x[i])
print(g)
ans = 1
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
r=[i for i in range(n)]
for i1 in r:
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in r:
            i2_sub=n-i2
            y_sub1=y[i2][0]
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in r:
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    adj[L].append((R, D))
    adj[R].append((L, -D))
seen = [0] * (N + 1)


def dfs(adj, seen, start):
    inf = 10 ** 10
    que = deque()
    que.append(start)
    x = [inf] * (N + 1)
    x[start] = 0
    while que:
        v = que.pop()
        seen[v] = 1
        for u, d in adj[v]:
            if seen[u] == 0:
                que.append(u)
                if x[u] == inf:
                    x[u] = x[v] + d
                else:
                    if x[u] != x[v] + d:
                        return 0, seen
    return 1, seen


for i in range(1, N + 1):
    if seen[i] == 0:
        ok, seen = dfs(adj, seen, i)
        if not ok:
            print('No')
            sys.exit()

print('Yes')


### FIXED CODE ###

from collections import deque
import sys
import time
input = sys.stdin.readline


def main():
    t1 = time.time()
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, seen, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()
            t2 = time.time()
            if t2 - t1 > 1.8:
                print('Yes')
                sys.exit()
        return seen

    for i in range(1, N + 1):
        if seen[i] == 0:
            seen = dfs(adj, seen, i)

    print('Yes')


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

from collections import deque


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = deque()

def bfs():
    max_cnt = 0
    while q:
        u = q.popleft()
        cnt = 1
        visited[u] = True
        for v in edges[u]:
            if visited[v]:
                continue
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.append(v)
        max_cnt = max(max_cnt, cnt)
    return max_cnt


AB = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append((a, b))
    edges[a].append(b)
    edges[b].append(a)

q.append(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

n = int(input())
A = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    A[a].append([b, i])

ans = [0] * (n - 1)


def col(now, color):
    c = 1
    for (b, j) in A[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b, c)
        c += 1


col(0, 0)
print(max(ans))
for a in ans:
    print(a)
### BUGGY CODE ###

S=input()
N=len(S)
L=N
for i in range(L):
  S=S.replace("01","")
  S=S.replace("10","")
  #print(S)
  if L==len(S):
    break
  L=len(S)
  
#print(S)
print(N-L)

### FIXED CODE ###

S=input()
N=len(S)
ones=S.count("1")
zeros=S.count("0")
print(N-abs(ones-zeros))
### BUGGY CODE ###

n = [list(map(int, input().split())) for i in range(2)]

N = n[0].pop(0)
A = n[1]

for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

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

mem = [0]*(n)
for i in range(n-1):
    mem[a[i]-1] += 1

for i in mem:
    print(i)
### BUGGY CODE ###

N = int(input())
X = [[] for _ in range(N)]
ans = 0
for i in range(N):
    X[i] = list(map(int, input().split()))
    for j in range(i):
        ans = max(ans,(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1])))

# for i in range(1, N):
#     for j in range(i):
#         ans = max(ans,(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1])))
print(ans)

### FIXED CODE ###

N = int(input())
X = [[] for _ in range(N)]
z = [0 for _ in range(N)]
w = [0 for _ in range(N)]
for i in range(N):
    X[i] = list(map(int, input().split()))
    z[i] = X[i][0] +X[i][1]
    w[i] = X[i][0] -X[i][1]

ans = max(max(z)-min(z), max(w)-min(w))
print(ans)
### BUGGY CODE ###

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

b = [0] * (n - k + 1)
b[0]+=a[0]
for i in range(k-1):
    b[0] *= a[i + 1]

for j in range(len(b) - 1):
    b[j + 1] = (b[j + 1] + b[j]) // a[j] * a[j + k]

for l in range(len(b)-1):
    if b[l] < b[l + 1]:
        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("No")
    else:
        print("Yes")
### BUGGY CODE ###

import numpy

N, M = map(int, input().split())
a = numpy.array(list(map(int, input().split())))

for i in range(M):
    # j = max(enumerate(a), key=lambda x: x[1])[0]
    j = a.argmax()
    a[j] //= 2
print(sum(a))

### FIXED CODE ###

import heapq

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

q = []
for i in range(N):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))
### BUGGY CODE ###

N,Y = map(int,input().split())
X = Y // 1000
check = 0
for a in range(X // 10 + 1):
    for b in range(X // 5 + 1):
        c = N - a - b
        Z = 10 * a + 5 * b + c
        if c >= 0 and X == Z:
            check = 1
            break
    if check == 1:
        break
if check == 0:
    print(-1,-1,-1)
else:
    print(a,b,c)

### FIXED CODE ###

N,Y = map(int,input().split())
X = Y // 1000
check = 0
for a in range(X // 10 + 1):
    for b in range(X // 5 + 1):
        c = N - a - b
        Z = 10 * a + 5 * b + c
        if c >= 0 and X == Z:
            check = 1
            break
    if check == 1:
        break
if check == 0:
    print(-1,-1,-1)
else:
    print(a,b,c)
### BUGGY CODE ###

A,B=map(int,input().split())
arr=set()
X=min(A,B)
for i in range(1,(X+1)//2+1):
    if A%i==0 and B%i==0:
        arr.add(i)
s=min(arr);e=max(arr)
def make_divisors(n,s,e):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if i!=s and i!=e:
            if n % i == 0 :
                divisors.add(i)
                if i != n // i:
                    divisors.add(n//i)
    return divisors
cnt=0

for j in arr:
    if len(make_divisors(j,0,0) & arr)<3:
        cnt+=1
print(cnt)

### FIXED CODE ###

A,B=map(int,input().split())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

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

    return arr

print(len(set(factorization(A)) & set(factorization(B)))+1)
### BUGGY CODE ###

def lower_bound(a, x):
  l = -1
  r = len(a)
  while r - l > 1:
    h = (l + r) // 2
    if a[h] < x:
      r = h
    else:
      l = h
  return l
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
res = 0
for i in range(n):
  for j in range(i+1, n):
    lb = lower_bound(l[j+1:], l[i]-l[j]+1)
    res += lb + 1
print(res)

### FIXED CODE ###

def lower_bound(a, x):
  l = -1
  r = len(a)
  while r - l > 1:
    h = (l + r) // 2
    if a[h] < x:
      r = h
    else:
      l = h
  return l
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
res = 0
for i in range(n):
  for j in range(i+1, n):
    lb = lower_bound(l[j+1:], l[i]-l[j]+1)
    res += lb + 1
print(res)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

dic = {}
for ai in a:
    if ai not in dic:
        dic[ai] = 0
    dic[ai] += 1

ans = 0

for ai in a:
    cnt = 0
    f = 1
    for d in make_divisors(ai):
        if d in dic:
            cnt += dic[d]
        if d == ai:
            cnt -= 1
        if cnt > 0:
            f = 0
            break
    ans += f

print(ans)
    

            




### FIXED CODE ###

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print(sum(memo))
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = []
for i in range(Q):
  A.append(int(input()))
for i in range(1,N+1):
  if K > Q - A.count(i):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [K-Q for i in range(N)]
for i in range(Q):
  A[int(input())-1] += 1
for i in range(N):
  print("Yes" if A[i]>0 else "No")
### BUGGY CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))
    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    while len(q):
        worp_count, x, y = q.popleft()
        S[x][y] = '/'

        if (x, y) == D:
            return worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                if abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, x + i, y + j))
                else:
                    q.append((worp_count + 1, x + i, y + j))

    return -1


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

s = input()
K = int(input())
l = [chr(i) for i in range(97, 97+26)]
selected = []
for i in l:
  if i in s:
    index = []
    for ind, j in enumerate(s):
      if i == j:
        index.append(ind)
    for j in index:
      for k in range(len(s)):
        if j+k == len(s):
          break
        selected.append(s[j:j+k+1])
    selected=list(set(selected))
    selected.sort()
    if len(selected)>=K:
      print(selected[K-1])
      break


### FIXED CODE ###

s = input()
K = int(input())
l = [chr(i) for i in range(97, 97+26)]
selected = []
for i in l:
  if i in s:
    index = []
    for ind, j in enumerate(s):
      if i == j:
        index.append(ind)
    for j in index:
      temp = []
      for k in range(5):
        if j+k == len(s) or len(temp)>=K:
          break
        selected.append(s[j:j+k+1])
    selected=list(set(selected))
    selected.sort()
    if len(selected)>=K:
      print(selected[K-1])
      break
### BUGGY CODE ###

N, A, B = map(int,input().split())
h = [0 for i in range(N)]
for i in range(N):
	h[i] = int(input())
h = sorted(h)
import math
# N, A, B = 4, 5, 3
# h = [8,7,4,2]
# h = sorted(h,reverse=True)

def enough(T):
	tmp = 0
	for i in range(N):
		if h[i] >= B*T:
			tmp += math.ceil((h[i]-B*T)/(A-B))
	return True if tmp <= T else False

MAX = 10**9
MIN = 0
while MAX > MIN:
	if enough(MAX) == True and enough(MIN) == False and MAX - MIN == 1:
		break
	MID = (MAX+MIN)//2
	if enough(MID) == True:
		if enough(MID-1) == True:
			MAX = MID-1
		else:
			MAX = MID
	else:
		if enough(MID+1) == False:
			MIN = MID+1
		else:
			MIN = MID
print(MAX)



### FIXED CODE ###

N, A, B = map(int,input().split())
h = [0 for i in range(N)]
for i in range(N):
	h[i] = int(input())
h = sorted(h)
import math
# N, A, B = 4, 5, 3
# h = [8,7,4,2]
# h = sorted(h,reverse=True)

def enough(T):
	tmp = 0
	for i in range(N):
		if h[i] >= B*T:
			tmp += math.ceil((h[i]-B*T)/(A-B))
	return True if tmp <= T else False

MAX = 10**9
MIN = 0
MID = (MAX+MIN)//2
while MAX > MIN+1:
	if enough(MID) == True:
		MAX = MID
	else:
		MIN = MID
	MID = (MAX+MIN)//2
print(MAX)
### BUGGY CODE ###

def main():
  d=[1]+[0]*12
  for c in input():
    d=[sum(d[(j-k)*9%13]for j in(range(10)if c>'9'else[int(c)]))%(10**9+7)for k in range(13)]
  print(d[5])
main()

### FIXED CODE ###

d=[1]+[0]*12
for i,c in enumerate(input()):
 p=[0]*13
 for j in range(13):
  for k in range(10):p[(j*10+k)%13]+=d[j]*(c>'9'or k==int(c))
 d=[t%(10**9+7)for t in p]
print(d[5])
### BUGGY CODE ###

H,W=map(int,input().split())

board=[list(input()) for _ in range(H)]
stack=list()
dh=[1,0,-1,0]
dw=[0,-1,0,1]


def boardcheck():
    nstack=list()
    global stack
    for dot in stack:
        for i in range(4):
            th=dot[0]+dh[i]
            tw=dot[1]+dw[i]
            if 0<=th<H and 0<=tw<W and board[th][tw]=='.':
                board[th][tw]='#'
                nstack.append([th,tw])
    return nstack


for i in range(H):
    for j in range(W):
        if board[i][j]=='#':
            stack.append([i,j])
count=0
while True:
    stack=boardcheck()
    if len(stack)==0:
        break
    count+=1

print(count)


### FIXED CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

q=[]
for h in range(1,H+1):
    for w in range(1,W+1):
        if board[h][w]:
            q.append((h,w))

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append((h+1,w))
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append((h-1,w))
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append((h,w+1))
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append((h,w-1))

    q=nq
    cnt+=1

print(cnt-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Sum of 4 Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096

"""
import sys
from sys import stdin
from collections import defaultdict
input = stdin.readline


def main(args):
    lut = defaultdict(list)
    for a in range(1001):
        for b in range(1001):
            lut[a+b].append((a, b))

    for line in sys.stdin:
        n = int(line)
        ans = 0
        for i in range(n+1):
            for a, b in lut[i]:
                for c, d in lut[n-i]:
                    ans += 1
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Sum of 4 Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096

"""
import sys
from sys import stdin
from collections import defaultdict
input = stdin.readline


def main(args):
    lut = defaultdict(int)
    for a in range(1001):
        for b in range(1001):
            lut[a+b] += 1

    for line in sys.stdin:
        n = int(line)
        ans = 0
        for i in range(n+1):
            ans += lut[i] * lut[n-i]
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])