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

import sys
sys.setrecursionlimit(2500)
H, W = map(int, input().split())
S = ['#'*(W+2)]+['#' + input() + '#' for _ in range(H)]+['#'*(W+2)]

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (W+2) for _ in range(H+2)]

def process(n, x, y, dx, dy):
  ret = 0
  if S[y][x] == '#':
    ret = n
  else:
    ret = process(n+1, x+dx, y+dy, dx, dy)
  if dx > 0:
    ansX[y][x] = ret
  else:
    ansY[y][x] = ret
  return ret

final = 0
for y in range(1, H+1):
  for x in range(1, W+1):
    if S[y][x] == '#':
      continue
    if ansX[y][x] is None:
      process(0, x, y, 1, 0)
    if ansY[y][x] is None:
      process(0, x, y, 0, 1)
    a = ansX[y][x] + ansY[y][x] - 1
    final = a if a > final else final
print(final)

### FIXED CODE ###

H, W = map(int, input().split())
S = ['#'*(W+2)]+[
  '#' + input() + '#' for _ in range(H)
]+['#'*(W+2)]

ST = list(map(''.join, zip(*S)))

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (H+2) for _ in range(W+2)]

final = 0
for y in range(1, H+1):
  Sy = S[y]
  ansXy = ansX[y]
  #ansYy = ansY[y]
  for x in range(1, W+1):
    if Sy[x] == '#':
      continue
    if ansX[y][x] is None:
      t = Sy.find('#', x)
      ansXy[x:t] = [t-x] * (t-x)
    if ansY[x][y] is None:
      t = ST[x].find('#', y)
      ansY[x][y:t] = [t-y] * (t-y)
    a = ansXy[x] + ansY[x][y] - 1
    final = a if a > final else final
print(final)
### BUGGY CODE ###

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**6)
for i in range(2,10**6):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**6,i):
        is_prime[j]=False

F=[[0 for _ in range(len(primes))] for __ in range(N)]
LCM=[0 for _ in range(len(primes))]
for i in range(N):
    n=A[i]
    f=F[i]
    for j,p in enumerate(primes):
        while n%p==0:
            f[j]+=1
            n//=p
        LCM[j]=max(LCM[j],f[j])

ans=0
for i in range(N):
    tmp=1
    f=F[i]
    for j,p in enumerate(primes):
        tmp=tmp*pow(p,LCM[j]-f[j],MOD)%MOD
    ans=(ans+tmp)%MOD

print(ans)

### FIXED CODE ###

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

MOD=10**9+7
def gcd(a,b):
    while b: a,b=b,a%b
    return a
def lcm(a,b): return a*b//gcd(a,b)

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]%MOD
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

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

N = int(input())
S = input()

ans = 0
for i in range(0, N):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            for k in range(j + 1, N):
                if (S[i] != S[j] and S[i] != S[k] and S[j] != S[k]) and j - i != k - j:
                    ans += 1

print(ans)

### FIXED CODE ###

# D - RGB Triplets

N = int(input())
S = input()
cnt_R = S.count('R')
cnt_G = S.count('G')
cnt_B = S.count('B')
total = cnt_R * cnt_G * cnt_B

expt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if k < N and (S[i] != S[j] and S[j] != S[k] and S[i] != S[k]):
            expt += 1

print(total - expt)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=0,z+1,0,~z;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PF[h, w] += 1

frequency_h_list = Counter(PH).most_common()
frequency_w_list = Counter(PW).most_common()
most_common_h_cnt = frequency_h_list[0][1]
most_common_w_cnt = frequency_w_list[0][1]

most_common_h_list = []
for x in frequency_h_list:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in frequency_w_list:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0

cnt = most_common_h_cnt + most_common_w_cnt + add

print(cnt)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PHF = defaultdict(int)
PWF = defaultdict(int)
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PHF[h] += 1
    PWF[w] += 1
    PF[h, w] += 1

sorted_PHF = sorted(PHF.items(), key=lambda x: x[1], reverse=True)
sorted_PWF = sorted(PWF.items(), key=lambda x: x[1], reverse=True)
most_common_h_cnt = sorted_PHF[0][1]
most_common_w_cnt = sorted_PWF[0][1]

most_common_h_list = []
for x in sorted_PHF:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in sorted_PWF:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0
            break

cnt = most_common_h_cnt + most_common_w_cnt + add

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

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    d = [[INF]*N for _ in range(N)]
    from scipy.sparse.csgraph import floyd_warshall
    for i in range(N):
        d[i][i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a][b] = c
            d[b][a] = c
    #
    '''
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][k]+d[k][j], d[i][j])    
    '''
    d = floyd_warshall(d)
    #
    d2 = [[INF]*N for _ in range(N)]
    for i in range(N):
        d2[i][i] = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                d2[i][j] = 1
    #
    '''
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d2[i][j] = min(d2[i][k]+d2[k][j], d2[i][j])    
    '''
    d2 = floyd_warshall(d2)
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s][t]
        if dist == INF:
            print(-1)
        else:
            print(dist-1)


main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
ii0 = lambda: ii() - 1
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M,L = mis()
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    INF = np.iinfo(np.int64).max
    d = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d[i,i] = 0
    #
    for _ in range(M):
        a,b,c = mis()
        a -= 1
        b -= 1
        if c <= L:
            d[a,b] = c
            d[b,a] = c
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d[i,:], d[i,k]+d[k,:], out=d[i,:])    
    '''
    d = floyd_warshall(d)
    #
    d2 = np.full((N,N), INF, dtype=np.uint64)
    for i in range(N):
        d2[i, i] = 0
    for i in range(N):
        for j in range(N):
            if d[i, j] <= L:
                d2[i, j] = 1
    #
    '''
    for k in range(N):
        for i in range(N):
            np.minimum(d2[i,:], d2[i,k]+d2[k,:], out=d2[i,:])    
    '''
    d2 = floyd_warshall(d2)
    #
    Q = ii()
    for _ in range(Q):
        s,t = mis()
        s -= 1
        t -= 1
        dist = d2[s,t]
        if dist == INF:
            print(-1)
        else:
            print(int(dist)-1)




main()
### BUGGY CODE ###

#import numpy as np
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = []
c = [sum(p[i:i+k]) for i in range(len(p)-k+1)]
#print(c)
#pn = np.array(p)
#v = np.array([1]*k)
#c = np.convolve(pn, v, mode='same')
print((max(c)+k)/2)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s = 0
rs = sum(p[0:k])
ms = rs
for i in range(1, n - k + 1):
  rs = rs - p[i-1] + p[i+k-1]
  if rs > ms:
    s = i
    ms = rs

ans = 0.0
for pp in p[s:s+k]:
  ans += (1+pp)/2
print(ans)

#for i in range(len(p)-k+1):
#  s = sum(p[i:i+k])
#  if s>m: m=s  

#c = [sum(p[i:i+k]) for i in range(len(p)-k+1)]
#print(c)
#pn = np.array(p)
#v = np.array([1]*k)
#c = np.convolve(pn, v, mode='same')
#print((max(c)+k)/2)
### BUGGY CODE ###

from collections import defaultdict as dd
import sys
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
def dfs(n):
  global visited
  global res
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      dfs(o)
dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)

### FIXED CODE ###

from collections import defaultdict as dd
from collections import deque as dq
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
Q = dq([])
Q.append(1)
visited[1] = 1
while len(Q) != 0:
  n = Q.pop()
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      Q.append(o)
#def dfs(n):
#  global visited
#  global res
#  visited[n] = 1
#  for o in e[n]:
#    if visited[o] == 0:
#      res[o] += res[n]
#      dfs(o)
#dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
s=[0]+list(itertools.accumulate(a))

dp=[[10**10]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
def c(i,j):
    if dp[i][j]!=10**10:
        return dp[i][j]
    else:
        S=s[j]-s[i]
        for k in range(1,j-i):
            dp[i][j]=min(c(i,i+k)+c(i+k,j)+S,dp[i][j])
        return dp[i][j]

print(c(0,n))

### FIXED CODE ###

import itertools

n=int(input())
a=list(map(int,input().split()))
s=[0]+list(itertools.accumulate(a))

dp=[[10**20]*(n+1) for _ in range(n)]
for l in range(n):
    dp[l][l+1]=0
for d in range(2,n+1): 
    for k in range(1,d):
        for i in range(n-d+1):
            j=i+d
            S=s[j]-s[i]
            dp[i][j]=min(dp[i][i+k]+dp[i+k][j]+S,dp[i][j])

print(dp[0][n])
### BUGGY CODE ###

from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[hh + 1, ww], [hh - 1, ww], [hh, ww + 1], [hh, ww - 1]]
        min_num = inf
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                min_num = min(min_num, visit[h_][w_])
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
        if visit[hh][ww] == inf:
            visit[hh][ww] = min_num + 1

    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
if ans < 0:
    ans = -1
print(ans)

### FIXED CODE ###

from queue import Queue

def bfs(point):
    global visit, s
    while point.qsize() > 0:
        hh, ww = point.get()
        h_w_list = [[1, 0], [- 1, 0], [0, 1], [0, - 1]]
        for h_, w_ in h_w_list:
            h_ = h_ + hh
            w_ = w_ + ww
            if (h_ in range(h)) & (w_ in range(w)):
                if s[h_][w_] == ".":
                    if visit[h_][w_] == inf:                    
                        point.put([h_, w_])
                        visit[h_][w_] = visit[hh][ww] + 1
        
    
inf = 10 ** 9    
h, w = map(int, input().split())
s = []
point_num = 0
for _ in range(h):
    k = input()
    point_num += k.count(".")
    s.append(list(k))
visit = [[inf for _ in range(w)] for _ in range(h)]
point = Queue()
point.put([0, 0])
visit[0][0] = 0
bfs(point)
ans = point_num - visit[-1][-1] - 1
if ans < 0:
    ans = -1
print(ans)
### BUGGY CODE ###

N = int(input())
Lists = []
ans = 0
for _ in range(3):
    s = [int(e) for e in input().split()]
    s.sort()
    Lists.append(s)
def bin(right,left,i,j):
    global ans
    while(right >= left):
        mid =int(left + (right-left) / 2)
        if(i>=Lists[j][mid]):
            left = mid + 1
        else:
            right = mid - 1
    if(j == 2 and left <= N-1):
        ans += N-left
    elif(left <= N-1):
        for k in range(left,N):
            bin(N-1,0,Lists[j][k],j+1)
for i in Lists[0]:
    bin(N-1,0,i,1)
print(ans)


### FIXED CODE ###

N = int(input())
Lists = []
ans = 0
for _ in range(3):
    s = [int(e) for e in input().split()]
    s.sort()
    Lists.append(s)
def bin(i,j):
    global t,s
    right = N-1;left = 0
    while(right >= left):
        mid = int(left + (right-left)/2)
        if(j==0):
            if(i>Lists[j][mid]):
                left = mid + 1
            else:
                right = mid -1
        else:
            if(i>=Lists[j][mid]):
                left = mid + 1
            else:
                right = mid - 1
    if(j == 0):
        t = left
    else:
        s = N - left
for i in Lists[1]:
    bin(i,0)
    bin(i,2)
    ans += t*s
print(ans)
### BUGGY CODE ###

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

    res = 0
    balls = {}

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1

    while len(set(A)) > k:
        
        minValue = 200000
        maxValue = 0

        for key, value in balls.items():
            if value < minValue and value > 0:
                minValue = value
                minKey = key
        
            if value > maxValue:
                maxValue = value
                maxKey = key
        
        A[A.index(minKey)] = maxKey
        balls[minKey] -= 1
        balls[maxKey] += 1

        res += 1
    
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    res = 0
    balls = {}
    bucket = [[] for _ in range(n+1)]

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    for key, value in balls.items():
        bucket[value].append(key)

    for i in range(len(bucket)):
        for j in range(len(bucket[i])):
            if bucket[i] != [] and len(balls) > k:
                res += i
                balls.pop(bucket[i][j])

    print(res)

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

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

def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  d = [float('inf')]*n
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != float('inf') and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = -float('inf')
      if i == n-1:
        temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  es.append([x-1, y-1, (z-p)*(-1)])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')

### FIXED CODE ###

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

def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  inf = float('inf')
  d = [inf for _ in range(n)]
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != inf and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = (-1)*inf
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  es.append([x-1, y-1, (z-p)*(-1)])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')
### BUGGY CODE ###

mod = 10**9 + 7

N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]

def dot(X, Y):
    x = len(X)
    y = len(Y[0])
    z = len(Y)
    C = [[0] * y for _ in range(x)]
    for i in range(x):
        for j in range(y):
            for k in range(z):
                C[i][j] += X[i][k] * Y[k][j]
                C[i][j] %= mod
    return C

B = [[0] * N for _ in range(N)]
for k in range(N):
    B[k][k] = 1

while K > 0:
    if K & 1:
        B = dot(B, A)
    A = dot(A, A)
    K >>= 1

ans = 0
for i in range(N):
    for j in range(N):
        ans += B[i][j]
        ans %= mod

print(ans)

### FIXED CODE ###

mod = 10**9 + 7

N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]

def dot(X, Y):
    x = len(X)
    y = len(Y[0])
    z = len(Y)
    C = [[0] * y for _ in range(x)]
    for i in range(x):
        for j in range(y):
            for k in range(z):
                C[i][j] += X[i][k] * Y[k][j]
                C[i][j] %= mod
    return C

B = [[0] * N for _ in range(N)]
for k in range(N):
    B[k][k] = 1

while K > 0:
    if K & 1:
        B = dot(B, A)
    A = dot(A, A)
    K >>= 1

ans = 0
for i in range(N):
    for j in range(N):
        ans += B[i][j]
        ans %= mod

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

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 隣接行列
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True

# 隣接リスト
route2 = [[] for n in range(N)]

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque()
visited = []

queue.append(0)
visited.append(0)

while queue:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    
    for r in route2[now]: 
    # for r in range(N):
        if r not in visited:
        # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(r)
            visited.append(r)

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[r]:
                room_depth[r] = min(room_depth[now] + 1, room_depth[r])
            else:
                room_depth[r] = room_depth[now] + 1

            room_sign[r] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


def solve():
    S = input()[:-1]
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            #dig = 10**i
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   # dp[i+1][j] += dp[i][(k*dig+j) % 13]
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            #dig = 10**i
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                #dp[i+1][j] = dp[i][(int(S[i])*dig+j) % 13]
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


def brute():
    S = input()[:-1]
    print(S)

    Q = [""]
    for c in reversed(S):
        tmp = []
        if c == "?":
            print("?")
            for q in Q:
                for i in range(0, 10):
                    tmp.append(str(i)+q)
        else:
            for q in Q:
                tmp.append(c+q)
        Q = tmp

    Q = sorted(Q)
    cnt = 0
    for q in Q:
        if int(q) % 13 == 5:
            cnt += 1
            print(int(q))
    print(cnt)
    print(cnt % MOD)


def solve():
    S = input()[:-1]
    # dp[i+1][j]イバン目まで見て、あまりがjのこすう
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            #dig = 10**i
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   # dp[i+1][j] += dp[i][(k*dig+j) % 13]
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            #dig = 10**i
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                #dp[i+1][j] = dp[i][(int(S[i])*dig+j) % 13]
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()