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

import sys 
import collections as cl

N=int(input())
A=list(map(int,sys.stdin.readline().split()))
c=cl.Counter(A)
NumberList=[x for x in c.values()]
LengthOfNumberList=len(NumberList)
FormulaList=[sum([min(NumberList[i],x) for i in range(LengthOfNumberList)])/x for x in range(1,N+1)]
FormulaList.sort(reverse=True)

pin=N-1
for K in range(1,N+1):
    while pin>=0 and K>FormulaList[pin]:
        pin-=1
    print(pin+1)


### FIXED CODE ###

import sys 
import collections as cl


N=int(input())
A=list(map(int,sys.stdin.readline().split()))
c=cl.Counter(A)
NumberTupleList=c.most_common()
NumberList=[x[1] for x in NumberTupleList[::-1]]
LengthOfNumberList=len(NumberList)
FormulaList=[0 for i in range(N)]
flag=0
S=sum(NumberList)
for x in range(1,N+1):
    while flag<LengthOfNumberList and NumberList[flag]<=x:
        flag+=1
    if flag<LengthOfNumberList:
        FormulaList[x-1]=(sum(NumberList[:flag])+x*(LengthOfNumberList-flag))/x
    else:
        FormulaList[x-1]=S/x
pin=N-1
for K in range(1,N+1):
    while pin>=0 and K>FormulaList[pin]:
        pin-=1
    print(pin+1)
### BUGGY CODE ###

N, K = map(int, input().split())
tmp = input().split(' ')
A = []
for i in range(N):
    A = A + [int(tmp[i])]
Z = [N]*N
while K > 0 and A != Z:
    K = K - 1
    B = [0]*N
    for i in range(N):
        l =  max(0,i-A[i])
        r =  min(N-1,i+A[i])
        B[l] = B[l]+1
        if r+1 < N:
            B[r+1] = B[r+1]-1

    A[0] = B[0]
    for i in range(1,N):
        A[i]=A[i-1]+B[i]

print(' '.join(map(str,A)))

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

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

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
for combi in combinations(l_ls, 2):
    bisect.insort_left(_sum_ls, combi[0] + combi[1])
len_sum_ls = len(_sum_ls)
for l in l_ls:
    ind = bisect.bisect_right(_sum_ls, l)
    cnt += ind
print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
### BUGGY CODE ###

S = input()

c = [0] * 2019
c[0] = 1
for i in range(len(S)):
    c[int(S[i:])%2019] += 1

ans = 0
for m in c:
    ans += m * (m - 1) / 2

print(int(ans)) 

### FIXED CODE ###

S = input()

mod = [0] * 2019
mod[0] = 1
digit = 1
temp = 0
 
for i in S[::-1]:
    temp = (temp + digit * int(i)) % 2019
    mod[temp] += 1
    digit = (digit * 10) % 2019

ans = 0
for m in mod:
    ans += m * (m - 1) // 2

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

import math

n = int(input())
aL = list(map(int, input().split(" ")))

ans = 0
for s in range(n):
    for e in range(s + 1, n):
        if e - s == aL[s] + aL[e]:
            ans += 1

print(ans)

### FIXED CODE ###

import math

n = int(input())
aL = list(map(int, input().split(" ")))

d1 = {}
d2 = {}
for i in range(n):
    d1i = i - aL[i]
    d2i = i + aL[i]

    if d1i in d1:
        d1[d1i] += 1
    else:
        d1[d1i] = 1

    if d2i in d2:
        d2[d2i] += 1
    else:
        d2[d2i] = 1

ans = 0
for k, v in d2.items():
    if k in d1:
        ans += v * d1[k]

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

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    

    ans = float("inf")
    
    if N == 2:
        print(abs(A[0] - A[1]))
        sys.exit()
    
    for i in range(1, N-1):
        sunuke = 0
        araiguma = 0
        
        for j, val in enumerate(A):
            if i >= j:
                sunuke += val
            else:
                araiguma += val
                
        tmp = abs(sunuke-araiguma)
        if ans > tmp:
            ans = tmp
            
    print(ans)
        
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = float("inf")
    
    if N == 2:
        print(abs(A[0] - A[1]))
        sys.exit()
    
    a_sp = []
    for i, val in enumerate(A):
        if i == 0:
            a_sp.append(val)
            continue
        tmp = val + a_sp[i-1]
        a_sp.append(tmp)
        
    for i, val in enumerate(a_sp):
        if i == (len(a_sp)-1):
            break
            
        tmp = abs(val - ((a_sp[-1])-val))
        
        if tmp < ans:
            ans = tmp
            
    print(ans)
        
if __name__ == "__main__":
	main()
### BUGGY CODE ###

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

result = 0
for i in range(len(As)-1):
    result+=As[i]*sum(As[i+1:])

print(result%(1*10**9+7))


### FIXED CODE ###

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

result = 0
before_sum = sum(As)
for i in range(N-1):
    before_sum-=As[i]
    result+=As[i]*(before_sum)
print(result%(1*10**9+7))
### BUGGY CODE ###

n = int(input())
a = [0] + [int(input()) for _ in range(n)]

pushed = [1]
button = 1

while button != 2:
    if a[button] in pushed:
        print(-1)
        break
    pushed.append(a[button])
    button = a[button]
else:
    print(len(pushed) - 1)

### FIXED CODE ###

import sys

n = int(input())
a = [0] + [int(sys.stdin.readline()) for _ in range(n)]

button = 1
count = 0

for _ in range(n):
    if button == 2:
        print(count)
        break
    button = a[button]
    count += 1

if count == n:
    print(-1)
### BUGGY CODE ###

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



for i in range(N):
    ans_L = []
    tmp_L = copy.deepcopy(L)
    tmp_L.pop(i)
    
#     print(tmp_L)
    for j in range(2**(N-1)):
        count = 0
        tmp2_L = []
        for k in range(N-1):
            if j>>k&1 == 1:
                count += 1
                tmp2_L.append(tmp_L[k])
        if count==2:
            ans_L.append(tmp2_L)
#     print(ans_L)
    ans = 0
    for x in ans_L:
        if x[0]==x[1]:
            ans += 1
    print(ans)

### FIXED CODE ###

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

C = collections.Counter(L)
ans = 0
for i in C.items():
    ans += int((i[1]*(i[1]-1))/2)
        
for i in range(N):
    del_target = L[i]
    print(ans - (C[del_target]-1))
### BUGGY CODE ###

import itertools
N = int(input())
arr = list(map(int, input().split()))
for i in itertools.permutations(arr):
    flg = True
    for k in range(N):
        if i[k-2] ^ i[k] != i[k-1]:
            flg = False
            break
    if flg:
        print('Yes')
        exit()
print('No')

### FIXED CODE ###

N = int(input())
arr = list(map(int, input().split()))
cnt = arr.count(0)
if cnt == N:
    print('Yes')
    exit()
if N % 3 != 0:
    print('No')
    exit()
if cnt == N//3 and len(set(arr)) == 2:
    print('Yes')
    exit()
from collections import defaultdict
d = defaultdict(int)
for i in arr:
    d[i] += 1
if len(d) != 3:
    print('No')
    exit()
check = []
for key in d.keys():
    check.append(key)
if d[check[0]] == d[check[1]] and d[check[1]] == d[check[2]] and d[check[2]] == d[check[0]] and check[0]^check[1]^check[2] == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import Counter
N=int(input())
C = Counter(map(int, input().split()))
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
print(dp[C[3]][C[2]][C[1]])

### FIXED CODE ###

N=int(input())
C=[0]*4
for i in map(int, input().split()):
    if i==1:
        C[1]+=1
    elif i==2:
        C[2]+=1
    else:
        C[3]+=1
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
print(dp[C[3]][C[2]][C[1]])
### BUGGY CODE ###

N, K = map(int, input().strip().split())
count = set()
for a in range(1, N+1):
    if a % K == 0:
        for b in range(K, N + 1, K):
            for c in range(K, N + 1, K):
                count.add((a, b, c))
    else:
        start = K - a % K
        for b in range(start, N + 1, K):
            for c in range(start, N + 1, K):
                if (b + c) % K == 0:
                    count.add((a, b, c))
print(len(count))

### FIXED CODE ###

N, K = map(int, input().strip().split())
result = 0
num = N // K
result += num
if num == 2:
    result += num * (num - 1) * 3
elif num > 2:
    result += num * (num - 1) * 3
    result += num * (num - 1) * (num - 2)


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    num = (N - start) // K + 1
    result += num
    if num == 2:
        result += num * (num - 1) * 3
    elif num > 2:
        result += num * (num - 1) * 3
        result += num * (num - 1) * (num - 2)
    print(result)
### BUGGY CODE ###

mod=10**9+7
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
xl=0
yl=0
for i in range(n-1):
  r=i+1
  while r<n:
    xl=(xl+x[r]-x[i])%mod
    r+=1
for i in range(m-1):
  u=i+1
  while u<m:
    yl=(yl+y[u]-y[i])%mod
    u+=1
print(xl*yl%mod)

### FIXED CODE ###

mod=10**9+7
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
xl=0
xt=0
yl=0
yt=0
for i in range(n-1):
  if i==0:
    for j in range(1,n):
      xt+=x[j]-x[i]
    xl=xt
  else:
    xt-=(x[i]-x[i-1])*(n-i)
    xl=(xl+xt)%mod
for i in range(m-1):
  if i==0:
    for j in range(1,m):
      yt+=y[j]-y[i]
    yl=yt
  else:
    yt-=(y[i]-y[i-1])*(m-i)
    yl=(yl+yt)%mod
print(xl*yl%mod)
### BUGGY CODE ###

K, S = map(int, input().split())

ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                # print([x,y,z])
                ans += 1

print(ans)

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0

for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0<=z and z<=K:
            # print([x,y,z])
            ans += 1

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

def func(i, j):
  il = len(str(i))
  jl = len(str(j))
  if il > jl:
    return il
  return jl

n = int(input())
min = len(str(10**10))
for i in range(1, n+1):
  if n % i == 0:
    if i > n/i:
      break
    fr = func(i, int(n/i))
    if min > fr:
      min = fr
print(min)


### FIXED CODE ###

def func(i, j):
  il = len(str(i))
  jl = len(str(j))
  if il > jl:
    return il
  return jl

n = int(input())
min = len(str(n))
for i in range(1, n+1):
  if i**2 > n:
    break
  if n % i == 0:
    fr = func(i, int(n/i))
    if min > fr:
      min = fr
print(min)
### BUGGY CODE ###

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

sum = 1
for num in nums:
    sum *= num

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

### FIXED CODE ###

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

sum = 1
if 0 in nums:
    print(0)
else:
    for num in nums:
        sum *= num
        if sum > 10 ** 18:
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

import bisect
X, Y, X, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort()
B.sort()
C.sort()
ans= []

for i in range(min(K,len(A))):
  for j in range(min(K,len(B))):
    for k in range(min(K,len(C))):
      tmp = A[i]+B[j]+C[k]
      bisect.insort_left(ans,tmp)
for i in range(K):
  print(ans[len(ans)-1-i])

### FIXED CODE ###

from heapq import heappop, heappush,heapify
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
H = []
heappush(H,[-1*(A[0]+B[0]+C[0]),0,0,0])
count = 1
memo = []
while H and count <= K:
  tmp,i,j,k = heappop(H)
  print(-1*tmp)
  count += 1
  if i+1 < X and ((i+1,j,k) not in memo):
    heappush(H,[-1*(A[i+1]+B[j]+C[k]),i+1,j,k])
    memo.append((i+1,j,k))
  if j+1 < Y and ((i,j+1,k) not in memo):
    heappush(H,[-1*(A[i]+B[j+1]+C[k]),i,j+1,k])
    memo.append((i,j+1,k))
  if k+1 < Z and ((i,j,k+1) not in memo):
    heappush(H,[-1*(A[i]+B[j]+C[k+1]),i,j,k+1])
    memo.append((i,j,k+1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
mod=p
B=[0]*p
for i in range(p):
  c=1
  B[0]-=A[i]
  for j in range(1,p):
    c*=i
    B[j]-=A[i]*c
    if j==p-1:
      B[j]+=A[i]
B=B[::-1]
for i in range(p):
  B[i]=B[i]%mod
print(*B)

### FIXED CODE ###

import sys
input = sys.stdin.readline
p=int(input())
A=[int(i) for i in input().split()]
B=[0]*p

P=[[0]*p for _ in range(p)]
for i in range(1,p): 
  for j in range(1,p):
    if j==1:
      P[i][j]=i
    else:
      P[i][j]=(P[i][j-1]*i)%p

for i in range(p):
  a=A[i]
  B[0]-=a
  for j in range(1,p):
    B[j]-=a*P[i][j]
    if j==p-1:
      B[j]+=a
B=B[::-1]
for i in range(p):
  B[i]%=p
print(*B)
### BUGGY CODE ###

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

ans = 0
for v in itertools.combinations(L,3):
  a,b,c = v[0],v[1],v[2]
  if a < b+c and b < c+a and c < a+b: ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n-2):
  for j in range(i+1, n-1):
    ab = l[i] + l[j]
    idx = bisect_left(l, ab)
    ans += max(idx-j-1, 0)
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
lst = []
lstn = [0] *10**5
cnt = 0
j = 0

def nCr(n,r):
    r = min(r,n-r)
    numerator = 1
    for i in range(n,n-r,-1):
        numerator *= i
    denomination = 1
    for i in range(r,1,-1):
        denomination *= i
    return numerator // denomination


for i in range(n):
    s = input()
    c = Counter(s)
    if c not in lst:
        lst.append(c)
        lstn[j] = 1
        j += 1
    else:
        k = lst.index(c)
        lstn[k] += 1

for x in lstn:
    if x >= 2:
        cnt += nCr(x,2)
print(cnt)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for i in range(N)]

sorted_S =  [''.join(sorted(s)) for s in S]
c = Counter(sorted_S)

print(sum([n * (n-1)//2 for n in  list(c.values())]))
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(str(input()))

for i in range(q):
        t1,t2 = map(int,input().split())
        r = s[t1-1:t2]
        r1 = ''.join(r)
        print(r1.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
c = 0
t = [0]
for i in range(1,n):
        if s[i] == "C" and s[i-1] == "A":
                c = c + 1
        t.append(c)

for i in range(q):
        t1,t2=map(int,input().split())
        print(t[t2-1]-t[t1-1])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for i in range(Q):
  l,r=map(int,input().split())
  A=S[l-1:r]
  ans=A.count('AC')
  print(ans)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

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

ans1 = 0 #偶数インデックスが正
for i in range(n):
    s1 = sum(a[:i+1])
    if i % 2 == 0:
        if s1 <= 0:
            x = abs(s1) + 1
            ans1 += x
            a[i] += x
        else:
            continue
    else:
        if s1 >= 0:
            x = abs(s1) + 1
            ans1 += x
            a[i] -= x
ans2 = 0 #偶数インデックスが負
for i in range(n):
    s2 = sum(a2[:i+1])
    if i % 2 == 1:
        if s2 <= 0:
            x = abs(s2) + 1
            ans2 += x
            a2[i] += x
        else:
            continue
    else:
        if s2 >= 0:
            x = abs(s2) + 1
            ans2 += x
            a2[i] -= x

print(min(ans1, ans2))

### FIXED CODE ###

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

def f(a, sgn):
    cnt = 0
    s = 0
    for i in range(n):
        s += a[i]
        sgn *= (-1) #判定する符号は交互に変わる
        if s * sgn <= 0: #sgn一致しなければその積は負
            x = s + sgn*(-1)
            s -= x
            cnt += abs(x)
        
    return cnt
ans = min(f(a, 1), f(a, -1))
print(ans)
### BUGGY CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None

if D.count(0)==1 and D[0]==0:

    mul=1
    n=1

    L=[]

    for i in range(1,max(D)+1):
        L.append(D.count(i))

    for m in L:
        mul*=n**m
        n=m
    
    ans=mul%998244353

else:
    ans=0

print(int(ans))

### FIXED CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None


if D.count(0)==1 and D[0]==0:

    L=[0]*(max(D)+1)

    for i in range(len(D)):
        L[D[i]]+=1

    mul=1

    for i in range(len(L)-1):
        mul*=L[i]**L[i+1]%998244353
    
    ans=mul%998244353

else:
    ans=0

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

import sys
input = sys.stdin.readline
import bisect
from collections import deque

def main():
    N = int(input())
    use = deque([10**9+1])
    for _ in range(N):
        num = int(input())
        if min(use) >= num:
            use.appendleft(num)
        else:
            index = bisect.bisect_left(use,num)
            use[index-1] = num
    
    print(len(use)-1)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
from collections import deque

def main():
    N = int(input())
    use = deque([int(input())])
    for _ in range(N-1):
        num = int(input())
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print(len(use))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

l = list(l)
for i in range(n):
	l[i] = int(l[i])

count = 0
memo =[0,0,0]*100
#a<b+c, a>b-c, a>c-b
for a in range(n):
	for b in range(a+1,n):
		for c in range(b+1,n):
			if l[a]<l[b]+l[c] and l[b]<l[c]+l[a] and l[c]<l[a]+l[b]:
				count += 1
				memo += a,b,c


print(count)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()

ans = 0

#a<b+c, a>b-c, a>c-b
for a in range(n-2):
	for b in range(a+1,n-1):
		index = bisect.bisect_left(l,l[a]+l[b])
		ans += index - (b+1)
print(ans)
### BUGGY CODE ###

S=input()
S=list(S)
dp=[]
for _ in range(len(S)):
    dp.append([0]*13)
if S[0]=='?':
    for i in range(10):
        dp[0][(i*10**(len(S)-1))%13]=1
else:
    dp[0][(int(S[0])*10**(len(S)-1))%13]=1
for j in range(0,len(S)-1):
    for k in range(13):
        if S[j+1]=='?':
            L=[]
            for l in range(10):
                l=(l*10**(len(S)-j-2)%13)
                L.append(dp[j][k-l])
            dp[j+1][k]+=sum(L)
        else:
            dp[j+1][k]=dp[j][k-(int(S[j+1]))*10**(len(S)-j-2)%13]
print((dp[len(S)-1][5])%(7+10**9))

### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()