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

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

for i in range(1,n+1):
    print(l.count(i))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
k = [0]*n
for i in range(len(l)):
    c = l[i]
    k[c-1] = k[c-1]+1
for j in range(len(k)):
    print(k[j])
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()
ans = 0
x0 = [0]*p
y = [0]*p
for i in range(p):
  y[i] = (i*10)%p
for t in s:
  x1 = [0]*p
  z = int(t)
  x1[z%p] = 1
  for j in range(p):
    x1[(y[j]+z)%p] += x0[j]
  x0 = x1
  ans += x0[0]
print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
x = [1] + [0]*(p-1)
ans = 0
u = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = (int(s[i])*pow(10,n-1-i,p)+u)%p
    ans += x[u]
    x[u] += 1
print(ans)
### BUGGY CODE ###

def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0: # 5,6回程度
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= input()
    X = list(X_str)
    bit_count = X_str.count('1')

    for i in range(N):
        # ビットの反転
        x_copy = X.copy()
        bit_count_n = bit_count
        if x_copy[i] == '0':
            x_copy[i] = '1'
            bit_count_n += 1
        else:
            x_copy[i] = '0'
            bit_count_n -= 1

        bit_int = int("".join(x_copy), 2)

        print(popcount(bit_int, bit_count_n))






### FIXED CODE ###

def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)
### BUGGY CODE ###

from heapq import heappop, heappush
N = int(input())
a = list(map(int, input().split()))

pq1 = []
for x in a[:N]:
    heappush(pq1, x)

pq2 = sorted(a[N:])

ans = sum(pq1) - sum(pq2[:N])
for k in range(N, 2 * N):
    heappush(pq1, a[k])
    heappop(pq1)    
    pq2.remove(a[k])
    
    ans = max(ans, sum(pq1) - sum(pq2[:N]))
    
print(ans)


### FIXED CODE ###

from heapq import heappop, heappush, heapify
N = int(input())
a = list(map(int, input().split()))

pq1 = a[:N]
pq2 = [-x for x in a[2 * N:]]

heapify(pq1)
heapify(pq2)

s1 = sum(pq1)
s2 = sum(pq2)

ans1 = [s1]
ans2 = [s2]

for k in range(N, 2 * N):
    heappush(pq1, a[k])
    x = heappop(pq1)
    s1 += a[k] - x
    ans1.append(s1)
    
    heappush(pq2, -a[3 * N - k - 1])
    x = heappop(pq2)
    s2 += -a[3 * N - k - 1] - x
    ans2.append(s2)
    
print(max(ans1[i] + ans2[-i - 1] for i in range(len(ans1))))
### BUGGY CODE ###

import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
def dfs(A):
  l=[]
  if len(A)==1:
    return A[0]
  for i in range(0,len(A),2):
    if i+1 != len(A):
      l.append(fractions.gcd(A[i],A[i+1]))
    else:
      l.append(A[i])
  return dfs(l)
  
  
for i in range(N):
  s=copy.deepcopy(A)
  s.pop(i)
  ans.append(dfs(s))

print(max(ans))

### FIXED CODE ###

import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
L=[0 for i in range(N)]
R=[0 for i in range(N)]
for i in range(N):
  if i != 0:
    L[i]=fractions.gcd(L[i-1],A[i-1])
    R[N-1-i]=fractions.gcd(R[N-i],A[N-i])

for i in range(N):
  ans.append(fractions.gcd(L[i],R[i]))

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

t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    dp=[set() for i in range(n+1)]
    dp[n]={0}
    for i in range(n,0,-1):
        if s[i-1]=="0":
            for j in dp[i]:
                dp[i-1].add(j)
                dp[i-1].add(j^a[i-1])
        else:
            if a[i-1] in dp[i]:
                for j in dp[i]:
                    dp[i-1].add(j)
            else:
                print(1)
                break
    else:
        print(0)





### FIXED CODE ###

#一次独立：rankが成分数
import numpy as np
#0-indexed,MSBがma以下の時
def msb(x,ma=59):
    for i in range(ma,-1,-1):
        if (x>>i)&1:
            return i
    return len()
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    #独立、msb同じものはない
    #逆に異なれば独立
    msbs=[0 for i in range(60)]
    for i in range(n-1,-1,-1):
        now=a[i]
        m=59
        #独立のときfはTrue、独立でない時fはFalse
        while True:
            m=msb(now,m)
            if msbs[m]==0:
                f=True
                break
            now=msbs[m]^now
            if now==0:
                f=False
                break
        if s[i]=="0":
            if f:
                msbs[m]=now
        else:
            if f:
                print(1)
                break
    else:
        print(0)
### BUGGY CODE ###

N, M = map(int, input().split())

#print(N,M)

okList = [1] * N

#print(okList)
#print(type(okList))

for i in range(M):
    L, R = map(int, input().split())
    L -= 1
    if 0 < L:
        okList[0:L] = [0] * L
        #print(okList)

    if R < len(okList):
        okList[R:len(okList)] = [0] * (len(okList) - R)
        #print(okList)

print(sum(okList))

### FIXED CODE ###

N, M = map(int, input().split())
maxL = 1
minR = N

for i in range(M):
    L, R = map(int, input().split())
    if maxL < L:
        maxL = L
    if minR != None and R < minR:
        minR = R
    #print("\t\t\t", maxL, minR)

if maxL <= minR:
    print(minR - maxL + 1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = []
new_a = []

for k in range(n):
    a.append(str(input()))
    new_a.append( ''.join(list(sorted(a[k]))))

new_a.sort()

b = 0

for k in range(n-1):
    for m in range(k+1, n):
        if(new_a[k] == new_a[m]):
            b = b + 1

print(b)

### FIXED CODE ###

import math
n = int(input())
list_voc = [str(input()) for _ in range(n)]
list_mo = []
for i, s in enumerate(list_voc):
    list_n = list(s)
    list_n.sort()
    list_n = ''.join(list_n)
    list_mo.append(list_n)

ans = {}
for s in list_mo:
    if s in ans:
        ans[s] += 1
    else:
        ans[s] = 1


ans_val = []

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


for s in ans:
    if ans[s] != 1:
        ans_val.append(cmb(ans[s], 2))


print(sum(ans_val))
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
max = 0
for i in range(N-K+1):
  r = 0
  for j in range(K):
    r += p[i+j] + 1
  if max < r/2:
    max = r/2
print(max)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
max = 0
r = 0
for i in range(K):
  max = max + p[i] + 1
  r = r + p[i] + 1
  
for j in range(N-K):
  r = r -p[j] + p[K+j]
  if max < r:
    max = r
    
print(max/2)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
kitaiti = [0] * n
for i in range(n):
    kitaiti[i] = (p[i]+1) / 2
# 初期値
l = 0
r = k - 1
max = 0
for i in range(n-k+1):
    now = sum(kitaiti[l:r+1])
    l += 1
    r += 1
    if now > max:
        max = now
print(max)

### FIXED CODE ###

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

kitaiti = [0 for _ in range(n)]
ruisekiwa = [0 for _ in range(n)]
r = k - 1
max = 0
now = 0
ans_list = []

for i in range(n):
    kitaiti[i] = (p[i]+1) / 2
    if i == 0:
        ruisekiwa[0] = kitaiti[0]
    else:
        ruisekiwa[i] = ruisekiwa[i-1] + kitaiti[i]
    if i == r:
        now = ruisekiwa[i]
    elif i > r:
        now = ruisekiwa[i] - ruisekiwa[i-r-1]
    if now > max:
        max = now
print(max)
### BUGGY CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

n = input()
arr = list(map(int, input().split()))
tmp = arr[0]
for i in arr:
    tmp = tmp*i//gcd(tmp,i)
print(sum(tmp//a for a in arr) % (10**9+7))

### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

n = input()
arr = list(map(int, input().split()))
tmp = arr[0]
for i in arr:
    tmp = tmp*i//gcd(tmp,i)
print(sum(tmp//a for a in arr) % (10**9+7))
### BUGGY CODE ###

def main():
    import bisect
    import sys
    from itertools import accumulate
    input = sys.stdin.readline
    def hsnum(ls,x,n):
        num = 0
        for i in range(n):
            y = x-ls[i]
            num += n-bisect.bisect_left(ls,y)
        return num
    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    suma = [0]+list(accumulate(a))
    lx = 0
    rx = 2*10**5+2
    error = 0
    while lx < rx:
        mx = (lx+rx)//2
        if hsnum(a,mx,n) < m:
            rx = mx
        elif hsnum(a,mx,n) > m:
            if hsnum(a,mx+1,n) < m:
                error = hsnum(a,mx,n)-m
                lx = mx
                break
            lx = mx + 1
        else:
            lx = mx
            break
    ans = 0
    for i in range(n):
        rema = lx - a[i]
        j = bisect.bisect_left(a,rema)
        ans += (n-j)*a[i]+suma[n]-suma[j]
    print(ans-error*lx)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx -= 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = []
for i in range(len(S)):
  for j in range(i+1,len(S)):
    for k in range(j+1,len(S)):
      ans.append(S[i]+S[j]+S[k])
print(len(list(set(ans))))
      


### FIXED CODE ###

def main():
  N = int(input())
  S = tuple(input())
  ans = 0
  for i in range(1000):
    if i<10:
      cnt0= 0
      cnt1 = 0
      for j in range(N):
        if 2<=cnt0 and S[j]=="%d"%i:
          ans+=1
          break
        if S[j]=="0":
          cnt0+=1
          continue
    elif 10<=i<=99:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[1]:
          ans+=1
          break
        if S[j]=="0" and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[0]:
          cnt1 +=1
          continue
    elif 100<=i:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[2]:
          ans+=1
          #print(i)
          break
        if S[j]=="%s"%i[0] and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[1]:
          cnt1 +=1
          continue
  print(ans)
main()
### BUGGY CODE ###

import copy


def main():
    n = int(input())
    s = [["" for j in range(10)] for i in range(n)]
    for i in range(n):
        s[i] = list(input())

    cnt = 0
    for i in range(n):
        cnt += count_anagram(s[i], s[i+1: n])

    print(cnt)


def anagram(list1, list2):
    if not list1:
        return True

    if list1[0] in list2:
        list2.remove(list1[0])
        list1.pop(0)
        return anagram(list1, list2)
    else:
        return False


def count_anagram(s, str_list):
    cnt = 0
    for t in str_list:
        u, v = copy.copy(s), copy.copy(t)
        if anagram(u, v):
            cnt += 1
    return cnt


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

n = int(input())
s = ["".join(sorted(input())) for i in range(n)]

counter = collections.Counter(s)

ans = 0
for i in counter.values():
   if i > 0:
        ans += i * (i - 1) // 2

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


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

def gcd(a,b):
    c=max(a,b)
    d=min(a,b)
    while True:
        if c%d==0:
            return d
        c,d=d,c%d

def gcd_list(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcd_list(A[len(A)//2:]),gcd_list(A[:len(A)//2]))
max_gcd=1
for i in range(N):
    max_gcd=max(gcd_list(A[:i]+A[i+1:]),max_gcd)
    
print(max_gcd)

### FIXED CODE ###

def gcd(a,b):
	a,b = max(a,b),min(a,b)
	while a%b!=0:
   		a,b = b,a%b
	return b

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

S1 = [A[0]]
s = A[0]
for i in range(1,N-1):
    s=gcd(s,A[i])
    S1.append(s)

S2 = [A[N-1]]
s = A[N-1]
for i in range(1,N-1):
    s=gcd(s,A[N-i-1])
    S2.append(s)

max_gcd = 1
for i in range(N):
    if i==0:
        max_gcd=max(max_gcd,S2[N-2])
    elif i==N-1:
        max_gcd=max(max_gcd,S1[N-2])
    else:
        max_gcd=max(max_gcd,gcd(S1[i-1],S2[N-2-i]))

print(max_gcd)
### BUGGY CODE ###

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

ans = ''
for i in range(1, N+1):
  ans += str(A.index(i)+1)
  ans += ' '
  
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
l = [0]*N
for i in range(N):
  l[A[i]-1] = str(i+1)

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

N, M = map(int, input().split())

id = [True] * (N+1)

for i in range(M):
    L, R = map(int, input().split())
    for j in range(1, L):
        id[j] = False
    for j in range(R+1, N+1):
        id[j] = False

cnt = 0
for i in range(1, N+1):
    if id[i] == True:
        cnt += 1

print(cnt)


### FIXED CODE ###

N, M = map(int, input().split())

left = 1
right = N

for i in range(M):
    L, R = map(int, input().split())
    if L > left :
        left = L
    if R < right:
        right = R

if right-left+1 > 0:
    print(right-left+1)
else:
    print(0)
### BUGGY CODE ###

n=int(input())
s = [0] *n

print(0,flush=True)
a = input()
if a=='Vacant':
    exit()
s[0]=a

l = 0
r = n-1
while True:
    m = (r-l)//2+l
    print(m,flush=True)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if ((m-l)%2==0 and s[m]==s[l]) or ((m-l)%2==1 and s[m]!=s[l]):
        l = m+1
    else:
        r = m-1



### FIXED CODE ###

n=int(input())
s = [0] * (n+1)

print(0,flush=True)
a = input()
if a=='Vacant':
    exit()
s[0]=a
s[n]=a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m,flush=True)
    a = input()
    if a=='Vacant':
        exit()
    s[m]=a
    if s[l]==s[r]:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
    else:
        if s[l]==s[m]:
            if (m-l)%2==1:
                r = m
            else:
                l = m
        else:
            if (m-l)%2==1:
                l = m
            else:
                r = m
### BUGGY CODE ###

def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v

# input data
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x > n: break
    g.append(x)
    m += 1
g = g[::-1]

# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))

# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])

# 3 output cnt
print(cnt)
# 4 output sorted a
for i in range(n):
    print(a[i])

### FIXED CODE ###

import sys
 
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
 
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
 
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
 
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
 
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
 
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))
### BUGGY CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
b = set(a)
c = [a.count(i) for i in b]
d = len(b)
c.sort()
ans = 0
for i in c:
    if K >= d:
        break
    ans += i
    d -= 1
print(ans)


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

N,K = map(int,input().split())
a = list(map(int,input().split()))
c = collections.Counter(a)
d = len(c)
ans = 0
c_sorted = sorted(c.items(),key = lambda x:x[1])
for i in c_sorted:
    if K >= d:
        break
    ans += i[1]
    d -= 1
print(ans)
### BUGGY CODE ###

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

a.sort(reverse=True)
f.sort()


def check(x):
    red = [a[i] - x // f[i] for i in range(n) if a[i] * f[i] > x]
    red = sum(red)
    return (red <= k)


lb = -1  # false
ub = max([a[i] * f[i] for i in range(n)])  # true
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


### FIXED CODE ###

from heapq import heappush, heappop
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a.sort(reverse=True)
f.sort()


def check(x):
    red = 0
    for i in range(n):
        if a[i] * f[i] > x:
            red += a[i] - x // f[i]

    return (red <= k)


lb = -1  # false
ub = max([a[i] * f[i] for i in range(n)])  # true
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)
### BUGGY CODE ###

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

mod=10**9+7
def modfc(x,y,p):
  f=1
  for i in range(x,y+1):
    f=f%p*i%p
  return f%p
def comb(x,y,p):
  return modfc(x-y+1,x,p)*pow(modfc(1,y,p),p-2,p)

maxs=0
for i in range(k,n+1):
  maxs+=a[i-1]*comb(i-1,k-1,mod)
  maxs%=mod
mins=0
for i in range(n-k+1):
  mins+=a[i]*comb(n-i-1,k-1,mod)
  mins%=mod
ans=(maxs-mins)%mod
print(ans+mod if ans<0 else ans)

### FIXED CODE ###

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

mod=10**9+7
fcl=[1]*(n+1)
for i in range(1,n+1):
  fcl[i]=(fcl[i-1]*i)%mod
def comb(x,y,p):
  return ((fcl[x]*pow(fcl[y],p-2,p))%mod*pow(fcl[x-y],p-2,p))%mod

maxs=0
for i in range(k,n+1):
  maxs+=a[i-1]*comb(i-1,k-1,mod)
  maxs%=mod
mins=0
for i in range(n-k+1):
  mins+=a[i]*comb(n-i-1,k-1,mod)
  mins%=mod
ans=(maxs-mins)%mod
print(ans+mod if ans<0 else ans)
### BUGGY CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
M = 13
DP = [0] * M
DP[0] = 1

mul = 1
for i in range(len(S) - 1, -1, -1):
    s = S[i]
    newDP = [0] * M
    if s == '?':
        for k in range(10):
            for j in range(M):
                newDP[(mul * k + j) % M] += DP[j]
    else:
        k = int(s)
        for j in range(M):
            newDP[(mul * k + j) % M] += DP[j]
    DP = [x % MOD for x in newDP]
    mul *= 10

print(DP[5])


### FIXED CODE ###

import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
M = 13
DP = [0] * M
DP[0] = 1

mul = 1
for i in range(len(S) - 1, -1, -1):
    s = S[i]
    newDP = [0] * M
    if s == '?':
        for k in range(10):
            for j in range(M):
                newDP[(mul * k + j) % M] += DP[j]
    else:
        k = int(s)
        for j in range(M):
            newDP[(mul * k + j) % M] += DP[j]
    DP = [x % MOD for x in newDP]
    mul *= 10
    mul %= M

print(DP[5])
### BUGGY CODE ###

import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))
  

### FIXED CODE ###

import sys
from heapq import heapify,heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
N=int(input())
List=[[] for i in range(N)]
for i in range(1,N):
  a=int(input())
  List[a-1].append(i)

def f(x):
  if len(List[x])==0:
    return 0
  L=[]
  heapify(L)
  for a in List[x]:
    heappush(L,f(a))
  n=len(L)
  res=0
  for i in range(n):
    b=heappop(L)
    res=max(res,b+n-i)
  return res
print(f(0))
### BUGGY CODE ###

N = int(input())
P = [int(x) - 1 for x in input().split()]

idx = [0] * N
for i in range(N):
    idx[P[i]] = i

ans = 0
for i in range(N - 2, -1, -1):
    find = False
    l1 = idx[i] + 1
    l2 = 0
    for j in range(idx[i] - 1, -1, -1):
        if i < P[j]:
            if not find:
                l1 = idx[i] - j
                l2 = j + 1
                find = True
            else:
                l2 = idx[i] - l1 - j
                break
    
    find = False
    r1 = N - idx[i]
    r2 = 0
    for j in range(idx[i] + 1, N):
        if i < P[j]:
            if not find:
                r1 = j - idx[i]
                r2 = N - j
                find = True
            else:
                r2 = j - r1 - idx[i]
                break
    ans += (i + 1) * (l1 * r2 + l2 * r1)

print(ans)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)