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

N = int(input())
A = [int(a) for a in input().split()]

l = 0
r = 2 * 10**5
while r-l >= 2:
    m = l + (r-l) //2
    X = {}
    for i in range(1,N):
        try:
            if A[i] <= A[i-1]:
                if A[i] < A[i-1]:
                    for j in X:
                        if j > A[i]:
                            X[j] = 0
                            # del X[j]
                if A[i] in X:
                    X[A[i]] += 1
                    k = A[i]
                    while k in X and X[k] >= m:
                        X[k] = 0
                        if k-1 in X:
                            X[k-1] += 1
                        else:
                            X[k-1] = 1
                        k -= 1
                        if k <= 0:
                            raise Exception
                else:
                    if m == 1:
                        raise Exception
                    X[A[i]] = 1
                    
        except:
            l = m
            break
    else:
        r = m
print(r)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

def chk(k):
    if k == 1:
        for i in range(1, N):
            if A[i] <= A[i-1]: return 0
        return 1
    
    X = [(0, 0)]
    def add(x, y):
        if x <= 0: return 0
        if x > X[-1][0]:
            X.append((x, 0 if x == y else 1))
        elif x == X[-1][0]:
            if X[-1][1] + 1 < k:
                X[-1] = (X[-1][0], X[-1][1] + 1)
            else:
                if add(x-1, y) == 0: return 0
        else:
            while X[-1][0] > x:
                X.pop()
            if x > X[-1][0]:
                X.append((x, 1))
            elif x == X[-1][0]:
                if X[-1][1] + 1 < k:
                    X[-1] = (X[-1][0], X[-1][1] + 1)
                else:
                    if add(x-1, y) == 0: return 0
        if X[-1][0] < y: X.append((y, 0))
        return 1
    
    for a in A:
        if add(a, a) == 0: return 0
    return 1

l, r = 0, 1 << 18
while r - l > 1:
    m = (l + r) // 2
    if chk(m):
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

s = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

divs = make_divisors(s)
n = len(divs)
if n%2 == 0:
    print(0, 0, divs[n//2-1], 0, divs[n//2-1], divs[n//2])
else:
    print(0, 0, divs[n//2], 0, divs[n//2], divs[n//2])
# print(divs)


### FIXED CODE ###

s = int(input())
x3 = (10**9-s%10**9)%10**9
y3 = (s+x3)//10**9
print(0, 0, 10**9, 1, x3, y3)
### BUGGY CODE ###

N,M = map(int,input().split())
K=[]
A=[]
B=[]
answer='IMPOSSIBLE'
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    A +=[b]
  if b==N:
    B += [a]
for x in B:
  if x in A:
    answer='POSSIBLE'
print(answer)

### FIXED CODE ###

N,M = map(int,input().split())
K=[0]*(N+1)
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    K[b] +=1
  if b == N:
    K[a] +=1
print('POSSIBLE' if 2 in K else 'IMPOSSIBLE')
### BUGGY CODE ###

def solve(mid):
    l=k
    for b,g in zip(a,f):
        if b*g>mid:
            l-=b-mid//g
    if l<0:return False
    return True
n,k,*a=map(int,open(0).read().split())
a,f=sorted(a[:n])[::-1],sorted(a[n:])
ok=10**12
ng=-1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if solve(mid):
        ok=mid
    else:
        ng=mid
print(ok)

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()
### BUGGY CODE ###

def main():
    a, b, x = map(int, input().split())
    li = filter(lambda y: y % x == 0, range(a, b + 1))
    print(len(list(li)))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    a, b, x = map(int, input().split())
    print(b // x + 1 - ((a - 1) // x + 1 if a != 0 else 0))


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

from fractions import Fraction as F
from fractions import gcd

MOD = 10 ** 9 + 7

def lcm(a, b):
    return a * b // gcd(a, b)

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

# B_1 = 1と仮定
b = [F(1, 1)]
for i in range(1, n):
    b.append(F(a[0], a[i]))

al_lcm = 1
for i in b:
    al_lcm = lcm(al_lcm, i.denominator)

# print(al_lcm)

res = 0
for i in b:
    res += i * al_lcm

print(res % MOD)

# print(b)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def cmb(n, r, p, fact, factinv):
    if r < 0 or n < r:return 0
    return fact[n] * factinv[r] * factinv[n-r] % p
def main():
    n, a, b = map(int, input().split())
    ans = 0
    p = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    for i in range(1, n+1):
        if i == a or i == b:continue
        ans += cmb(n, i, p, fact, factinv)
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def cmb(n, k, p):
    x, y = 1, 1
    for i in range(k):
        x = x * (n-i) % p
        y = y * (k-i) % p
    return x * pow(y, p-2, p) % p
def main():
    n, a, b = map(int, input().split())
    p = 10 ** 9 + 7
    ans = pow(2, n, p) - 1
    ans -= cmb(n, a, p) + cmb(n, b, p)
    print(ans%p)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
change = [list(map(int,input().split())) for _ in range(M)]

for i in change:
  for j in range(i[0]):
    A.append(i[1])

A.sort(reverse = True)
print(sum(A[0:N]))

### FIXED CODE ###

from heapq import heappush,heappop,heapify

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
change = [list(map(int,input().split())) for _ in range(M)]

def tempchange(l,change):
  heapify(l)  
  for B,C in change:
    for j in range(B):
      a = heappop(l)
      if C - a > 0:
        heappush(l,C)
      else:
        heappush(l,a)
        break
  return sum(l)

#A.sort(reverse = True)
change.sort(key = lambda x:x[1],reverse =True)
print(tempchange(A,change))
### BUGGY CODE ###

from bisect import bisect_right, bisect_left

n = int(input())

a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))


i_list = []
j_list = []

for x in b:
  i = bisect_left(a, x)
  i_list.append(len(a[:i]))

for x in b:
  j = bisect_right(c, x)
  j_list.append(len(c[j:]))

ans = 0

for i, j in zip(i_list, j_list):
  ans += i*j

print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left

n = int(input())

a = sorted(list(map(int, input().split())))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for x in b:
  ans += bisect_left(a, x) * (n - bisect_right(c, x))

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

import math
k = int(input())
s = input()

ss = len(s)

mod = 10**9 + 7

m25 = []
m26 = []
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

samu = 0
for i in range(k+1):
    sm = math.factorial(ss+k-i-1) // (math.factorial(ss-1) * math.factorial(k-i))
    sm %= mod
    sm *= m25[k-i]
    sm *= m26[i]
    sm %= mod
    samu += sm

samu %= mod
print(samu)


### FIXED CODE ###

import math
k = int(input())
s = len(input())

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
m_n = [1] # 逆元を記録する
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(2,k+s):
    x = mod % i
    y = mod // i
    c = - m_n[x-1] * y
    c %= mod
    m_n.append(c)

samu = 0
fc = 1
for i in range(k):
    sm = fc
    sm *= m25[i]
    sm *= m26[k-i]
    sm %= mod
    samu += sm

    fc *= (s + i)
    fc %= mod
    fc *= m_n[i]
    fc %= mod

sm = fc
sm *= m25[k]
sm %= mod
samu += sm

samu %= mod
print(samu)
### BUGGY CODE ###

S = input()
T = input()
len_S = len(S)
len_T = len(T)

dp = {i: {j: 0 for j in range(len_T+1)} for i in range(len_S+1)}
for i in range(len_S):
    for j in range(len_T):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

# backtrack
ans = ''
i, j = len_S, len_T
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i, j = i - 1, j - 1
    else:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
print(ans)

### FIXED CODE ###

S = input()
T = input()
len_S = len(S)
len_T = len(T)

dp = {i: {j: 0 for j in range(len_T+1)} for i in range(len_S+1)}
for i in range(len_S):
    for j in range(len_T):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

# backtrack
ans = ''
i, j = len_S, len_T
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i, j = i - 1, j - 1
    else:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
print(ans)
### BUGGY CODE ###

import fractions

def main():
  x,y=map(int,input().split())
  mod=10**9+7

  if (2*x-y)%3==0 and (2*y-x)%3==0 and (2*x-y)>=0 and (2*y-x)>=0:
    a=(2*x-y)//3
    b=(2*y-x)//3
    #print(a,b)

    result=0.0
    bunbo=1
    bunshi=1

    for i in range(min(a,b)):
      bunbo=bunbo*(a+b-i)
      temp=1+i
      
      if bunbo%temp==0:
        bunbo=bunbo//temp
      else:
        bunshi=bunshi*(1+i)
      while bunbo%2==0 and bunshi%2==0:
        bunbo=bunbo//2
        bunshi=bunshi//2
      while bunbo%3==0 and bunshi%3==0:
        bunbo=bunbo//3
        bunshi=bunshi//3
      while bunbo%5==0 and bunshi%5==0:
        bunbo=bunbo//5
        bunshi=bunshi//5
      while bunbo%7==0 and bunshi%7==0:
        bunbo=bunbo//7
        bunshi=bunshi//7
      while bunbo%11==0 and bunshi%11==0:
        bunbo=bunbo//11
        bunshi=bunshi//11
      while bunbo%13==0 and bunshi%13==0:
        bunbo=bunbo//13
        bunshi=bunshi//13
      while bunbo%17==0 and bunshi%17==0:
        bunbo=bunbo//17
        bunshi=bunshi//17
      #print(bunbo,bunshi)
      
    result=bunbo//bunshi%mod
    print(int(result))

  else:
    print(0)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

x,y=map(int,input().split())



if (x+y)%3!=0:
    print(0)
    exit()

if x==0 and y==0:
    print(0)
    exit()


n=(2*y-x)//3
m=(2*x-y)//3


if m<0 or n<0:
    print(0)
    exit()

if n==0 and m==1:
    print(1)
    exit()
if n==1 and m==0:
    print(1)
    exit()
    

#n+mCm
#(n+m)!/m!


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)



print(cmb(n+m, m, 10**9+7))
### BUGGY CODE ###

from sys import stdin

#ans = []
#temp_array = []
temp_ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    N_l = len(N)
    global temp_ans
    #global ans
    #global temp_array
    for i in range(N_l)[::-1]:
        temp_ans += N[i]
        #if i == N_l-1:
        #    temp_ans = ans
        #else:
        for s in temp_ans:
            if s[0] != N[i] and N[i] not in s:
                temp_ans.append(N[i]+s)
                    #print(N[i]+s)
        #print(temp_ans)
        #ans += temp_array
        #temp_ans = ans
        #temp_array = []
    return len(temp_ans) % (10**9 + 7)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
import math
import itertools


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

# これだと、O(n*n)
"""
temp_ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    N_l = len(N)
    global temp_ans
    for i in range(N_l)[::-1]:
        temp_ans += N[i]
        #print(temp_ans)
        for s in temp_ans:
            #print(s)
            if N[i] not in s:
                temp_ans.append(N[i]+s)
    #print(temp_ans)
    return len(temp_ans) % (10**9 + 7)
"""


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    #print(S)
    dic = {}
    c = 0
    for i in range(S)[::-1]:
        if N[i] not in dic:
            dic[N[i]] = 1
            #c += i+1
        else:
            dic[N[i]] += 1

    c = 1
    for key, value in dic.items():
        c *= (value+1)
    c -= 1
    """
    c += 2**len(dic.keys())-1
    #print(c)
    #c += S
    for key, value in dic.items():
        if value > 1:
            #c -= (value-1)
            c += 2**(len(dic.keys()))-1
            #print(c)
    #for key, value in dic.items():
    for key, value in dic.items():
        if value > 1:
            if len(dic.keys()) != S:
                c -= 2**(S-len(dic.keys())-1)
    """
            #print(c)
        #else:
    #c += (S-len(dic.keys()))
    """
    s_N = sorted(N)
    for i in range(S-1):
        if s_N[i] != s_N[i+1]:
            c += 2**(i+2)
    """
    """
    for key, value in dic.items():
        if value > 1:
            c += 2**(len(dic.items())-value)
        else:
            c += 2**(len(dic.items())-value)
    """
    #combinations_count(len(, r)

    return c % (10**9 + 7)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


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

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort(key=lambda z:z[0])
y.sort(key=lambda z:z[0])
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,0,-1):
        for i2 in range(n):
            for l2 in range(n-i2,0,-1):
                x_sub1,y_sub1=10**9+1,10**9+1
                x_sub2,y_sub2=-10**9-1,-10**9-1
                z=[0]*n
                for i in range(i1,i1+l1):
                    l=x[i][1]
                    x_sub1=min(xy[l][0],x_sub1)
                    x_sub2=max(xy[l][0],x_sub2)
                    y_sub1=min(xy[l][1],y_sub1)
                    y_sub2=max(xy[l][1],y_sub2)
                    z[l]=1
                for i in range(i2,i2+l2):
                    l=y[i][1]
                    x_sub1=min(xy[l][0],x_sub1)
                    x_sub2=max(xy[l][0],x_sub2)
                    y_sub1=min(xy[l][1],y_sub1)
                    y_sub2=max(xy[l][1],y_sub2)
                    z[l]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break

print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

costs = [0] * N
for i in range(1,N):
  _h = h[i]
  s = 0
  if i > K:
    s = i-K
  mn = float('inf')
  for a,b in zip(costs[s:i],h[s:i]):
    cur = a + abs(_h-b)
    if cur < mn:
      mn = cur
 
  costs[i] = mn
print(costs[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

def aa (n,k,ll):
  dp = [0] * n
  for i in range(1,n):
    s = max(i-k,0)
    mn = float('inf')
    for a,b in zip(dp[s:i],ll[s:i]):
      cur = a + abs(ll[i]-b)
      if cur < mn:
        mn = cur
  
    dp[i] = mn
  print(dp[-1])

aa(N,K,h)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = input()
q = int(input())
for i in range(q):
    qfc = input()
    if qfc[0] == '1':
        s = s[::-1]
    else:
        if qfc[2] == '1':
            s = qfc[4] + s
        else:
            s += qfc[4]
print(s)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = input()
q = int(input())
flag = True
p = ''
m = ''
for i in range(q):
    qfc = input()
    if qfc[0] == '1':
        if flag:
            flag = False
        else:
            flag = True
    else:
        if qfc[2] == '1':
            if flag:
                p += qfc[4]
            else:
                m += qfc[4]
        else:
            if flag:
                m += qfc[4]
            else:
                p += qfc[4]
if flag:
    print(p[::-1] + s + m)
else:
    print(m[::-1] + s[::-1] + p)
### BUGGY CODE ###

n = int(input())
temp = []
for i in range(n):
	temp.append(int(input()))

if n > 1:
	print(max(temp[1:n]))

	for i in range(1,n-1):
		print(max(max(temp[0:i]), max(temp[i+1:n])))

	print(max(temp[0:n-1]))

else:
	print(temp[0])

### FIXED CODE ###

n = int(input())
temp = []
for i in range(n):
	temp.append(int(input()))

sort = temp[:]

sort.sort()

maximum = sort[-1]


for i in temp:
	if i != maximum:
		print(maximum)

	else:
		print(sort[-2])
### BUGGY CODE ###

""" dpはi桁,あまりj
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
S = str(input())
S = S[::-1]
n = len(S)

dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1 #0を割ったあまりは0

q = 1 # はじめの1桁のときはあまりは1

# i桁目のあまりが何通りあるか
for i in range(1,n+1): # 「1-n」桁まで
  s = S[i-1]
  for j in range(13): # 13で割ったあまり
    
    if s == '?': # ?の場合は0-9を計算する
      for k in range(10):
        dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目 +=を忘れずに！
    else:
      k = int(s)
      dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目
      
  q = (10*q)%13 # 「10^iをqで割ったあまり」

print(dp[n][5]% (10**9+7))

### FIXED CODE ###

""" dpはi桁,あまりj
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
MOD = 10**9+7

S = str(input())
S = S[::-1]
n = len(S)

dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1 #0を割ったあまりは0

q = 1 # はじめの1桁のときはあまりは1

# i桁目のあまりが何通りあるか
for i in range(1,n+1): # 「1-n」桁まで
  s = S[i-1]
  for j in range(13): # 13で割ったあまり
    
    if s == '?': # ?の場合は0-9を計算する
      for k in range(10):
        dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目 +=を忘れずに！
    else:
      k = int(s)
      dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目
  for m in range(13):
    dp[i][m] %= MOD
  q = (10*q)%13 # 「10^iをqで割ったあまり」

print(dp[n][5] % MOD)
### BUGGY CODE ###

import bisect
import math

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    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

#####単位元######
ide_ele = 0
#input
data = []
n, d, a = map(int, input().split())
x_point = []
for i in range(n):
    x, h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
x_point.sort()
data.sort()
##初期化
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
ans = 0
for i in range(n):
    x, h = data[i]
    index = bisect.bisect_left(x_point, x - 2*d)
    sum_damage = query(index, i)
    h -= sum_damage
    count = max(((h+a-1)//a), 0)
    ans += count
    update(i, count * a)
print(ans)

### FIXED CODE ###

from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    h = max(h, 0)
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)
### BUGGY CODE ###

n = int(input())
arr = [int(x) for x in input().split()]
ans = arr[0]
for i in range(1,n):
	ans *= arr[i]

if ans>1000000000000000000:
	print(-1)
else:
	print(ans)


### FIXED CODE ###

N = int(input())
arr = [int(x) for x in input().split()]
arr.sort()
prod = 1
for i in arr:
	prod *= i
	if prod>10**18:
		prod = -1
		break
print(prod)
### BUGGY CODE ###

from collections import defaultdict
H, W = map(int, input().split())

A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(map(int, input().split())) for _ in range(H)]
dp = [[defaultdict(lambda : False) for _ in range(W)] for _ in range(H)]
dp[0][0][0] = True

for h in range(H):
    for w in range(W):
        C = A[h][w] - B[h][w]
        for v, f in dp[h][w].items():
            if f:
                if h < H - 1:
                    dp[h + 1][w][v + C] = True
                    dp[h + 1][w][v - C] = True
                if w < W - 1:
                    dp[h][w + 1][v + C] = True
                    dp[h][w + 1][v - C] = True

ans = 10**10
C = A[H - 1][W - 1] - B[H - 1][W - 1]
for v, f in dp[H - 1][W - 1].items():
    if f:
        ans = min(ans, abs(v - C))
        ans = min(ans, abs(v + C))
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
M = (H + W) * 80

A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(map(int, input().split())) for _ in range(H)]

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(digit - M)
ans = min(abs(n) for n in nums)
print(ans)