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

from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
field = [list(input()) for i in range(H)]

dist_from_nearest_black = [[10 ** 9] * W for i in range(H)]
seen = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(h, w):
    if field[h][w] != "#":
        return

    queue = deque([])
    queue.append([h, w])
    dist_from_nearest_black[h][w] = 0

    while len(queue) != 0:

        h, w = queue.popleft()

        if seen[h][w] == 1:
            continue

        seen[h][w] = 1

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = min(
                    dist_from_nearest_black[h][w] + 1, dist_from_nearest_black[next_h][next_w])
                queue.append([next_h, next_w])


for h in range(H):
    for w in range(W):
        seen = [[0] * W for i in range(H)]
        bfs(h, w)

ans = 0

for d in dist_from_nearest_black:
    # print(d)
    ans = max(ans, max(d))

print(ans)


### FIXED CODE ###

from collections import deque
import sys
# from time import time

# start = time()

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

# print(time() - start)

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "#"
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)
# print(time() - start)
### BUGGY CODE ###

from math import ceil

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

def calcn(r, x):
    n = 1
    while n * r < x:
        n += 1
    return n

for i in range(1, n):
    rt, ra = data[i][0], data[i][1]
    na = int(calcn(ra, a))
    nt = int(calcn(rt, t))
    n = max(na, nt)
    t = n * rt
    a = n * ra

print(t + a)


### FIXED CODE ###

from math import ceil

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

def calcn(r, x):
    n = int(x / r)
    while n * r > x:
        n -= 1
    while n * r < x:
        n += 1
    return n

for i in range(1, n):
    rt, ra = data[i][0], data[i][1]
    na = int(calcn(ra, a))
    nt = int(calcn(rt, t))
    n = max(na, nt)
    t = n * rt
    a = n * ra

print(t + a)
### BUGGY CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
s=sorted(l)
m=max(l)
nums=[i for i in range(n)]
for num in nums:
  if(l[num]!=m or l.count(m)!=1):
    print(m)
  else:
    print(s[-2])

### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
s=sorted(l)
p=s[-1]
q=s[-2]
for i in range(n):
  if l[i]==p:
    print(q)
  else:
    print(p)
### BUGGY CODE ###

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

ans = 0

for i in range(1 , n+1):
    ans_p = (a*i//b) - a * (i//b)
    if ans_p >= ans:
        ans = ans_p

print(ans)

### FIXED CODE ###

import math

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

if n < b:
    print(math.floor(a*n/b))
else:
    print(math.floor(a*(b-1)/b))
### BUGGY CODE ###

N = int(input())
dicts = {}
for i in range(N):
    s = "".join(sorted(input()))
    dicts[s] = dicts[s] + 1 if s in list(dicts.keys()) else 1

num = 0
for k, v in dicts.items():
  num += v * (v-1) // 2
print(num)

### FIXED CODE ###

N = int(input())
dicts = {}
for i in range(N):
    s = "".join(sorted(input()))
    dicts[s] = dicts[s] + 1 if s in dicts.keys() else 1

num = 0
for k, v in dicts.items():
  num += v * (v-1) // 2
print(num)
### BUGGY CODE ###

Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)

for _ in range(Q):
    cnt = 0
    l, r = map(int, input().split())

    for x in range(l, r + 1):
        if prime[x] and prime[(x + 1) // 2]:
            cnt += 1

    print(cnt)




### FIXED CODE ###

Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)
primeSum = [0] * (MAX + 1)
for x in range(1, MAX + 1):
    primeSum[x] = primeSum[x - 1]
    if prime[x] and prime[(x + 1) // 2]:
        primeSum[x] += 1
        

for _ in range(Q):
    cnt = 0
    l, r = map(int, input().split())

    print(primeSum[r] - primeSum[l - 1])
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

n, m, ss, *uvabcd = map(int, sys.stdin.buffer.read().split())
uuu = uvabcd[0:4 * m:4]
vvv = uvabcd[1:4 * m:4]
aaa = uvabcd[2:4 * m:4]
bbb = uvabcd[3:4 * m:4]
ccc = uvabcd[4 * m + 0::2]
ddd = uvabcd[4 * m + 1::2]
links = [set() for _ in range(n)]

for u, v, a, b in zip(uuu, vvv, aaa, bbb):
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))

INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u))

    ts = s
    tt = t
    while ts < 2500:
        ts += ccc[v]
        tt += ddd[v]
        nk = (tt, ts, v)
        if nk not in visited:
            heappush(q, (tt, ts, v))

print('\n'.join(map(str, ans[1:])))


### FIXED CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b.sort()

c = []
if len(b) != 1:
  for i in range(len(b) - 1):
    c.append(b[i+1] - b[i])

if len(b) == 1:
  print(0)
  
    
else:  
  for j in range(min(a[0] - 1,a[1])):
    for k in range(len(c)):
      if c[k] == max(c):
        c[k] = 0
        break
  print(sum(c))



### FIXED CODE ###

# coding: utf-8
# Your code here!
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b.sort()

c = []
if len(b) != 1:
  for i in range(len(b) - 1):
    c.append(b[i+1] - b[i])

if len(b) == 1:
  print(0)
  
    
else:  
  c.sort()
  for j in range(min(a[0] - 1,a[1])):
    c[len(c)- 1 - j] = 0
  print(sum(c))
### BUGGY CODE ###

# ARC076C - Reconciled?
def factorial(x):
    ret = 1
    for i in range(1, x + 1):
        ret *= i
    return ret


def main():
    n, m = list(map(int, input().rstrip().split()))
    MOD = 10 ** 9 + 7
    dif = abs(n - m)
    if dif > 1:  # must be ...DDM...
        print(0)
    else:
        if dif == 0:  # start with either D or M (DM..., MD...)
            ans = (factorial(n) * factorial(m) * 2) % MOD
        else:  # sandwich (DMD or MDM)
            ans = (factorial(n) * factorial(m)) % MOD
        print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ARC076C - Reconciled?
from math import factorial


def main():
    n, m = list(map(int, input().rstrip().split()))
    MOD = 10 ** 9 + 7
    dif = abs(n - m)
    if abs(n - m) not in (0, 1):
        print(0)
    else:
        if dif == 0:
            ans = (factorial(n) * factorial(m) * 2) % MOD
        else:
            ans = (factorial(n) * factorial(m)) % MOD
        print(ans)


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

#A,B,C,D=map(int,input().split(" "))

mod=2019
a=input()

N=len(a)
t=[]
ans=0

for i in range(N):
  for j in range(i+1,N+1):
    u=int(a[i:j])
    #print(u)
    if (u % mod)==0:
      ans+=1
      #print(i+1,j)
      i=j

print(ans)


### FIXED CODE ###

mod=2019
a=input()

N=len(a)
t=[0]*mod
t[0]=1

w=1
u=0

for i in range(N):
  u=int(a[N-1-i]) * w + u
  v=u % mod
  t[v] += 1
  w *=10
  w %= mod

ans=0
for i in t:
  ans += (i-1)*i//2

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

import bisect

# 別解 :
N = int(input())
L = list(map(int, input().split()))

L.sort()
cnt = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        idx = bisect.bisect_left(L, L[i] + L[j], lo=j + 1)
        cnt += max(0, idx - (j + 1))


print(cnt)

### FIXED CODE ###

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


L.sort(reverse=True)
dic = {}
cnt = 0

for i in range(1, N - 1):
    p = L[i]
    for j in range(i + 1, N):
        s = p + L[j]

        if s not in dic:
            dic[s] = 1
        else:
            dic[s] += 1

for i in range(N - 2):
    p = L[i]

    if i > 0:
        for x in range(i + 1, N):
            dic[p + L[x]] -= 1

    for key, value in dic.items():
        if key > p:
            cnt += value

print(cnt)
### BUGGY CODE ###

def convert(L):
    H=len(L)
    W=len(L[0])
    dp = [[0 for _ in range(W)] for _ in range(H)]
    #dp = np.zeros((L.shape[0],L.shape[1]), dtype='int')
    for i in range(H):
        l=L[i]
        for j in range(W):
            if l[j]:
                if j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i][j-1] + 1
            else:
                dp[i][j] = 0
    return dp
H,W=map(int,input().split())
L= [[] for _ in range(H)]
for i in range(H):
    L[i]=list(map(lambda x: False if x=="#" else True,list(input()) ))

def rr(matrix):
    return list(map(list, zip(*matrix)))[::-1]

def mir(L):
    return [list(l[::-1]) for l in L]
def flip(L):
    H=len(L)
    W=len(L[0])
    return [[L[i][j] for i in range(H)] for j in range(W)]
A=rr(L)
B=rr(rr(L))
C=rr(rr(rr(L)))
LL=convert(L)
AA=rr(rr(rr(convert(A))))
BB=rr(rr(convert(B)))
CC=rr(convert(C))
#K=flip(L)
ans = -1
M=[[0for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        t = LL[i][j]+AA[i][j]+BB[i][j]+CC[i][j]-3 
        ans = max(ans,t)
        M[i][j] = t
print(ans)

### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1

# x軸正方向の集計
def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x

# y軸
def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)
# x軸
answer += F()
# 逆順
map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]

# y軸
answer += G()
# 逆順
map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)
### BUGGY CODE ###

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

for i in range(q):
  tmp = a[i]
  for j in range(len(K)):
    K[j] -= 1
  K[int(tmp)-1] = K[int(tmp)-1]+1
  
for k in range(len(K)):
  if K[k] > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [input() for i in range(q)]
K = [k]*n
limit = 0

for i in range(q):
  tmp = a[i]
  K[int(tmp)-1] = K[int(tmp)-1]+1
  limit += 1
  
for k in range(len(K)):
  if K[k] > limit:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
c=int(input())
d=list(map(int,input().split()))
e=set(d)

for item in e:
  if d.count(item)>b.count(item):
    print("NO")
    exit()
    
print("YES")


### FIXED CODE ###

import collections

a=int(input())
b=collections.Counter(list(map(int,input().split())))
c=int(input())
d=collections.Counter(list(map(int,input().split())))
e=set(d)

for item in e:
  if d[item]>b[item]:
    print("NO")
    exit()
    
print("YES")
### BUGGY CODE ###

import heapq
 
n= int(input())
s=[input() for i in range(n)]
 
ss = list(set(s))
 
if(len(s)==len(ss)):
    s.sort()
    for i in s:
        print(i)
 
else:
    li = []
    heapq.heapify(li)
    for i in ss:
        ans = s.count(i)
        heapq.heappush(li,(-ans,i))
    
    for i in range(len(ss)):
        amount,st = heapq.heappop(li)
        if(i==0):
            print(st)
            ri=amount
            continue
        
        if(ri==amount):
            print(st)
        else:
            break

### FIXED CODE ###

import collections

n= int(input())
s=[input() for i in range(n)]

li = collections.Counter(s)
ma= max(li.values())

ans= [i for i,j in li.items() if(j==ma)]
print("\n".join(sorted(ans)))
### BUGGY CODE ###

def main():
    from bisect import bisect_left as bs
    n, m, *abc = map(int, open(0).read().split())
    a = sorted(abc[:n])
    *bc, = zip(*[iter(abc[n:])] * 2)
    bc.sort(key=lambda x: x[1], reverse=True)

    ans = 0
    for b, c in bc:
        i = bs(a, c)
        if i == 0:
            break
        j = min(i, b)
        ans += j * c
        a = a[j:]

    print(ans + sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

import heapq

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

C=[0 for i in range(N+1)]
L=[[]for i in range(N+1)]
A=[10**15 for i in range(N+1)]
B=[]

for i in range(M):
    l,r,d=map(int,input().split())
    B.append([l,r,d])
    C[r]=1
    L[l].append([l,r,d])
for i in range(N+1):
    if C[i]==0:
        A[i]=0
for i in range(1,N+1):
    if A[i]==0:
        if len(L[i])>0:
            Q=[]
            for l,r,d in L[i]:
                Q.append([A[i]+d,r,l])
            #print(Q)
            heapq.heapify(Q)
            for j in range(10**6):
                if len(Q)==0:
                    break
                else:
                    q=Q[0]
                    if A[q[1]]>=q[0]:
                        A[q[1]]=q[0]
                        for k in L[q[1]]:
                            heapq.heappush(Q,[q[0]+k[2],k[1],k[0]])
                heapq.heappop(Q)
#print(C)
#print(A)
for i in range(M):

    if A[B[i][1]]!=A[B[i][0]]+B[i][2]:
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

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

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

L=[[]for i in range(N+1)]
D=dict()
for i in range(M):
    l,r,d=map(int,input().split())
    L[l].append([r,d])
    L[r].append([l,-d])
    D[i]=(l,r,d)
    
C=["N" for i in range(N+1)]

def dfs(x):
    for i,j in L[x]:
        if C[i]=="N":
            C[i]=C[x]+j
            dfs(i)

for i in range(1,N+1):
    if C[i]=="N":
        C[i]=0
        dfs(i)
#print(C)
#print(D)
for i in range(M):
    l,r,d=D[i]
    if C[r]-C[l]!=d:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,int(N**0.5)):      
        for j in range(1,int(N**0.5)):
            for k in range(1,int(N**0.5)):
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

### FIXED CODE ###

N = int(input())
list = [0]*(N+1)
for i in range(1,100):  
    for j in range(1,100):
        a = i*i + j*j + i*j
        for k in range(1,100):
            a = i*i + j*j + k*k + i*j +j*k + i*k
            if a <= N:
                list[a] += 1
for i in range(1,N+1):
    print(list[i])
### BUGGY CODE ###

#!/usr/bin/python

import sets
import sys

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split(" ")

    while len(tokens) == 3:
        n, k, l = map(lambda x: int(x), tokens)

        roads = [i for i in xrange(n)]
        railways = [i for i in xrange(n)]

        for i in xrange(k):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if roads[y - 1] > roads[x - 1]:
                roads[y - 1] = roads[x - 1]
            else:
                roads[x - 1] = roads[y - 1]

        for i in xrange(l):
            x, y = map(
              lambda c: int(c), sys.stdin.readline().rstrip("\n").split(" "))
            if railways[y - 1] > railways[x - 1]:
                railways[y - 1] = railways[x - 1]
            else:
                railways[x - 1] = railways[y - 1]

        results = [0 for i in xrange(n)]
        for i in xrange(n):
            for j in xrange(n):
                if roads[i] == roads[j] and railways[i] == railways[j]:
                    results[i] += 1
        results = map(lambda r: str(r), results)
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split(" ")

if __name__ == "__main__":
    main(sys.argv)

### FIXED CODE ###

#!/usr/bin/python

import sets
import sys

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent, parent[x])
        return parent[x]

def union(parent, x, y):
    parent_x = find(parent, x)
    parent_y = find(parent, y)

    if parent_x != parent_y:
        parent[parent_y] = parent[parent_x]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

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

import math

beki=[]
beki.append(1)
x=int(input())
for i in range(int(math.sqrt(x))):
  p=2
  while(i**p<=x):
    beki.append(i**p)
    p+=1
print(beki)

### FIXED CODE ###

import math

beki=[]
beki.append(1)
x=int(input())
for i in range(2,x):
  p=2
  while(i**p<=x):
    beki.append(i**p)
    p+=1
print(max(beki))
### BUGGY CODE ###

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
revS = S[::-1]
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if revS[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(revS[0]) % MOD1] += 1

for i in range(1, N):
    if revS[i] == '?':
        for k in range(10):
            for j in range(MOD1):
                tmp_j = (k * 10 ** i % MOD1 + j) % MOD1
                dp[i][tmp_j] += dp[i - 1][j]
    else:
        for j in range(MOD1):
            tmp_j = (int(revS[i]) * 10 ** i % MOD1 + j) % MOD1
            dp[i][tmp_j] += dp[i - 1][j]

print(dp[-1][5] % MOD2)


### FIXED CODE ###

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
                dp[i + 1][tmp_j] %= MOD2
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]
            dp[i + 1][tmp_j] %= MOD2

print(dp[-1][5] % MOD2)