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

N = int(input())
for i in range(1,N+1):
  ans = 0
  for x in range(1,i):
    for y in range(1,i):
      for z in range(1,i):
        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
          ans += 1
  print(ans)


### FIXED CODE ###

import math

N = int(input())
ans = [0 for _ in range(10050)]

# for i in range(1,N+1):
for x in range(1,math.ceil(math.sqrt(N))):
  for y in range(1,math.ceil(math.sqrt(N))):
    for z in range(1,math.ceil(math.sqrt(N))):
      v = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if v < 10050:
        ans[v] += 1

for i in range(N):
  print(ans[i+1])
### BUGGY CODE ###

n=int(input())
l=[int(input())]

for i in range(n-1):
    a=int(input())
    f=True
    for i in range(len(l)):
        if l[i]<a:
            l[i]=a
            f=False
            break
    if f:
        l.append(a)
print(len(l))


### FIXED CODE ###

import sys,bisect
input=sys.stdin.readline
n=int(input())

a=[int(input()) for _ in range(n)]
a.reverse()

dp=[float("inf")]*(n+1)
for b in a:
    idx=bisect.bisect_right(dp,b)
    dp[idx]=b

ans=bisect.bisect_left(dp,float("inf"))

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

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
BC = [0] * M
for i in range(M):
    BC = list(map(int,input().split()))
    i = 0
    while i < BC[0] and BC[1] > A[0]:
        heapq.heappop(A)
        heapq.heappush(A,BC[1])
        i += 1

print(sum(A))


### FIXED CODE ###

import heapq

N,M = (int(i) for i in input().split())
A = list(map(int,input().split()))
A.sort()
D = []
len = 0
BC = [0] * M

for i in range(M):
    BC[i] = list(map(int,input().split()))
BC.sort(key = lambda x:x[1],reverse = True)
for i in range(M):
    D.extend([BC[i][1]] * BC[i][0])
    len += BC[i][0]
    if len > N:
        break
cnt = min(N,len)
for i in range(cnt):
    if A[0] < D[i]:
        heapq.heapreplace(A,D[i])
    else:
        break
print(sum(A))
### BUGGY CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(sum(list(map(reverse, tail))))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

from numpy import array
diff = array(sum_red) - array(sum_blue)
print(max(diff))


### FIXED CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))
### BUGGY CODE ###

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

x = 1
for i in range(N):
    x = x * l[i]

if x > 10 ** 18:
    x = -1
    print(x)
else:
    print(x)

### FIXED CODE ###

import sys

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

def solve():
    if 0 in l:
        return (0)
        sys.exit()

    x = 1
    for i in range(N):
        x = x * l[i]
        if x > (1000000000000000000):
            x = -1
            break

    return str(x)

print(solve())
### BUGGY CODE ###

#!/usr/bin/env python

import sys
import heapq

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(-bi)
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        if not cur: cur= ref
        else: cur+= ref
    #
    if not cur: continue
    heapq.heapify(cur)
    tot+= heapq.heappop(cur)
#
print( -tot )


### FIXED CODE ###

#!/usr/bin/env python

import sys

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(bi)
#
for i in range(m):
    if baito[i]: baito[i].sort()
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        if not cur:
            cur= ref
        else:
            if ref[-1]<=cur[0]:
                cur= ref + cur
            elif cur[-1]<=ref[0]:
                cur= cur + ref
            else:
                cur+= ref
                cur.sort()
    #
    if not cur: continue
    tot+= cur.pop()
#
print( tot )
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, P = LI()
S = input()

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[N-1 - i]) % P == 0:
            ans += N-i
    print(ans)
else:
    A = [0] * (N+1)
    for i in range(N):
        A[i+1] = (A[i] + int(S[N-1 - i]) * (10**i)) % P

    c = collections.Counter(A)
    ans = 0
    for k, v in c.items():
        ans += v * (v-1) // 2
    
    print(ans)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, P = LI()
S = input()

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[N-1 - i]) % P == 0:
            ans += N-i
    print(ans)
else:
    A = [0] * (N+1)
    for i in range(N):
        A[i+1] = (A[i] + int(S[N-1 - i]) * pow(10, i, P)) % P

    c = collections.Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v-1) // 2
    
    print(ans)
### BUGGY CODE ###

n = int(input())
SET = set()
dict = {}
ans = 0
for i in range(n):
    s = list(input())
    s.sort()
    s = str(s)
    if s in SET:
        if s in dict:
            dict[s] += 1
        else:
            dict[s] = 1
    SET.add(s)

for i in dict.values():
    ans += i * (i + 1) // 2
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

n = int(input())
SET = set()
dict = {}
ans = 0
for i in range(n):
    s = list(input())
    s.sort()
    s = str(s)
    if s in SET:
        if s in dict:
            dict[s] += 1
        else:
            dict[s] = 1
    SET.add(s)

for i in dict.values():
    ans += i * (i + 1) // 2
print(ans)
### BUGGY CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

X,Y,Z,K=rl()
A=rl()
B=rl()
C=rl()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
X=[]
for a,b,c in zip(A,B,C):
    X.append([a,0])
    X.append([b,1])
    X.append([c,2])
X.sort(reverse=True)

ca=0
cb=0
cc=0
xl = 0
for i in range(len(X)):
    _,a = X[i]
    if a == 0:
        ca += 1
    elif a == 1:
        cb += 1
    else:
        cc += 1 
    if ca*cb*cc>=K:
        xl=i
Ax=[]
Bx=[]
Cx=[]
for x,a in X:
    if a == 0:
        Ax.append(x)
    elif a == 1:
        Bx.append(x)
    else:
        Cx.append(x)

ans = []
import itertools
for a,b,c in itertools.product(Ax,Bx,Cx):
    ans.append(a+b+c)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

X,Y,Z,K=rl()
A=rl()
B=rl()
C=rl()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
ans = []
for a in range(1,X+1):
    for b in range(1,Y+1):
        for c in range(1,Z+1):
            if a*b*c<=K:
                ans.append(A[a-1]+B[b-1]+C[c-1])
            else:
                break
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

from itertools import product
from math import gcd
from functools import reduce

K = int(input())

p = product(range(1, K + 1), repeat=3)
print(sum([reduce(gcd, i) for i in p]))


### FIXED CODE ###

from itertools import product
from math import gcd
from functools import reduce

K = int(input())

p = product(range(1, K + 1), repeat=3)
print(sum([reduce(gcd, i) for i in p]))
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
b_list = []

for a_i in a_list:
  b_list.append(a_i)
  b_list = b_list[::-1]
  
print(*b_list)

### FIXED CODE ###

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

print(*a_list[::-2], end = ' ')
print(*a_list[n%2::2])
### BUGGY CODE ###

N = int(input())
list0 = []
list1 = []
for i in range(N):
  x = input()
  if x in list0:
    t = list0.index(x)
    list1[t] += 1
  else:
    list0.append(x)
    list1.append(1)
l = len(list0)
counter = 0
list2 = []
for i in range(l):
  if list1[i] > counter:
    counter = list1[i]
for i in range(l):
  if list1[i] == counter:
    list2.append(list0[i])
list2 = sorted(list2)
l_2 = len(list2)
for i in range(l_2):
  print(list2[i])

### FIXED CODE ###

N = int(input())
list0 = {}
for i in range(N):
  x = input()
  if x in list0:
    list0[x] = list0[x] + 1
  else:
    list0[x] = 1
m = max(list0.values())
k_m = [key for key in list0 if list0[key] == m]
k_m.sort()
for i in range(len(k_m)):
  print(k_m[i])
### BUGGY CODE ###

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,[loop,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999999 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

print(ans)

### FIXED CODE ###

from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, K = NMI()
    A = NLI()

    for k in range(min(K, 42)):
        tmp = [0] * (N+1)
        for i, a in enumerate(A):
            tmp[max(0, i-a)] += 1
            tmp[min(N, i+a+1)] -= 1
        cum = [0] * (N+1)
        for i, t in enumerate(tmp):
            if i == 0:
                cum[0] = t
                continue
            cum[i] = cum[i-1] + t
        A = cum[:-1]
    print(" ".join(map(str, A)))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, K = NMI()
    A = NLI()

    for k in range(min(K, 42)):
        tmp = [0] * (N+1)
        for i, a in enumerate(A):
            tmp[max(0, i-a)] += 1
            tmp[min(N, i+a+1)] -= 1
        cum = [0] * (N+1)
        for i, t in enumerate(tmp):
            if i == 0:
                cum[0] = t
                continue
            cum[i] = cum[i-1] + t
        A = cum[:-1]
    print(" ".join(map(str, A)))


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

from numba import njit


@njit#(fastmath=True)
def fact(x):
    i = 1
    ret = set()
    while i * i <= x:
        if x % i == 0:
            ret.add(i)
            ret.add(x // i)
        i += 1

    return ret


def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


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

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    l_tmp = 0
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = l_tmp = l_tmp + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    r_tmp = 0
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = r_tmp = r_tmp + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)


### FIXED CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().split()))
cnt = 0

for i in range(0, N):
    flag = 0
    for j in range(0, i):
        if array[i] > array[j]:
            flag = 1
            break
    if not flag == 1:
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
cnt = 1
minv = array[0]

for i in range(1, N):
    if minv > array[i]:
        minv = array[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

input1 = input()
input2 = input()
N = int(input1)
list_an = input2.split()
list_an = list(map(int,list_an))

list_an_sub = []


total = 0

def check():
    check_total = 0
    for i in range(len(list_an)):
        if list_an[i] == i+1:
            check_total += 0
        else:
            check_total += 1
    if check_total == 0:
        return 1
    if check_total == 0:
        return 0
                

while check() is None:
    for i in range(len(list_an)):
        if i <= len(list_an):
            if list_an[i] == i+1:
                total += 0
            else:
                del(list_an[i])
                total += 1
                break
        else:
            break
   
if list_an == []:
    print(-1)
else:
    print(total)

### FIXED CODE ###

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

checkNum = 1
howMany = 0

for j in range(N):
    if line[j] == checkNum:
        checkNum += 1
    else:
        howMany += 1

# print(line)
# print(checkNum)
# print(howMany)

if checkNum == 1:
    print("-1")
else:
    print(howMany)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    for i in range(len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(10 ** i * j + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        else:
            if i == 0:
                dp[1][s[-i-1] % 13] += 1
            else:
                for k in range(13):
                    dp[1][(10 ** i * s[-i-1] + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


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

# いきぬきreview　忘れた問題
# gluttony
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
F.sort()
A.sort(reverse=True)


def func(X):
    s = 0
    for i in range(N):
        a, f = A[i], F[i]
        s += max(0, a-X//f)
    return s <= K


R = 10**12
L = -1
while R-L > 1:
    m = (R+L)//2
    if func(m):
        R = m
    else:
        L = m
print(R)

### FIXED CODE ###

# いきぬきreview　忘れた問題
# gluttony
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
F.sort()
A.sort(reverse=True)


def func(X):
    s = 0
    for i in range(N):
        a, f = A[i], F[i]
        s += max(0, a-X//f)
    return s <= K


R = 10**12
L = -1
while R-L > 1:
    m = (R+L)//2
    if func(m):
        R = m
    else:
        L = m
print(R)
### BUGGY CODE ###

import itertools
import numpy as np

def solve(n, x, y):
    total, num = 0, 0
    for p in itertools.permutations(range(n)):
        num += 1
        for i in range(n-1):
            total += np.linalg.norm([x[p[i+1]]-x[p[i]],y[p[i+1]]-y[p[i]]])
    return total / num

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

### FIXED CODE ###

import itertools
import numpy as np

def solve(n, x, y):
    total, num = 0, 0
    x, y = np.asarray(x), np.asarray(y)
    for p in itertools.permutations(range(n)):
        num += 1
        p = np.array(p, dtype=int)
        dx = x[p[1:]] - x[p[:-1]]
        dy = y[p[1:]] - y[p[:-1]]
        total += np.sum(np.sqrt(dx**2 + dy**2))
    return total / num

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))