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

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    d = list(map(int, input().split()))
    mind = min(d)
    maxd = max(d)

    ans = 0
    for i in range(mind, maxd):
        n = sum(x > i for x in d)
        if n == N // 2:
            ans += 1


    print(ans)


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    d = list(map(int, input().split()))
    sod = sorted(d)


    print(sod[int(N/2)] - sod[int(N/2)-1])


main()
### BUGGY CODE ###

H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = []
index_w = []
for k in range(H):
  if counth[k] == maxh:
    index_h.append(k)
for k in range(W):
  if countw[k] == maxw:
    index_w.append(k)
ans = maxh + maxw - 1
for h in index_h:
  for w in index_w:
    if grid[h][w] == 0:
      ans += 1
      break
  else:
    continue
  break
print(ans)

### FIXED CODE ###

from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1
counth = deque(counth)
countw = deque(countw)

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False


maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)


if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  for K in kouho:
    if binary_search(bomb, K):
      continue
    else:
      ans += 1
      break
    
print(ans)
### BUGGY CODE ###

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

INF = 10 ** 16

dp = [INF] * N
dp[0] = 0

for i in range(1, N):
    for j in range(i - 1, max(i - 1 - K, -1), -1):
        dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]))

print(dp[N - 1])


### FIXED CODE ###

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

INF = 10 ** 16

dp = [INF] * N
dp[0] = 0

for i in range(1, N):
    for j in range(i - 1, max(i - 1 - K, -1), -1):
        dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]))

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

import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]


xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            if nx>=0 and nx<H and ny>=0 and ny<W and cnt[nx][ny]==10**10:
                if li[nx][ny]=="@":
                    # print(nx,ny)
                    break
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()





### FIXED CODE ###

import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]
cnt2 = [[10**10 for _ in range(W)] for _ in range(H)]



xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            
            if nx>=0 and nx<H and ny>=0 and ny<W and li[nx][ny]==".":
                if cnt[nx][ny]!=10**10 and cnt[nx][ny]<cst+1:
                    break
                elif cnt[nx][ny]!=10**10:
                    continue
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()
### BUGGY CODE ###

def xgcd(a, b):
    if b == 0:
        g = a
        x = 1
        y = 0
        return g, x, y
    else:
        g, s, t = xgcd(b, a%b)
        x = t
        y = s - a//b*x
        return g, x, y

def invmod(a, p):
    _, x, _ = xgcd(a, p)
    if x < 0:
        x = x + p
    return x

def count_route(n):
  if n < 0:
    return 0
  res = 0
  for i in range(n//2+1):
    res += f[n - i] * inv[i] * inv[n - 2* i]
  return res%const
    
n, m = map(int, input().split())
const = 1000000007
#nまでの階乗をハッシュテーブルに格納する
f = [1 for i in range(n + 1)]
inv = [1 for i in range(n + 1)]
for i in range(1, n+1):
  f[i] = f[i - 1] * i
  inv[i] = invmod(f[i], const)
prev = 0
ans = 1
for i in range(m):
  m = int(input())
  ans = (ans * count_route(m - 1 - prev))%const
  prev = m + 1
  if ans == 0:
    break
ans = (ans * count_route(n - prev))%const
print(ans)

### FIXED CODE ###

def xgcd(a, b):
    if b == 0:
        g = a
        x = 1
        y = 0
        return g, x, y
    else:
        g, s, t = xgcd(b, a%b)
        x = t
        y = s - a//b*x
        return g, x, y

def invmod(a, p):
    _, x, _ = xgcd(a, p)
    if x < 0:
        x = x + p
    return x

def count_route(n):
  if n < 0:
    return 0
  res = 0
  for i in range(n//2+1):
    res += f[n - i] * inv[i] * inv[n - 2* i]
  return res%const
    
n, m = map(int, input().split())
const = 1000000007
#nまでの階乗をハッシュテーブルに格納する
f = [1 for i in range(n + 1)]
inv = [1 for i in range(n + 1)]
for i in range(1, n+1):
  f[i] = (f[i - 1] * i)%const
  inv[i] = invmod(f[i], const)
prev = 0
ans = 1
for i in range(m):
  m = int(input())
  ans = (ans * count_route(m - 1 - prev))%const
  prev = m + 1
  if ans == 0:
    break
ans = (ans * count_route(n - prev))%const
print(ans)
### BUGGY CODE ###

from functools import lru_cache


N, W = list(map(int, input().split(" ")))

l = []
for i in range(N):
	w, v = list(map(int, input().split(" ")))
	l.append((w, v))
    
@lru_cache(maxsize=1000000)
def dp(i, score, remaining_weight):
	if (i < 0):
		return score
	if remaining_weight >= l[i][0]:
		# on / off
		return max([dp(i - 1, score + l[i][1], remaining_weight - l[i][0]), dp(i - 1, score, remaining_weight)])
	else:
		return dp(i-1, score, remaining_weight)

print(dp(N-1, 0, W))

### FIXED CODE ###

N, W = list(map(int, input().split(" ")))
dp =  [[0] * (W+1) for _ in range(N+1)]
 
for i in range(0, N):
	weight, value = map(int, input().split(" "))
	for w in range(1, W+1):
		if w >= weight:
			dp[i + 1][w] = max([dp[i][w - weight] + value, dp[i][w]])
		else:
			dp[i + 1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
c = []
for i in range(n+1):
  c.append(s[:i].count("AC"))
  
for i in range(q):
  l,r = map(int,input().split())
  print(c[r]-c[l])

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
c = []
pre = ""
count = 0
for i in range(n):
  if pre == "A" and s[i] == "C":
    count += 1
  pre = s[i]
  c.append(count)
  
for i in range(q):
  l,r = map(int,input().split())
  print(c[r-1]-c[l-1])
### BUGGY CODE ###

n, c = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(n)]

# for i in range(c):
#   for j in range(c):
#     for k in range(c):
#       d = D[i][j] + D[j][k]
#       if D[i][k] > d:
#         D[i][k] = d

sum_d = [[0] * c for i in range(3)]

for i in range(n):
  for j in range(n):
    for k in range(c):
      sum_d[(i+j)%3][k] += D[C[i][j]-1][k]
      
max_d = 1000 * (n//3+1)
ans = max_d * n**2
      
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j != k != i:
        ans = min(ans, sum_d[0][i] + sum_d[1][j] + sum_d[2][k])
        
print(ans)

### FIXED CODE ###

n, c = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(n)]

# for i in range(c):
#   for j in range(c):
#     for k in range(c):
#       d = D[i][j] + D[j][k]
#       if D[i][k] > d:
#         D[i][k] = d

sum_d = [[0] * c for i in range(3)]
mod_c = [[0] * c for i in range(3)]

for i in range(n):
  for j in range(n):
      mod_c[(i+j)%3][C[i][j]-1] += 1

for i in range(c):
    for j in range(c):
        for k in range(3):
            sum_d[k][j] += D[i][j] * mod_c[k][i]
      
max_d = 1000 * (n//3+1)
ans = max_d * n**2
      
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j != k != i:
        ans = min(ans, sum_d[0][i] + sum_d[1][j] + sum_d[2][k])
        
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = defaultdict(list)
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)

        return 0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].add(b-1)
        G[b-1].add(a-1)

    weights = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        weights[p-1] += x

    ans = [0] * N
    ans[0] = weights[0]
    visited = [False] * N
    def f(a, node):
        visited[node] = True
        for nt in G[node]:
            if visited[nt]:
                continue
            b = a + weights[nt]
            ans[nt] = b
            f(b, nt)
        return  0

    f(weights[0], 0)
    return ' '.join(map(str, ans))


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


n, k = (int(x) for x in input().split())

while n > k:
    n = n - k

temp = n

n = n - k

if abs(temp) < abs(n) :
    print(abs(temp))
else:
    print(abs(n))

### FIXED CODE ###


n, k = (int(x) for x in input().split())

mod = n % k
kari = mod - k

if abs(mod) < abs(kari) :
    print(abs(mod))
else:
    print(abs(kari))
### BUGGY CODE ###

def gcd(a, b): 
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

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

def main():
    n=int(input())
    a=1
    b=1
    for _ in range(n):
        x,y = map(int,input().split())
        x1=x
        y1=y
        while x1<a or y1<b:
            x1+=x
            y1+=y
        a=x1
        b=y1
    print(a+b)
        

if __name__ == "__main__":
    main()


### FIXED CODE ###

def gcd(a, b): 
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

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

def main():
    n=int(input())
    a=1
    b=1
    for _ in range(n):
        x,y = map(int,input().split())
        n=a//x
        m=b//y
        if a%x!=0:
            n+=1
        if b%y!=0:
            m+=1
        a=max(n,m)*x
        b=max(n,m)*y
    print(a+b)
        

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

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N)

for i in range(M):
    A,B = map(int,input().split())
    uf.union(A-1,B-1)

group = list(uf.all_group_members().values())
ans = 0
for i in range(len(group)):
    ans = max(ans,len(group[i]))
print(ans)

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N)

for i in range(M):
    A,B = map(int,input().split())
    uf.union(A-1,B-1)

ans = 0
for i in range(N):
    ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

k = int(input())

cnt = 1
mod = 7

for i in range(k):
    if mod%k == 0:
        break
    cnt+=1
    mod = mod*10 + 7

if mod%k == 0:
    print(cnt)
else:
    print(-1)

### FIXED CODE ###

k = int(input())

cnt = 1
mod = 7

for i in range(k):
    if mod%k == 0:
        break
    cnt+=1
    mod = (mod*10 + 7)%k

if mod%k == 0:
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
# TLE
duplication = {}
ans = 0
for x in A:
    if x in duplication:
        continue
    count = A.count(x)
    if count > 1:
        duplication[x] = count
        ans += count*(count-1)//2
for x in A:
    if x not in duplication:
        print(ans)
    else:
        print(ans -duplication[x]+1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# TLE
def test():
    duplication = {}
    ans = 0
    for x in A:
        if x in duplication:
            continue
        count = A.count(x)
        if count > 1:
            duplication[x] = count
            ans += count*(count-1)//2
    for x in A:
        if x not in duplication:
            print(ans)
        else:
            print(ans -(duplication[x]-1))
from collections import defaultdict

sum = 0
count_dic = defaultdict(int)
for x in A:
    count_dic[x] +=1
for v in count_dic.values():
    sum += v*(v-1)//2
for x in A:
    print(sum -(count_dic[x]-1))
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
STX = [[int(x) for x in input().split()] for _ in range(N)]
EVENT = []
for s, t, x in STX:
    EVENT.append((s-x, 1, x))
    EVENT.append((t-x, 0, x))

for i in range(Q):
    d = int(input())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()


STOP = set()
h = []
for t, op, x in EVENT:
    if not op:
        STOP.remove(x)
    elif op & 1:
        STOP.add(x)
        heappush(h, x)
    else:
        while h and h[0] not in STOP:
            heappop(h)
        ans[x] = h[0] if h else -1


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

n = int(input())
#a = [x for x in range(1, n+1)]
#print(sum(a) - n)

wa = 0
a = n+1
for i in range(n//2):
    wa+=(n+1)
if n % 2 == 1:
    wa+=(n+1)/2

print(int(wa-n))

### FIXED CODE ###

n = int(input())

wa = (n+1)*(n//2)
if n % 2 == 1:
    wa+=(n+1)//2

print(wa-n)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] + L[j] > L[k]:
                ans += 1
print(ans)


### FIXED CODE ###

# coding: utf-8
from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        ans += bisect_left(L, a+b) - 1 - j
print(ans)
### BUGGY CODE ###

if __name__=="__main__":
    N = int(input())
    l = list(map(int,input().split(" ")))
    v = []
    c = []
    count = 0
    for i in l:
          if i not in v:
              v.append(i)
              c.append(1)
          else:
              c[v.index(i)]+=1
    for j in range(len(v)):
        count+= c[j]-v[j] if c[j]>=v[j] else c[j]
    print(count)

### FIXED CODE ###

def main():
    N = int(input())
    l = list(map(int,input().split(" ")))
    dic = {}
    count = 0
    for i in l:
        try:
            dic[i] += 1
        except Exception:
            dic[i] = 1

    for j in dic.items():
        count += j[1] - j[0] if j[1] >= j[0] else j[1]
    print(count)


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

s = list(input())
t = list(input())
n = len(s)
m = len(t)
s1 = list(set(s))
t1 = list(set(t))
key = 0
for i in range(len(t1)):
    if t1[i] not in s1:
        key = 1
if key == 0:
    count = 0
    i = 0
    j = 0
    while j < m:
        if s[i] == t[j]:
            i = i + 1
            j = j + 1
        else:
            i = i + 1
        if i == n:
            count = count + 1
            i = 0
    print(count*n+i)
else:
    print("-1")

### FIXED CODE ###

import bisect
ai = [[] for i in range(26)]
s = list(input())
t = list(input())
n = len(s)
for i in range(n):
    ai[int(ord(s[i])-97)].append(i)
n2 = len(t)
count = 0
if len(ai[int(ord(t[0]))-97]) > 0:
    now = ai[int(ord(t[0]))-97][0]
    for i in range(1,n2):
        nex = int(ord(t[i]))-97
        n3 = len(ai[nex])
        if n3 == 0:
            count = 0
            now = -2
            break
        else:
            ni = bisect.bisect_right(ai[nex],now)
            #print(ni,count,now)
            if ni == n3:
                ni = 0
            if ai[nex][ni] > now:
                now = ai[nex][ni]
            else:
                count += 1
                now = ai[nex][ni]
    print(count*n+now+1)
else:
    print(-1)
### BUGGY CODE ###

import itertools

n = int(input())
s = list(input())

p = list(itertools.combinations(s, 3))
p = set(p)

print(len(p))


### FIXED CODE ###

n = int(input())
s = list(input())

li = [[] for _ in range(10)]

for i in range(n):
    t = int(s[i])
    li[t].append(i)

a = 0
b = 0
c = 0
cnt = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      b = 0
      a = 0
      
      if len(li[i]) > 0:
        a = li[i][0]
          
        for d in li[j]:
            if d > a:
                b = d
                break
        else:
            break
        
        for e in li[k]:
            if e > b:
                cnt += 1
                break
        

print(cnt)
### BUGGY CODE ###


def solve():
  s = input()
  n  = len(s)
  mod = 10**9+7
  reverses = s[::-1]
  if reverses[0] != "?":
    tmp = int(reverses[0])
    query = [0 for i in range(13)]
    query[tmp] += 1
  else:
    query = [0 for i in range(13)]
    for i in range(10):
      query[i] += 1
      
  digit = 1
  tmp = [0 for i in range(13)]
  for i in range(1,n):
    digit *= 10
    digit %= 13
    tmp = [0 for i in range(13)]
    
    if reverses[i] =="?":
      for k in range(10):
        for j in range(13):
          tmp[(k*digit + j)%13] += query[j]
      
    else:
      for j in range(13):
        tmp[(digit*int(reverses[i])+j)%13] += query[j]

    for i in range(13):
      tmp[i] %= mod
    query = tmp 
      
  print(query[5])
if __name__ == '__main__':
  solve()

### FIXED CODE ###

def solve():
  s = input()
  n  = len(s)
  mod = 10**9+7
  reverses = s[::-1]
  
  query = [0 for i in range(13)]
  if reverses[0] != "?":
    tmp = int(reverses[0])
    query = [0 for i in range(13)]
    query[tmp] += 1
  else:
    for i in range(10):
      query[i] += 1
  digit = 1
  
  for i in range(1,n):
    digit *= 10
    digit %= 13
    tmp = [0 for _ in range(13)]
    
    if reverses[i] =="?":
      for k in range(10):
        for j in range(13):
          num = k*digit
          num += j
          num %= 13
          tmp[num] += query[j]
      
    else:
      for j in range(13):
        num = digit*int(reverses[i])
        num += j
        num %= 13
        tmp[num] += query[j]

    for i in range(13):
      tmp[i] %= mod
    query = tmp 
      
  print(query[5])
solve()