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

H, W = map(int, input().split())
S = ""
for i in range(H):
    S += input()

vert = [0] * (H*W)
horz = [0] * (H*W)

for i in range(H*W):
    if S[i] == '.':
        if i - W >= 0:
            if S[i - W] == '.':
                vert[i] = vert[i - W]
                continue
        j = i
        L = 0
        while True:
            if j >= H * W:
                vert[i] = L
                break
            if S[j] == '.':
                L += 1
            else:
                vert[i] = L
                break
            j += W

for i in range(H*W):
    if S[i] == '.':
        if i % W > 0:
            if S[i - 1] == '.':
                horz[i] = horz[i - 1]
                continue
        j = i
        L = 0
        while True:
            if S[j] == '.':
                L += 1
            else:
                horz[i] = L
                break
            j += 1
            if j % W == 0:
                horz[i] = L
                break

light = [0] * (H*W)
for i in range(H * W):
    light[i] = horz[i] + vert[i]
print(max(light) - 1)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(1, W):
            if grid[h][w-1] == '.' and grid[h][w] == '.':
                L[h][w] = L[h][w-1] + 1
    for h in range(H):
        for w in range(W-2, -1, -1):
            if grid[h][w] == '.' and grid[h][w+1] == '.':
                R[h][w] = R[h][w+1] + 1
    for w in range(W):
        for h in range(1, H):
            if grid[h][w] == '.' and grid[h-1][w] == '.':
                U[h][w] = U[h-1][w] + 1
    for w in range(W):
        for h in range(H-2, -1, -1):
            if grid[h][w] == '.' and grid[h+1][w] == '.':
                D[h][w] = D[h+1][w] + 1

    ans = 1
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] + 1)
    print(ans)


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

ABN = input().split()
A = int(ABN[0])
B = int(ABN[1])
N = int(ABN[2])

answer = 0
temp = 0

for x in range(N+1):
    temp = (A*x)//B - A * (x//B)

    if answer < temp:
        answer = temp

print(answer)

### FIXED CODE ###

ABN = input().split()
A = int(ABN[0])
B = int(ABN[1])
N = int(ABN[2])

answer = 0
temp = 0

if N >= B:
    answer = A*(B-1) // B - A * ((B-1)//B)

else:
    answer = A*N //B - A * (N//B)

print(answer)
### BUGGY CODE ###

import math

N = int(input())

A = []
B = []
C = []
for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            C.append(a)
        else:
            c = a*pow(10,len(s)-s.find('.')-1)+b
            d = pow(10,len(s)-s.find('.')-1)
            g = math.gcd(c,d)
            if(d//g <= 200000):
                A.append(c//g)
                B.append(d//g)
    else:
        C.append(int(s))

ans = len(C) * (len(C)-1) // 2
for i in range(len(A)):
    for j in range(len(C)):
        if A[i]*C[j]%B[i]==0:
            ans += 1
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        if (A[i]%B[j]==0) and (A[j]%B[i]==0):
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = []

for i in range(N):
    s = input()
    if '.' in s:
        a,b = map(int,s.split('.'))
        if(int(b)==0):
            c = a
            d = 1
        else:
            c = a*pow(10,len(s)-s.find('.')-1)+b
            d = pow(10,len(s)-s.find('.')-1)
    else:
        c = int(s)
        d = 1
    e = 0
    f = 0
    while(c != 0 and c%2==0):
        e += 1
        c //= 2
    while(c != 0 and c%5==0):
        f += 1
        c //= 5
    while(d%2==0):
        e -= 1
        d //=2
    while(d%5==0):
        f -= 1
        d //=5
    A.append([e,f])

tm = max(max([a[0] for a in A]), -1 * min([a[0] for a in A])) + 1
fm = max(max([a[1] for a in A]), -1 * min([a[1] for a in A])) + 1

B = [[0] * (tm * 2 ) for _ in range(fm * 2)]

for a in A:
    B[a[1]+fm][a[0]+tm] += 1

for i in range(fm*2):
    for j in range(tm*2):
        if(i>0):
            B[i][j] += B[i-1][j]
        if(j>0):
            B[i][j] += B[i][j-1]
        if(i>0 and j>0):
            B[i][j] -= B[i-1][j-1]

ans = 0
for a in A:
    i = -1 * a[1] + fm
    j = -1 * a[0] + tm
    ans += B[fm*2-1][tm*2-1] - B[fm*2-1][j-1] - B[i-1][tm*2-1] + B[i-1][j-1]
    if a[1]>=0 and a[0]>=0:
        ans -= 1

print(ans//2)
### BUGGY CODE ###

data = list(map(int, input().split()))
X = data[0]
K = data[1]
D = data[2]

if X < 0:
    X *= -1
for i in range(K):
    if X-D <= 0:
        if D-X > X:
            i -= 1
            break
    X -= D
if (K-i-1)%2 == 0:
    print(abs(X))
else:
    if X > 0:
        print(D-X)
    else:
        print(X+D)

### FIXED CODE ###

import decimal    

data = input().split()
X = decimal.Decimal(data[0])
K = decimal.Decimal(data[1])
D = decimal.Decimal(data[2])
if X < 0:
    X *= -1
if X/D-X//D > 0.5:
    y = X//D + 1
else:
    y = X//D
if y > K:
    y = K
X -= y * D

if (K-y)%2 == 0:
    print(abs(X))
else:
    if X > 0:
        print(D-X)
    else:
        print(X+D)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
Prob = [[int(_) for _ in input().split()] for _ in range(Q)]

for i, j in Prob:
    print(S[i-1:j].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
Prob = [[int(_) for _ in input().split()] for _ in range(Q)]
numlist = [0, ]
cnt = 0

for i in range(1, N):
    if S[i-1: i+1] == "AC":
        cnt += 1
    numlist.append(cnt)

for j, k in Prob:
    print(numlist[k-1]-numlist[j-1])
### BUGGY CODE ###

import math

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=(math.gcd(math.gcd(i,j),l))
print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=(gcd(i,gcd(j,l)))
print(ans)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
que = deque(maxlen=h * w)
next = deque(maxlen=h * w)

data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0

while len(que) > 0:
    count += 1
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in ((row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)):
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que, next = next, que
    next.clear()

print(count - 1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
que = deque()
data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que = next

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

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

# もし修行により消化コストが全て0になる場合
if sum(a_list) <= k:
    print(0)
    exit()

# 更新メソッド
def update_cost():
    min_cost = []
    for i in range(len(a_list)):
        min_cost.append(a_list[i] * f_list[i])
    return min_cost

# ソート
a_list.sort()
f_list.sort(reverse=True)

# コストリストinit
result_cost = update_cost()


# 修行する
while k > 0:
    # 現状で最もコストが大きいものについて考える
    max_idx = result_cost.index(max(result_cost))

    # 修行実行
    a_list[max_idx] -= 1
    a_list.sort()

    # コストリスト更新
    result_cost = update_cost()

    # 修行数減らす
    k -= 1

print(max(result_cost))

### FIXED CODE ###

# # もし修行により消化コストが全て0になる場合
# if sum(a_list) <= k:
#     print(0)
#     exit()

# # 更新メソッド
# def update_cost(max_idx, result_cost, a_list, f_list):

#     result_cost[max_idx] = a_list[max_idx] * f_list[max_idx]

#     if max_idx == 0:
#         pass
#     else:
#         result_cost[max_idx-1] = a_list[max_idx-1] * f_list[max_idx-1]

#     return result_cost

# # ソート
# a_list.sort()
# f_list.sort(reverse=True)

# # コストリストinit
# result_cost = [a_list[idx] * f_list[idx] for idx in range(len(a_list))]


# # 修行する
# while k > 0:
#     # 現状で最もコストが大きいものについて考える
#     max_idx = result_cost.index(max(result_cost))

#     # 修行実行
#     a_list[max_idx] -= 1
#     a_list.sort()

#     # コストリスト更新
#     result_cost = update_cost(max_idx, result_cost, a_list, f_list)

#     # 修行数減らす
#     k -= 1

# print(max(result_cost))

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

A = np.array(input().split(), np.int)
F = np.array(input().split(), np.int)

A.sort()
F.sort()
F = F[::-1]

left = -1 
right = (A * F).sum()

while (right-left) > 1:
    # print(left, right)
    split_line = (left + right) // 2
    r = np.maximum(0, A-split_line // F).sum() <= k
    if r:
        right = split_line
    else:
        left = split_line

print(right)
### BUGGY CODE ###

from collections import defaultdict
import math

def culcD(a,b):
  x1,y1,r1=a
  x2,y2,r2=b
  return max(0,math.sqrt((x1-x2)**2+(y1-y2)**2)-(r1+r2))

A=[]

xs,ys,xg,yg=map(int,input().split())
A.append((xs,ys,0))
A.append((xg,yg,0))

V=defaultdict(int)
V[(0,1)]=(culcD(A[0],A[1]))
V[(1,0)]=(culcD(A[0],A[1]))

N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  A.append((x,y,r))
  for j in range(len(A)-1):
    dist = culcD(A[j],A[-1])
    V[(i+2,j)]=dist
    V[(j,i+2)]=dist

def dijkstra(n):
  d=[float('inf')]*(n+2)
  d[0]=0
  used=[False]*(n+2)
  
  while True:
    v=-1
    for i in range(n+2):
      if used[i]==False and (v==-1 or d[i] < d[v]):
        v=i
    if v==-1:
      break
    used[v]=True
    for j in range(n+2):
      d[j]=min(d[j],d[v]+V[(j,v)])

  return d[1]

print(dijkstra(N))

### FIXED CODE ###

from collections import defaultdict
import math

def culcD(a,b):
  x1,y1,r1=a
  x2,y2,r2=b
  return max(0,math.sqrt((x1-x2)**2+(y1-y2)**2)-(r1+r2))

A=[]

xs,ys,xg,yg=map(int,input().split())
A.append((xs,ys,0))
A.append((xg,yg,0))

V=defaultdict(int)
V[(0,1)]=(culcD(A[0],A[1]))
V[(1,0)]=(culcD(A[0],A[1]))

N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  A.append((x,y,r))
  for j in range(len(A)-1):
    dist = culcD(A[j],A[-1])
    V[(i+2,j)]=dist
    V[(j,i+2)]=dist

def dijkstra(n):
  d=[float('inf')]*(n+2)
  d[0]=0
  used=[False]*(n+2)
  
  while True:
    v=-1
    for i in range(n+2):
      if used[i]==False and (v==-1 or d[i] < d[v]):
        v=i
    if v==-1:
      break
    used[v]=True
    for j in range(n+2):
      d[j]=min(d[j],d[v]+V[(j,v)])

  return d[1]

print(dijkstra(N))
### BUGGY CODE ###

n, q = map(int, input().split())

s =[set([i]) for i in range(n)]
p =[i for i in range(n)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if y in s[p[x]]: print(1)
        else: print(0)
    else:
        s[p[x]] = s[p[x]] | s[p[y]]
        p_x_tmp = p[x]
        p_y_tmp = p[y]
        for j in range(n):
            if p[j] == p_y_tmp: p[j] = p_x_tmp

### FIXED CODE ###

def find(x):
    global s
    if s[x] == x:
        return x
    s[x] = find(s[x])
    return s[x]

n, q = map(int, input().split())

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

for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if find(x) == find(y): print(1)
        else: print(0)
    else:
        s[find(y)] = find(x)
### BUGGY CODE ###

import numpy as np
n = int(input())

d = np.ones(n)

for i in range(2, n+1):
    k = 1
    while i*k <= n:
        d[i*k-1] += 1
        if k == 1:
            d[i*k-1] *= i
        k += 1

print(int(sum(d)))

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
  d = n // i
  ans += d*(d+1)//2*i
print(ans)
### BUGGY CODE ###

import fractions
 
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def LI():
  return [int(s) for s in input().split()]
 
N = int(input())
A_s = LI()
 
mod = 10**9 + 7
 
l = lcm_list(A_s)
 
print(sum(map(lambda x : l//x, A_s)) % mod)

### FIXED CODE ###

import fractions
 
N = int(input())

def LI():
  return [int(s) for s in input().split()]

A_s = LI()
mod = 10**9 + 7

#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

count = 0
for a in A_s:
  count+=l//a
  
print(count % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
A=list(map(int,input().split()))
if n==1:
    ans=(m//(A[0]//2)+1)//2
    print(int(ans))
    exit()
from fractions import gcd
kou=A[0]*A[1]//gcd(A[0],A[1])
for a in A:
    kou=a*kou//gcd(a,kou)
for a in A:
    if (kou//a)%2==0:
        print(0)
        exit()
kou//=2
#print(kou)
ans=(m//kou+1)//2
print(int(ans))


### FIXED CODE ###

def main():
    """"ここに今までのコード"""
    import sys
    input = sys.stdin.readline
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    #A.sort()
    if n==1:
        ans=(m//(A[0]//2)+1)//2
        print(int(ans))
        exit()
    from fractions import gcd
    kou=A[0]*A[1]//gcd(A[0],A[1])
    for a in A:
        kou=a*kou//gcd(a,kou)
        if (kou//a)%2==0:
            print(0)
            exit()
    kou//=2
    #print(kou)
    ans=(m//kou+1)//2
    print(int(ans))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
H = [int(h) for h in input().split()]
H = np.array(H, dtype=np.int32)

dp = np.array([0]*(N+1), dtype=np.int32)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    if n < K:
        dp[n] = np.amin(dp[np.maximum(n-k, 0)] + np.abs(H[n]-H[np.maximum(n-k, 0)]))
    else:
        dp[n] = np.amin(dp[n - k] + np.abs(H[n] - H[n - k]))


print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
# H = np.array([int(h) for h in input().split()])
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = max(n-K, 0)
    #if n < K:
    #   dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    #else:
    #   dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))
    dp[n] = np.min(dp[start:n] + np.abs(H[n]-H[start:n]))

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

from collections import Counter as c
m=int(input())
a=list(map(int,input().split()))

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

arr=[]
for i in a:
  arr+=make_divisors(i)

commonarr=c(arr).most_common()
ans=0
for i in commonarr:
  if i[1]>=m-1:
    ans=max(ans,i[0])
  else:
    break
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
i=a[1]
while i > 0:
  flg=0
  for j in a:
    if j%i!=0:
      flg+=1
      if flg>1:
        break
  if flg<=1:
    print(i)
    break
  else:
    i-=1
### BUGGY CODE ###

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

Result = []
for i in range(0,40):
	Result.append(0)

for i in range(A,B+1):
	li=list(bin(i))
	#print(li)
	li.reverse()
	for j in range(len(li)):
		if li[j] == "1":
			Result[j]=Result[j]+1

#print(Result)
R2 = list(map(lambda x: str(x%2),Result))

#for k in R2[::-1]:
#	if k == "0":
#		R2.pop()
#	else:
#		break

R2.reverse()
#print(R2)
print(int("0b"+"".join(R2),2))

### FIXED CODE ###

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

def f(x):
	if x == 0:
		return 0
	elif x%2==0:
		return int(x/2)%2 ^ x
	else:
		return int((x-1)/2)%2 ^ x-1 ^ x

if A==B:
	print(B)
elif A == 0:
	print(0^f(B))
else:
	print(f(A-1)^f(B))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sum(a)
for i in range(n-1):
    if a[i]<0:
        a[i]=a[i]*(-1)
        a[i+1]=a[i+1]*(-1)
    b=max(b,sum(a))
print(sum(a))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in a:
    if i<0:
        cnt+=1
s=0
for i in range(n):
    s+=abs(a[i])
if cnt%2==1:
    c=10**10
    for i in range(n):
        num=abs(a[i])
        if num<c:
            c=num
    s=s-(c*2)
print(s)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
l = []
for i in range(1, N):
    for j in range(i+1, N+1):
        s = j -i
        if 0 < i < Y:
            ss = abs(j - Y) + abs(X - i) + 1 
            l.append(min(s, ss))
        elif i >= Y:
            l.append(s)
for i in range(1, N):
    print(l.count(i))

### FIXED CODE ###

N, X, Y = map(int, input().split())
l = [0] * (N-1)
for i in range(1, N):
    for j in range(i+1, N+1):
        s = j -i
        if 0 < i < Y:
            ss = abs(j - Y) + abs(X - i) + 1 
            l[min(s, ss)-1] += 1
        elif i >= Y:
            l[s-1] += 1
for i in range(N-1):
    print(l[i])
### BUGGY CODE ###

#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=[]

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.append(a[i])
    for j in range(a[i]*2,max_a+1,a[i]):
      check.append(j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

  
    
    

### FIXED CODE ###

#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=set()

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.add(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.add(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

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

def z_algorithm(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def main():
    N = int(input())
    S = input()
    l = len(S)
    answer = 0
    for i in range(1, N - 1):
        a = z_algorithm(S[i:])
        for j in range(1, l - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def z_algorithm(S):
    n = len(S)
    A = [0] * n
    A[0] = n
    L = 0
    R = 0
    # 過去にS[R]まで調べたとする
    for i in range(1, n):
        if R <= i:
            L = R = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
        elif A[i - L] < R - i:
            A[i] = A[i - L]
        else:
            L = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
    return A


def main():
    N = int(input())
    S = input()
    answer = 0
    for i in range(N):
        a = z_algorithm(S[i:])
        for j in range(1, N - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


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


S=str(input())
S_list=list(S)

Q=int(input())

q=[]
for i in range(Q):
   q.append(input().split())

for i in range(Q):
    if q[i][0]=="1":
        S_list.reverse()
    elif q[i][0]=="2":
        if q[i][1]=="1":
            S_list.insert(0,q[i][2])
        elif q[i][1]=="2":
            S_list.append(q[i][2])

S=''.join(S_list)
print(S)

### FIXED CODE ###

S=str(input())
S_list=list(S)

Q=int(input())

q=[]
right=[]
left=[]

rev=1

for i in range(Q):
    q.append(input().split())
    if q[i][0]=="1":
        rev=rev*(-1)
    elif q[i][0]=="2":
        if q[i][1]=="1":
            if rev==1:
                right.append(q[i][2])
            else:
                left.append(q[i][2])
        elif q[i][1]=="2":
            if rev==1:
                left.append(q[i][2])
            else:
                right.append(q[i][2])
right.reverse()
if rev==1:
    S_list=right+S_list+left
else:
    S_list=right+S_list+left
    S_list.reverse()

S=''.join(S_list)
print(S)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ac = sorted(list(set(a)))
ans = []
for i in ac[::-1]:
    c = a.count(i)
    if len(ans) == 2:
        break
    if not ans and c >= 4:
        print(i ** 2)
        exit()
    if c >= 2:
        ans.append(i)
if len(ans) == 2:
    print(ans[0] * ans[1])
else:
    print(0)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
ac = collections.Counter(a)
quad = [i for i in ac if ac[i] >= 4]
if quad:
    ans = max(quad) ** 2
else:
    ans = 0
twice = sorted([i for i in ac if ac[i] >= 2])
if len(twice) >= 2:
    ans = max(ans, twice[-1] * twice[-2])
print(ans)
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = input()

div_num = 10 ** 9 + 7
arr = np.arange(13, dtype = int)
# dp = [[0 for _ in range(13)] for _ in range(len(S))]
dp = np.zeros([len(S), 13], dtype = int)

if S[-1] == "?":
    for ii in range(10): dp[0, ii] = 1
else:
    dp[0, int(S[-1])] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == '?':
        for n in range(10):
            res = ((10 ** ii) * n) % 13
            res = (arr + res) % 13
            for jj in range(13):
                dp[ii, res[jj]] += dp[ii - 1, jj]
                if dp[ii, res[jj]] > div_num: dp[ii, res[jj]] -= div_num
    else:
        res = ((10 ** ii) * int(S[ind])) % 13
        res = (arr + res) % 13
        for jj in range(13):
            dp[ii, res[jj]] += dp[ii - 1, jj]
            if dp[ii, res[jj]] > div_num: dp[ii, res[jj]] -= div_num

print (dp[-1, 5])


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)