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

# -*- coding: utf-8 -*-
import sys
buff_readline = sys.stdin.buffer.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


from collections import deque

def slv(N, P):
    M = N+2
    cost = [0] * M**2
    occupy = [True] * M**2
    for i in range(N):
        im = i*M + M + 1
        for j in range(N):
            cost[im+j] = min(i, j, N-i-1, N-j-1)

    ds = [-1, 1, -M, M]
    ans = 0
    for p in P:
        p -= 1
        x = p // N
        y = p % N
        p = x * M + y + M + 1
        ans += cost[p]
        occupy[p] = False
        s = [p]
        while s:
            pi = s.pop()
            for d in ds:
                ni = pi + d
                nc = cost[pi] + (1 if occupy[pi] else 0)
                if nc < cost[ni]:
                    s.append(ni)
                    cost[ni] = nc
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))

    # import random
    # N = 500
    # P = list(range(1, N**2+1))
    # random.shuffle(P)
    # print(slv(N, P))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
buff_readline = sys.stdin.buffer.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def slv(N, P):
    M = N+2
    cost = [0] * M**2
    occupy = [1] * M**2
    for i in range(N):
        im = i*M + M + 1
        for j in range(N):
            cost[im+j] = min(i, j, N-i-1, N-j-1)

    ds = [-1, 1, -M, M]
    ans = 0
    for p in P:
        p -= 1
        x = p // N
        y = p % N
        p = x * M + y + M + 1
        ans += cost[p]
        occupy[p] = 0
        s = []
        s.append(p)
        while s:
            pi = s.pop()
            for d in ds:
                ni = pi + d
                nc = cost[pi] + occupy[pi]
                if nc < cost[ni]:
                    cost[ni] = nc
                    s.append(ni)
    return ans


def main():
    N = read_int()
    P = read_int_n()
    print(slv(N, P))


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

import sys


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    adj = [[] for u in range(n)]
    for i in range(n - 1):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))

    q, k = read_int_list()
    k -= 1
    state = [0 for u in range(n)]
    d = [inf for u in range(n)]

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v, w in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + w
                Q.append(v)
                # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        x -= 1
        y -= 1
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()


### FIXED CODE ###

import sys
from collections import deque


# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * (n+1)
    q, k = read_int_list()

    # Q = [(k, 0, 0)]
    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        for v, w in adj[u]:
            if v != parent:
                Q.append((v, u, dist+w))
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()
### BUGGY CODE ###

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

A_sum=[0,A[0]]
B_sum=[0,B[0]]
for i in range(1,N):
    A_sum.append(A_sum[i]+A[i])
for i in range(1,M):
    B_sum.append(B_sum[i]+B[i])

b_read=0
ans=0
for i in range(N,-1,-1):
    for j in range(b_read,M+1):
        if A_sum[i]+B_sum[j]<=K:
            ans=max(ans,i+j)
            b_read=j
print(ans)


### FIXED CODE ###

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

used=0
a_read=0
for i in range(N):
    if used+A[i]>K:
        break
    else:
        used+=A[i]
        a_read+=1

b_read=0
for i in range(M):
    if used+B[i]>K:
        break
    else:
        used+=B[i]
        b_read+=1
ans=a_read+b_read
tmp=ans

for i in range(a_read):
    if b_read==M:
        break
    used-=A[a_read-1]
    a_read-=1
    tmp-=1
    while True:
        if b_read>=M:
            break
        if used+B[b_read]<=K:
            b_read+=1
            used+=B[b_read-1]
            tmp+=1
        else:
            break
    ans=max(ans,tmp)

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

N, *A = map(int, open(0).read().split())
MOD = 1_000_000_007
ans = 0
for i in range(61):
    p, q, = 0, 0
    for a in A:
        if a >> i & 1:
            p += 1
        else:
            q += 1
    ans += pow(2, i, MOD) * p * q
    ans %= MOD
print(ans)

### FIXED CODE ###

import numpy as np


def solve():
    ans = 0
    mask = 1
    for i in range(60):
        one_cnt = np.sum(A >> i & 1)
        tmp = one_cnt * (N - one_cnt)
        tmp %= MOD
        ans += tmp * mask
        ans %= MOD
        mask <<= 1
        mask %= MOD
    return ans


N, *A = map(int, open(0).read().split())
A = np.array(A, dtype=np.int64)
MOD = 1_000_000_007
print(solve())
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N = int(f_i.readline())
    A = list(map(int, f_i.readline().split()))
    A_max = max(A)
    
    ans = 0
    b = 1
    while A_max:
        next_A = []
        
        zero_cnt = 0
        one_cnt = 0
        
        for A_i in A:
            if A_i & 1:
                one_cnt += 1
            else:
                zero_cnt += 1
            next_A.append(A_i >> 1)
        
        ans += b * one_cnt * zero_cnt
        ans %= mod
        
        b *= 2
        A_max >>= 1
        A = next_A[:]
        
    print(ans)

solve()

### FIXED CODE ###

def solve():
    import numpy as np
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N = int(f_i.readline())
    A = np.array(f_i.readline().split(), dtype=np.int64)
    
    ans = 0
    for i in range(60):
        cnt = np.count_nonzero((A >> i) & 1)
        ans += (1 << i) * cnt * (N - cnt)
    
    print(ans % mod)

solve()
### BUGGY CODE ###

import numpy as np

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

L = np.array(sorted(L, reverse=True))

ans = 0

for n in range(0,N-2):
    if L[n] > 2* L[n+1]:
        pass
    else:
        for o in range(n+1,N-1):
            ans += np.sum(L[o+1:]>L[n]+-L[o])
                
print(int(ans))

### FIXED CODE ###

import bisect

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

count = 0
for n in range(N-2):
    for m in range(n+1,N-1):
        count += bisect.bisect_left(L,L[m]+L[n]) -m-1

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

n=int(input())
x=input()
t=int(x,2)
from functools import *
@lru_cache(None)
def popcount(x):
  if x==0: return 0
  return popcount(x%bin(x).count('1'))+1
for i in range(n):
  s=t+2**(n-i-1)*(1-int(x[i])*2)
  print(popcount(s))

### FIXED CODE ###

n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)
### BUGGY CODE ###

'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N, M = map(int, input().split())
W = [0] * (N +2)
V = [0] * (N +2)
for i in range(0, N):
    W[i],V[i] = map(int, input().split())

for i in range(0, N):
    for j in range(1, M+1):
        if (j - W[i] >= 0):
            dp[(i+1,j)] = max(dp[(i+1,j)], dp[(i,j-W[i])] + V[i])
        dp[(i+1,j)] = max(dp[(i+1,j)], dp[(i,j)])

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[(i,j)])
    print('')
'''

print(max(dp.values()))


### FIXED CODE ###

N,M = map(int,input().split())
dp = [[0]*(M+1) for _ in range(N+1)]

for i in range(1, N+1):
    W,V = map(int,input().split())
    for j in range(W):
        dp[i][j] = dp[i-1][j]
    for j in range(M-W+1):
        dp[i][j+W] = max(dp[i-1][j+W],dp[i-1][j]+V)

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

# -*- coding: utf-8 -*-
import math

MOD = 10 ** 9 + 7

def main():
    N = int(input())
    S = input().strip()

    if S[0] == 'W' or S[-1] == 'W':
        print(0)
        return

    Sp = ''
    Dc = True
    LRsub = 0
    Pattern = 1
    for Sc in S:
        Dc = not Dc if Sc == Sp else Dc
        Sp = Sc
        Pattern *= LRsub if not Dc else 1
        LRsub += 1 if Dc else -1

    if LRsub == 0:
        Pattern *= math.factorial(N)
        Pattern = Pattern % MOD
        print(Pattern)
    else:
        print(0)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

MOD = 10 ** 9 + 7

N = int(input())
S = list(map(lambda x: int(x == "W"),input()))
if S[0] or S[-1]:
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i in range(1,N*2):
    Sc = S[i]
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern = (Pattern * LRsub) % MOD
    LRsub += Dc

if LRsub == 0:
    for i in range(2,N+1):
        Pattern = (Pattern * i) % MOD
    print(Pattern)
else:
    print(0)
### BUGGY CODE ###

s = input()
li = list(s)

ans = 0
tmp = 0

while "ABC" in s:
    for i in range(len(li)):
        if tmp == 0:
            if li[i] == "A":
                tmp += 1
                continue
            else:
                continue
        elif tmp == 1:
            if li[i] == "B":
                tmp += 1
                continue
            elif li[i] == "A":
                continue
            else:
                tmp = 0
                continue
        elif tmp == 2:
            if li[i] == "C":
                li[i] = "A"
                li[i-1] = "C"
                li[i-2] = "B"
                ans += 1
                s = "".join(li)
                tmp = 0
                break
            else:
                continue
print(ans)

### FIXED CODE ###

s = input()
 
ans = 0
s = s.replace("BC","D")
cnt_A = 0
 

for i in s:
    if i == "A":
        cnt_A += 1
    elif i == "D":
        ans += cnt_A
    else:
        cnt_A = 0

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

#!/usr/bin
# -*- coding="utf-8" -*-
 
n = int(input())
a = input().split()
b = ""
if n == 1:
  b = a[0] + " "
else:
  for i in range(n-1, 0, -2):
    b = b + a[i] + " "
  for i in range(0, n-1, 2):
    b = b + a[i] + " "
    if n % 2 == 1 and i ==0:
      i = i + 1
      b = b + a[i] + " "
print(b[:-1])

### FIXED CODE ###

#!/usr/bin
# -*- coding="utf-8" -*-
 
n = int(input())
a = input().split()
b = []
if n == 1:
  b.append(a[0])
else:
  for i in range(n-1, 0, -2):
    b.append(a[i])
  b.append(a[0])
  if n % 2 == 1:
    for i in range(1, n-1, 2):
      b.append(a[i])
  else:
    for i in range(2, n-1, 2):
      b.append(a[i])
print(' '.join(b))
### BUGGY CODE ###


def solve(A, ms, flags):
	while 0 in ms:
		i = ms.index(0)
		flags[i]=True
		ms[i]=-1

	if len(A)==0:
		return flags
	else:
		use = solve(A[1:], list(map(lambda x:x-A[0], ms)), flags)
		no_use = solve(A[1:], ms, flags)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	for flag in solve(A, m, flags):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

### FIXED CODE ###

def power_set(A, s):
	if len(A) == 0:
		return {s}
	else:
		return power_set(A[1:], s) | power_set(A[1:], s+A[0])

def main():
	n = int(input())
	A = input()
	#print(n)
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	ms = list(map(int, m.split()))
	powerset = power_set(A, 0)
	
	for m in ms:
		if m in powerset:
			print('yes')
		else:
			print('no')

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

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
ans=[]
n=int(raw_input())
for _ in range(n):
    a=sys.stdin.readline().split()
    chk=a[0]
    if chk=='insert': ans.insert(0,a[1])
    elif chk=='deleteFirst': ans.pop(0)
    elif chk=='deleteLast': ans.pop()
#    else: ans.remove(str(a[1]))
    else:
        if a[1] in ans:
            ans.remove(a[1])
#    print ans
print ' '.join(ans)

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

S = list(input())
K = int(input())
sub = set(S)
for step in range(2, len(S) + 1):
    for i in range(0, len(S) - step + 1):
        st = ''
        for s in S[i:i + step]:
            st += s
        sub.add(st)
substring = list(sub)
substring.sort()
print(substring[K - 1])


### FIXED CODE ###

S = input()
K = int(input())
sub = set(S)
for step in range(2, 6):
    for i in range(0, len(S) - step + 1):
        sub.add(S[i:i+step])
print(sorted(sub)[K - 1])
### BUGGY CODE ###

h, n = list(map(int, input().split()))
a = list(map(int, input().split()))
i = 0
while (i < n):
  if(a[i] <= 0):
    print("Yes")
print("No")

### FIXED CODE ###

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

if h > sum(a):
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
for i in range(1, len(S) + 1):
    s = int(S[-i:])
    div.append(s % 2019)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += combinations_count(l, 2)
print(ans)


### FIXED CODE ###

from collections import Counter


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    # s += int(S[i]) * ((10 ** (len(S) - 1 - i)) % 2019)
    # s %= 2019
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    kurai %= 2019
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())

#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val):
    for i in range(N):
        seg[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1], seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

num =2**(N-1).bit_length()
ide_ele = set()
seg=[ide_ele]*2*num
init([set([c]) for c in Cs])
for _ in range(Q):
    l, r = mapint()
    print(len(query(l-1, r)))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
    l, r = mapint()
    LR.append((l, r, i))
LR.sort(key=lambda x:x[1])
A = [0]*N

def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

def sums(A,a):#k番目までの和
    x = a
    S = 0
    while x != 0:
        S += A[x-1]
        x -= x&(-x)
    return S

ans = [0]*Q
idx = 0
dic = {}
for i in range(N):
    c = Cs[i]
    if c not in dic:
        dic[c] = i+1
        add(A, i+1, 1)
    else:
        past = dic[c]
        dic[c] = i+1
        add(A, past, -1)
        add(A, i+1, 1)
    while idx<Q and LR[idx][1]<=i+1:
        l, r, ans_idx = LR[idx]
        ans[ans_idx] = sums(A, r)-sums(A, l-1)
        idx += 1
for a in ans:
    print(a)
### BUGGY CODE ###

n = int(input())
a=input().split()
a_int = [int(i) for i in a]

ans=[0]*n

for i in range(n-1):
    s=str(i+1)
    ans[i]=a.count(s)

for m in range(n):
    print(str(ans[m]))

### FIXED CODE ###

n = int(input())
a=input().split()

ans=[0]*n

for i in range(n-1):
    ans[int(a[i])-1]+=1
    
print(*ans, sep='\n')
### BUGGY CODE ###

n=int(input())
A=list(input().split())
B=[]
import queue
q=queue.Queue()
for a in A:q.put(a)
while not q.empty():
    B.append(q.get())
    B=B[::-1]
print(" ".join(B))

### FIXED CODE ###

n = int(input())
a = list(input().split())
a1 = ['']*(n//2 + n%2)
a2 = ['']*(n//2)

for i in range(n):
	if i%2 == 0:
		a1[i//2] = a[i]
	else:
		a2[-i//2] = a[i]

if n%2 != 0 and n != 1:
	ans = ' '.join(a1[::-1]) + ' ' + ' '.join(a2[::-1])
elif n%2 == 0:
	ans = ' '.join(a2) + ' ' + ' '.join(a1)
else:
	ans = a[0]
print(ans)
### BUGGY CODE ###

n = int(input())
a = input().split()
alist = set()
adic = {}
for i in a:
    if int(i) in alist:
        adic[int(i)] = adic[int(i)] + 1
    else:
        alist.add(int(i))
        adic[int(i)] = 1

q = int(input())
ans = []

for i in range(q):
    s = input().split()
    b = int(s[0])
    c = int(s[1])
    su = 0
    if b in alist:
        if not(c in alist):
            adic[c] = 0
            alist.add(c)
        adic[c] = adic[c] + adic[b]
        adic[b] = 0
    for j in adic:
        su += j * adic[j]
    ans.append(su)
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

n = int(input())
a = input().split()
alist = set()
adic = {}
su = 0

for i in a:
    su += int(i)
    if int(i) in alist:
        adic[int(i)] = adic[int(i)] + 1
    else:
        alist.add(int(i))
        adic[int(i)] = 1

q = int(input())
ans = []

for i in range(q):
    s = input().split()
    b = int(s[0])
    c = int(s[1])
    if b in alist:
        if not(c in alist):
            adic[c] = 0
            alist.add(c)
        adic[c] = adic[c] + adic[b]
        su = su + (c * adic[b]) - (b * adic[b])
        adic[b] = 0

    ans.append(su)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import itertools


input()
s = list(input())
r =[]
g =[]
b =[]
n= len(s)
ans =0
for i in range(n):
    if s[i]== "R":
        r.append(i+1)
    elif s[i]== "G":
        g.append(i+1)
    else:
        b.append(i+1)

for ss in itertools.product(r,g,b):
    sss =sorted(ss)
    if sss[2] + sss[0] != 2*sss[1]:
        ans +=1

print(ans)

### FIXED CODE ###

import sys
import math
import itertools
from functools import reduce
from functools import lru_cache


# \n
def input():
    return sys.stdin.readline().rstrip()

def main():

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

    R=[0]*N
    G=[0]*N
    B=[0]*N
    r=0
    g  =0
    b=0
    count =0
    for i in range(N-1,-1,-1):
        if S[i] =="R":
            r+=1
        elif S[i] =="G":
            g+=1
        else:
            b+=1
        R[i]=r
        G[i]=g
        B[i]=b

    count =0
    for i in range(N):



        for j in range(i+1,N):
            SE = set(["R", "G", "B"])
            I = S[i]
            SE.remove(I)
            J =S[j]
            if I==J:
                continue
            SE.remove(J)
            if "G" in SE:
                count+=G[j]
                if j+j-i <N and S[j+j-i] =="G":
                    count -=1

            elif "R" in SE:
                count+=R[j]
                if j+j-i <N and S[j+j-i] =="R":
                    count -=1
            else:
                count+=B[j]
                if j+j-i <N and S[j+j-i] =="B":
                    count -=1



    print(count)


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

def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  # 13で割ったあまりを考えている
    # editorialでは2次元配列を考えているが、こうするとメモリを節約できる
    dp = [0] * modulo  # dp[k]: 13で割ったあまりがkの場合の数
    dp[0] = 1  # 初期値を0とすると、これを13で割ったあまりは0

    # Sを下の桁から見ていく
    # ex. 1?2?3: 0 - 3 - ?3 - 2?3 - ...

    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  # ?に対し1桁の数字のすべてを試す
                for j in range(modulo):
                    # k * mul: mulの位がk、j: それより下の桁についてのあまり
                    # なので、このような遷移
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        # a*10**d % modulo = (a*(10**d % modulo)) % modulo なので、先に剰余を取る
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))

### FIXED CODE ###

def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  # 13で割ったあまりを考えている
    # editorialでは2次元配列を考えているが、こうするとメモリを節約できる
    dp = [0] * modulo  # dp[k]: 13で割ったあまりがkの場合の数
    dp[0] = 1  # 初期値を0とすると、これを13で割ったあまりは0

    # Sを下の桁から見ていく
    # ex. 1?2?3: 0 - 3 - ?3 - 2?3 - ...
    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  # ?に対し1桁の数字のすべてを試す
                for j in range(modulo):
                    # k * mul: mulの位がk、j: それより下の桁についてのあまり
                    # なので、このような遷移
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        # a*10**d % modulo = (a*(10**d % modulo)) % modulo なので、先に剰余を取る
        # (多倍長整数を持ち出さなくてよくなる)
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))