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

from collections import deque
h , w = map(int,input().split())
ch , cw = map(lambda x:int(x)-1,input().split())
dh , dw = map(lambda x:int(x)-1,input().split())
ma = [list(input()) for i in range(h)]
visit = [[-1 for i in range(w)] for j in range(h)]
cou = -1
p = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    for j in range(w):
        if visit[i][j] != -1 or ma[i][j] == "#":
            continue
        cou += 1
        visit[i][j] = cou
        d = deque()
        d.append((i,j))
        while d:
            now = d.popleft()
            for x , y in p:
                if 0 <= now[0]+x < h and 0 <= now[1]+y < w:
                    if ma[now[0]+x][now[1]+y] == "." and visit[now[0]+x][now[1]+y] == -1:
                        visit[now[0]+x][now[1]+y] = cou
                        d.append(((now[0]+x,now[1]+y)))

st = visit[ch][cw]
go = visit[dh][dw]
route = [set() for i in range(cou+1)]

for i in range(h):
    for j in range(w):
        if visit[i][j] == -1:
            continue
        for s in range(-2,3,1):
            for t in range(-2,3,1):
                if 0<=i+s<h and 0<=j+t<w:
                    if visit[i+s][j+t] != -1 and visit[i+s][j+t] != visit[i][j]:
                        route[visit[i][j]].add(visit[i+s][j+t])

kyori = [-1 for i in range(cou+1)]
kyori[st] = 0
d = deque()
d.append(st)

while d:
    now = d.popleft()
    for i in route[now]:
        if kyori[i] == -1:
            kyori[i] = kyori[now] + 1
            d.append(i)

print(kyori[go])

### FIXED CODE ###

from collections import deque
h , w = map(int,input().split())
ch , cw = map(lambda x:int(x)-1,input().split())
dh , dw = map(lambda x:int(x)-1,input().split())
ma = [list(input()) for i in range(h)]
visit = [[-1 for i in range(w)] for j in range(h)]
cou = -1
p = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    for j in range(w):
        if visit[i][j] != -1 or ma[i][j] == "#":
            continue
        cou += 1
        visit[i][j] = cou
        d = deque()
        d.append((i,j))
        while d:
            now = d.popleft()
            for x , y in p:
                if 0 <= now[0]+x < h and 0 <= now[1]+y < w:
                    if ma[now[0]+x][now[1]+y] == "." and visit[now[0]+x][now[1]+y] == -1:
                        visit[now[0]+x][now[1]+y] = cou
                        d.append(((now[0]+x,now[1]+y)))

st = visit[ch][cw]
go = visit[dh][dw]
route = [set() for i in range(cou+1)]

for i in range(h):
    for j in range(w):
        if visit[i][j] == -1:
            continue
        for s in range(-2,3,1):
            for t in range(-2,3,1):
                if 0<=i+s<h and 0<=j+t<w:
                    if visit[i+s][j+t] != -1 and visit[i+s][j+t] != visit[i][j]:
                        route[visit[i][j]].add(visit[i+s][j+t])

kyori = [-1 for i in range(cou+1)]
kyori[st] = 0
d = deque()
d.append(st)

while d:
    now = d.popleft()
    for i in route[now]:
        if kyori[i] == -1:
            kyori[i] = kyori[now] + 1
            d.append(i)

print(kyori[go])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x: -x[1])
# print(a)
# print(bc)

count = 0
end = False
for b, c in bc:
  if end:
    break
  if len(a) <= 0:
    break
  for j in range(b):
    if end:
      break
    if a[0] < c:
      count += c
      # print(c)
      del a[0]
    else:
      end = True

print(count + sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x: -x[1])
# print(a)
# print(bc)

count = 0
idx = -1
end = False
for b, c in bc:
  if idx + b <= n-1 and a[idx+b] < c:
    count += b * c
    idx += b
  else:
    for i in range(idx+1, idx+1+b):
      if i >= n or end:
        break
      else:
        if a[i] < c:
          count += c
          idx += 1
        else:
          end = True
  # print((idx, count))
  if end:
    break

if idx <= n-2:
  count += sum(a[idx+1:])

print(count)
### BUGGY CODE ###

D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(input())-1 for _ in range(D)]

def calc(x):
    res = 0
    last = 0
    for day,i in enumerate(range(D),1):
        if t[i] == x:
            last = day
            res += s[i][x]
        res -= c[x]*(day-last)
    return res

score = [0]*26
for i in range(26): score[i] = calc(i)
M = int(input())
ans = [0]*M
for i in range(M):
    d,q = map(int,input().split())
    d -= 1
    q -= 1
    old = t[d]
    t[d] = q
    score[old] = calc(old)
    score[q] = calc(q)
    ans[i] = sum(score)
for i in range(M): print(ans[i])


### FIXED CODE ###

D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(input())-1 for _ in range(D)]

def scoreing(x):
    res = 0
    last = 0
    for day,i in enumerate(range(D),1):
        if t[i] == x:
            last = day
            res += s[i][x]
        res -= c[x]*(day-last)
    return res

score = [0]*26
for i in range(26): score[i] = scoreing(i)
M = int(input())
ans = [0]*M
for i in range(M):
    d,q = map(int,input().split())
    d -= 1
    q -= 1
    old = t[d]
    t[d] = q
    score[old] = scoreing(old)
    score[q] = scoreing(q)
    ans[i] = sum(score)
for i in range(M): print(ans[i])
### BUGGY CODE ###

import heapq
import math
a,b=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
if b>=sum(c):
  print(0)
else:
  c.sort()
  d.sort(reverse=True)
  e=[c[i]*d[i] for i in range(a)]
  f=[]
  for i in range(a):
    heapq.heappush(f,-e[i])
  k=0
  while k<b or f[0]==0:
    x=-heapq.heappop(f)
    y=e.index(x)
    z=min(b-k,(x+f[0])//d[y]+1)
    k+=z
    c[y]=c[y]-z
    e[y]=c[y]*d[y]
    heapq.heappush(f,-e[y])
  print(-f[0])

### FIXED CODE ###

import math
a,b=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
c.sort()
d.sort(reverse=True)
e=[0 for i in range(a)]
for i in range(a):
  e[i]=c[i]*d[i]
def s(e,x):
  k=0
  for i in range(a):
    if e[i]<x:
      continue
    else:
      k+=math.ceil((e[i]-x)/d[i])
  if k>b:
    return False
  else:
    return True
    
left=0
right=max(e)
while left!=right:
  mid=(left+right)//2
  if s(e,mid):
    right=mid
  else:
    left=mid+1
print(left)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
from operator import itemgetter

N = int(input())
P = []
for i in range(N):
  x,y = map(int, input().split())
  P.append((x,y,i))
  
P.sort() 
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  D[p][q] = min(abs(a-c), abs(b-d))
    
P.sort(key=itemgetter(1))
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  D[p][q] = min(abs(a-c), abs(b-d))

mst = minimum_spanning_tree(D)
print(int(mst.sum()))

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
from operator import itemgetter

N = int(input())
P = []
for i in range(N):
  x,y = map(int, input().split())
  P.append((x,y,i))
  
data = [10, 20, 30, 40]
row = [0, 0, 1, 1]
col = [1, 2, 0, 2]

#print(csr_matrix((data, (row, col))).toarray())
  
data = []
row = []
col = []

P.sort() 
D = {}
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

P.sort(key=itemgetter(1))
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  if (p,q) in D:
    continue
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

coo = coo_matrix((data, (row, col)), (N, N))
mst = minimum_spanning_tree(coo)
print(int(mst.sum()))
### BUGGY CODE ###

a=int(input())
x=list(map(int, input().split()))
ans=1
for i in range(a):
	ans=ans*x[i]
if ans>10**18:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

a=int(input())
x=list(map(int, input().split()))
ans=1
x.sort()
for i in range(a):

	if x[i]!=1 and x[i]!=0:
		ans=ans*x[i]
	if ans>10**18:
		break
	if x[i]==0:
		ans=0
		break
if ans>10**18:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###

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

X_sub = [[] for i in range(N-K+1)]

for i in range(N-K+1):
    X_sub[i] = X[i:i+K]

min_cost = float('inf')

for i in X_sub:
    tmp_l = abs(i[0]) + abs(i[-1]-i[0])
    tmp_r = abs(i[-1]) + abs(i[0]-i[-1])
    tmp = min(tmp_l,tmp_r)

    if min_cost > tmp:
        min_cost = tmp

print(min_cost)

### FIXED CODE ###

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

min_cost = float('inf')

for i in range(N-K+1):
    l = X[i]
    r = X[i+K-1]
    tmp_l = abs(l) + abs(r-l)
    tmp_r = abs(r) + abs(l-r)
    tmp = min(tmp_l,tmp_r)

    if min_cost > tmp:
        min_cost = tmp

print(min_cost)
### BUGGY CODE ###

difficulties, goal = map(int, input().split())

pcs = [list(map(int, input().split())) for _ in range(difficulties)]

dp = [[0] * 1102 for _ in range(difficulties + 1)]

for d, pc in enumerate(pcs, 1):
    problem, complete = pc

    score = [x*100*d for x in range(problem)] + [problem*100*d+complete] +[0] * 1001

    for i in range(1, 1001):
        for j in range(0, i + 1):
            if i - j > problem:
                dp[d][i] = max(dp[d][i], dp[d - 1][j])
            else:
                dp[d][i] = max(dp[d][i], dp[d-1][j] + score[i-j])

for i, a in enumerate(dp[difficulties]):
    if a >= goal:
        print(i)
        exit()


### FIXED CODE ###

difficulties, goal = map(int, input().split())

pcs = [list(map(int, input().split())) for _ in range(difficulties)]

dp = [[0] * 1102 for _ in range(difficulties + 1)]

total_problem = 0
for d, pc in enumerate(pcs, 1):
    problem, complete = pc
    total_problem += problem

    score = {x: x*100*d for x in range(problem)}
    score[problem] = problem * 100 * d +complete

    for i in range(1, total_problem + 1):
        for j in range(0, i + 1):
            if i - j > problem:
                dp[d][i] = max(dp[d][i], dp[d - 1][j])
            else:
                dp[d][i] = max(dp[d][i], dp[d-1][j] + score[i-j])

for i, a in enumerate(dp[difficulties]):
    if a >= goal:
        print(i)
        exit()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 10**9+7
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans+=(a[i]%m)*(a[j]%m)
        ans%=m
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 10**9+7
x = 0
ans = 0
for i in range(n):
    ans+=a[i]*x
    x += a[i]%m
    ans%=m
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline()[:-1]
from collections import defaultdict
s =input()
lenth=len(s)
ss=s*2
t =input()
place=defaultdict(list)

for k,l in enumerate(s):
	for word in range(97, 97+26):
		word=chr(word)
		if word==l:
			place[word].append(k+1)
			place[word].append(k+1+lenth)

now=0
ans=0
for i in t:
	if not place[i]:
		print(-1)
		exit()
	mt=min((j for j in place[i] if j>now))
	if mt>lenth:
		mt-=lenth
		ans+=lenth
	now=mt
print(ans+now)



			

	





	

### FIXED CODE ###

import sys
from bisect import bisect_right
input = lambda: sys.stdin.readline()[:-1]
from collections import defaultdict
s =input()
lenth=len(s)
ss=s*2
t =input()
place=defaultdict(list)

for k,l in enumerate(s):
	place[l].append(k+1)
	place[l].append(k+1+lenth)
for i in place.values():
	i.sort()
now=0
ans=0

for i in t:
	if not place[i]:
		print(-1)
		exit()
	mt=place[i][bisect_right(place[i],now)]
	if mt>lenth:
		mt-=lenth
		ans+=lenth
	now=mt
print(ans+now)
### BUGGY CODE ###

s = input()

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [(int(s[len(s) - i - 1]) * (10 ** i)) % 2019 for i in range(len(s))]
	cnt = 0
	for i in range(len(nums)):
		k = nums[i]
		if k == 0:
			cnt += 1
		for j in range(i + 1, len(nums)):
				k = (k + nums[j]) % 2019
				if k == 0:
					cnt += 1
	return cnt

print(main(s))

### FIXED CODE ###

import collections
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	p = 0.1
	for i in range(len(s)):
		p = int(p * 10) % 2019
		cur = (cur + int(s[len(s) - 1 - i]) * p) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(n-1):
	for j in range(i+1,n):
		if j-i == a[i]+a[j]:
			c += 1

print(c)

### FIXED CODE ###

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

l = [0]*n
r = [0]*n

l = [i+a[i] for i in range(n)]
r = [i-a[i] for i in range(n)]
ld = {}
rd = {}

c = 0

for i in range(n):
	if l[i] in ld:
		ld[l[i]] += 1
	else:
		ld[l[i]] = 1
	if r[i] in rd:
		rd[r[i]] += 1
	else:
		rd[r[i]] = 1

for i in ld.keys():
	if i in rd:
		c += ld[i]*rd[i]	
	
print(c)
### BUGGY CODE ###

[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [] #L[i][j]はi,j間の最短距離(i<=j)
for i in range(N):
  L.append([10**4 for j in range(N-i)])
for i in range(N):
  L[i][0] = 0
  if i < N-1:
    L[i][1] = 1
L[X-1][Y-X] = 1
for k in range(1,N):
  a = 0
  for i in range(N):
    for j in range(N-i):
      if L[i][j] == k:
        a += 1
      elif L[i][j] > k:
        for p in range(N):
          if p < i:
              L[i][j] = min(L[i][j],L[p][i-p] + L[p][i+j-p])
          elif p < i+j:
              L[i][j] = min(L[i][j],L[i][p-i] + L[p][i+j-p])
          else:
              L[i][j] = min(L[i][j],L[i][p-i] + L[i+j][p-i-j])
  print(a)

### FIXED CODE ###

[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [0 for n in range(N)]
for i in range(N):
  for j in range(N-i):
    L[min(j,abs(X-1-i)+abs(Y-1-i-j)+1,abs(X-1-j-i)+abs(Y-1-i)+1)]+=1
for k in range(1,N):
  print(L[k])
### BUGGY CODE ###

import bisect
INF = float("inf")

A,B,Q = map(int,input().split())
s = [-INF]+[int(input()) for _ in range(A)]+[INF]
t = [-INF]+[int(input()) for _ in range(B)]+[INF]

for i in range(Q):
    q = int(input())
    b,d = bisect.bisect_right(s,q),bisect.bisect_right(t,q)
    ans = INF
    for S in [s[b-1],s[b]]:
        for T in [t[d-1],t[d]]:
            d1,d2 = abs(S-q)+abs(T-S),abs(T-q)+abs(S-T)
            ans = min(ans,d1,d2)
    print(ans)

### FIXED CODE ###

import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
INF = 10**20

A,B,Q = map(int,input().split())
s = [-INF]+[int(input()) for _ in range(A)]+[INF]
t = [-INF]+[int(input()) for _ in range(B)]+[INF]

for i in range(Q):
    q = int(input())
    b,d = bisect.bisect_right(s,q),bisect.bisect_right(t,q)
    ans = INF
    for S in [s[b-1],s[b]]:
        for T in [t[d-1],t[d]]:
            d1,d2 = abs(S-q)+abs(T-S),abs(T-q)+abs(S-T)
            ans = min(ans,d1,d2)
    print(ans)
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
sys.setrecursionlimit(10**7)


def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    def is_binarygraph(v, color):
        colors = [-1] * N
        colors[v] = color
        for n in G[v]:
            if colors[n] == color:
                return False
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, (color+1)%2):
                return False
        return True
    
    if not is_binarygraph(0, 0):
        return -1

    fw = floyd_warshall(G)
    return max(fw)

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
sys.setrecursionlimit(10**7)


def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    colors = [-1] * N
    visited = [False] * N
    def is_binarygraph(v, color):
        visited[v] = True
        for n in G[v]:
            if colors[n] == color:
                return False
            if visited[n]:
                continue
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, colors[n]):
                return False
        return True
    
    colors[0] = 0
    if not is_binarygraph(0, 0):
        return -1

    inf = 10**3
    d = [[inf]*N for _ in range(N)]
    for i in range(N):
        for j in G[i]:
            d[i][j] = 1
    for i in range(N):
        d[i][i] = 0
    
    fw = floyd_warshall(d)
    return np.max(fw) + 1

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

n, k = map(int, input().split())
W, V = [0], [0]
for _ in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(1, k+1):
        if w - W[i] >= 0:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
        else:
            dp[i][w] = dp[i-1][w]
            
print(max(dp[-1]))

### FIXED CODE ###

n, k = map(int, input().split())
W, V = [0], [0]
for _ in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(1, k+1):
        if w - W[i] >= 0:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i])
        else:
            dp[i][w] = dp[i-1][w]
            
print(max(dp[-1]))
### BUGGY CODE ###

from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0
    A = []
    for c in C[i]:
        A.append(dfs(c))

    B = []
    for bits in range(2**len(A)):
        a, b = 0, 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            b += c[((bits >> j & 1) + 1) % 2]
        if a <= X[i]:
            B.append((X[i], b))
        if b <= X[i]:
            B.append((X[i], a))
    if not B:
        print('IMPOSSIBLE')
        exit()

    return min(B)

dfs(1)
print('POSSIBLE')

### FIXED CODE ###

from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0

    A = []
    
    for c in C[i]:
        A.append(dfs(c))

    S = 0
    for a in A:
        S += sum(a)

    dp = [[False]*(X[i]+1) for j in range(len(A)+1)]
    dp[0][0] = True

    for j in range(len(A)):
        for k in range(X[i]+1):
            a, b = A[j]
            if a <= k and dp[j][k-a]:
                dp[j+1][k] = True
            elif b <= k and dp[j][k-b]:
                dp[j+1][k] = True
        if not any(dp[j+1]):
            print('IMPOSSIBLE')
            exit()

    b = 0
    for j in range(X[i], -1, -1):
        if dp[len(A)][j]:
            b = j
            break

    return X[i], S - b

dfs(1)
print('POSSIBLE')
### BUGGY CODE ###

n = int(input())
list_A = list(map(int, input().split()))
list_A.sort()
max_value = max(list_A)
cnt = 0
hight = 1
hight_num = max_value
low = 1
low_num = 1
cnt = 0
ans = 0
b = 0
num = 1
for i in range(max_value):
    hight = hight_num - i
    low = low_num + i
    num = num*hight//low
    if list_A[cnt] == low_num + i:
        ans = max(ans, num)
        cnt += 1
        if ans == num:
            b = low_num + i

print(max_value, b)

### FIXED CODE ###

n = int(input())
list_A = list(map(int, input().split()))
list_A.sort()
max_value = max(list_A)
a = max_value/2
b = pow(10, 10)
c = 0
for num in list_A:
    if abs(a-num) < b:
        b = abs(a-num)
        c = num

print(max_value, c)
### BUGGY CODE ###

import sys

def solve():
    S = input()
    mod = 7 + 10 ** 9
    DP = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[0] == "?":
        for i in range(10): DP[0][i] = 1
    else: DP[0][int(S[0])] = 1

    for i in range(1, len(S)):
        if S[i] == "?":
            for j in range(13):
                for k in range(10):
                    DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                    DP[i][(j * 10 + k) % 13] %= mod
        else:
            k = int(S[i])
            for j in range(13):
                DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                DP[i][(j * 10 + k) % 13] %= mod
    print(DP[len(S) - 1][5])

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    S = input()
    mod = 7 + 10 ** 9
    DP = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[0] == "?":
        for i in range(10): DP[0][i] = 1
    else: DP[0][int(S[0])] = 1

    for i in range(1, len(S)):
        if S[i] == "?":
            for j in range(13):
                for k in range(10):
                    DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                    DP[i][(j * 10 + k) % 13] %= mod
        else:
            k = int(S[i])
            for j in range(13):
                DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                DP[i][(j * 10 + k) % 13] %= mod
    print(DP[len(S) - 1][5])

    return 0

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

N,K,S=map(int,input().split())
answers=[S]*K
answers_=[S+1]*(N-K)
answer=''
for k in range(K):
    answer+=str(answers[k])
    answer+=' '
for answer_ in answers_:
    answer+=str(answer_)
    answer+=' '
print(answer)


### FIXED CODE ###

N,K,S=map(int,input().split())
answers=[str(S)]*K
answers_=[str(S+1)]*(N-K)
a=' '.join(answers)
b=' '.join(answers_)
if K==0:
    if S==pow(10,9):
        answers_ = ['1'] * (N - K)
        b = ' '.join(answers_)
        c=b
    else:
        c=b
elif S==pow(10,9):
    answers_=['1']*(N-K)
    b = ' '.join(answers_)
    c=a+' '+b
else:
    c = a + ' ' + b
print(c)
### BUGGY CODE ###

a,b = map(int,input().split())
import math 
import fractions
def is_prime(n):
	if n == 1: return False

	for k in range(3, int(math.sqrt(n)) + 1,2):
		if n % k == 0:
			return False

	return True

gc = fractions.gcd(a,b)
if gc == 1:
	print(1)
	exit()

list1 = [1,2]

cout = 0 #1がfalse判定される
for i in range(3,gc+1,2):
	if is_prime(i):
		list1.append(i)
for i in range(len(list1)):
	if a % list1[i] == 0 and b % list1[i] == 0:
		cout += 1

print(cout)

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
"""素因数分解"""
def factrize(n):
	b = 2
	fct = []
	while b*b <= n:
		while n % b == 0:
			n //= b
			#もし素因数を重複させたくないならここを加えてfct.append(b)を消す
			
			if not b in fct:
				fct.append(b)
			
			
		b = b+1
	if n > 1:
		fct.append(n)
	return fct #リストが帰る

gc = fractions.gcd(a,b)

ans = factrize(gc)
print(len(ans)+1)
### BUGGY CODE ###

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

ans=1
for i in range(n):
  ans=ans*x[i]
if ans >10**18:
  print(-1)
else:
  print(ans)  
   

### FIXED CODE ###

n =int(input())
x = list(map(int, input().split()))
if x.count(0) !=0:
  print('0')
else:  
  ans=x[0]
  for i in range(1,n):
    ans=ans*x[i]
    if ans >10**18:
      print(-1)
      exit()
  print(ans)