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

import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

maximum = 100000
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if v and i >= l and i > 1 and i <= r and i % 2 == 1 and primes[(i + 1) // 2]:
            count += 1
    print(count)


### FIXED CODE ###

import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])
### BUGGY CODE ###

n,m=map(int,input().split())

candidate = []
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        if b in candidate:
            print('POSSIBLE')
            exit()
        else:
            candidate.append(b)
    if b==n:
        if a in candidate:
            print('POSSIBLE')
            exit()
        else:
            candidate.append(a)
print('IMPOSSIBLE')


### FIXED CODE ###

n,m=map(int,input().split())

from_1=[]
to_n=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        from_1.append(b)
    if b==n:
        to_n.append(a)

if len(set(from_1) & set(to_n)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N = int(input())
u,v,w = [0 for i in range(N-1)],[0 for i in range(N-1)],[0 for i in range(N-1)]
for i in range(N-1):
    u[i],v[i],w[i] = map(int,input().split())
res = [0 for i in range(N+1)]

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    index_num = [n for n, value in enumerate(u) if value == node]
    # print(index_num)
    for index in index_num:
        new_node = v[index]
        if new_node == p:
            continue
        if w[index] % 2 == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)

    index_num = [n for n, value in enumerate(v) if value == node]
    # print(index_num)
    for index in index_num:
        new_node = u[index]
        if new_node == p:
            continue
        if w[index] % 2 == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)

#tree 探索　
# vは頂点，ｐは親
dfs(1,-1,1)

# print(res[1:])
for i in range(1,N+1):
    print(res[i])


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys



mod = 10**9+7
sys.setrecursionlimit(mod)

N = int(input())
graph = [set() for i in range(N+1)]

for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w = w % 2
    graph[u].add((v,w))
    graph[v].add((u,w))


res = [None for i in range(N+1)]

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:
            pass
        else:
            if w == 1:dfs(new_node,node,1-color)
            else:dfs(new_node,node,color)
#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

for i in range(N):
    print(res[i])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
s=[0]*q
for i in range(q):
	b[i],c[i]=map(int,input().split())
f={}
for i in range(n):
	f.setdefault(a[i],[])
for i in range(n):
	f[a[i]].append(i)
#print(f)
for i in range(q):
	if b[i] in f:
		if c[i] in f:
			f[c[i]]=f[c[i]]+f[b[i]]
			f.pop(b[i])
		else:
			f.setdefault(c[i],[])
			f[c[i]]=f[c[i]]+f[b[i]]
			f.pop(b[i])
	#print(f)
	for g,h in f.items():
		#print(len(h)*g)
		s[i]=s[i]+len(h)*g
	print(s[i])


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
s=[0]*(q+1)
for i in range(q):
	b[i],c[i]=map(int,input().split())
f={}
for i in range(n):
	f.setdefault(a[i],0)
for i in range(n):
	f[a[i]]+=1
for g,h in f.items():
	#print(len(h)*g)
	s[0]=s[0]+h*g
#print(f)
for i in range(1,q+1):
	if b[i-1] in f:
		if c[i-1] in f:
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-f[b[i-1]]*b[i-1]
			#print(s[i])
			
			s[i]=s[i]+f[b[i-1]]*c[i-1]
			f.pop(b[i-1])
		else:
			f.setdefault(c[i-1],0)
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-f[b[i-1]]*b[i-1]
			#print(s[i])
			
			s[i]+=f[b[i-1]]*c[i-1]
			f.pop(b[i-1])
	#print(f)
	#for g,h in f.items():
		#print(len(h)*g)
		#s[i]=s[i]+len(h)*g
	else:
		s[i]=s[i-1]
	print(s[i])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

c = [[10**9 for _ in range(W)] for _ in range(H)]
que = deque()

for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      c[i][j] = 0
      que.append([i, j])

dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]      
      
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] == 10**9 and maze[nx][ny] ==".":
      maze[nx][ny] = "#"
      c[nx][ny] = c[p[0]][p[1]] + 1
      que.append([nx, ny])
max = 0
for i in range(H):
  for j in range(W):
    if max < c[i][j]:
      max = c[i][j]
print(max)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

c = [[10**9 for _ in range(W)] for _ in range(H)]
que = deque()

for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      c[i][j] = 0
      que.append([i, j])

dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]      
      
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] == 10**9 and maze[nx][ny] ==".":
      maze[nx][ny] = "#"
      c[nx][ny] = c[p[0]][p[1]] + 1
      que.append([nx, ny])
max = 0
for i in range(H):
  for j in range(W):
    if max < c[i][j]:
      max = c[i][j]
print(max)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        heapq.heappush(A_LIST, max(tmp, c))
print(sum(A_LIST))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))
### BUGGY CODE ###

import math

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a_ = a.copy()
    res = 0
    a_.pop(i)
    a_ = sorted(a_)
    a__ = set(a_)
    for j in a__:
        k = a_.count(j)
        if k != 1:
            res += math.factorial(k) // (math.factorial(k-2) * math.factorial(2))
    print(res)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
a_ = set(a)
x = Counter(a)
y = {i:x[i]*(x[i]-1)//2 for i in a_}

res = sum(y.values())
for i in a:
    t = x[i]
    t_ = y[i]
    print(res-t_+(t-1)*(t-2)//2)
### BUGGY CODE ###

N=int(input())
result=0
for i in range(N):
    result+=i

print(result)

### FIXED CODE ###

N=int(input())

result=(N-1)*(N)//2
print(result)
### BUGGY CODE ###

def napzak(w,v,limit):
    dp = [0]*(limit+1)
    for i in range(1,limit+1):
        for j,value in zip(w,v):
            if value<=j:
                continue
            if (i-j)>=0:
                dp[i] = max(dp[i],dp[i-j]+value-j)
    return dp[limit]+limit

n = int(input())
wa = list(map(int,input().split()))
wb = list(map(int,input().split()))

m = napzak(wa,wb,n)
ans = napzak(wb,wa,m)

print(ans)

### FIXED CODE ###

def napzak(w,v,limit):
    dp = [0]*(limit+1)
    wv = [(weight,value) for weight,value in zip(w,v) if value>weight]
    if wv == []:
        return limit
    for i in range(1,limit+1):
        for j,value in wv:
            if (i-j)>=0 and dp[i]<(dp[i-j]+value-j):
                dp[i] = dp[i-j]+value-j
    return dp[limit]+limit

n = int(input())
wa = list(map(int,input().split()))
wb = list(map(int,input().split()))

m = napzak(wa,wb,n)
ans = napzak(wb,wa,m)

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

N = int(input())
ns = [int(input()) for _ in range(N)]

primes = set()
def is_prime(n):
  if n in primes:
    return True

  for m in range(2, n):
    if is_prime(m) and n % m == 0:
      return False
  primes.add(n)
  return True

print(len([n for n in ns if is_prime(n)]))

### FIXED CODE ###

N = int(input())
ns = [int(input()) for _ in range(N)]

#primes = set()
#def is_prime(n):
#  if n in primes:
#    return True
#
#  for m in range(2, n):
#    if is_prime(m) and n % m == 0:
#      return False
#
#  primes.add(n)
#  return True

# Proof:
# if n < d ^ 2 and n mod d = 0;
# n = ad (a in N)
# ad < d ^ 2
# a < d
# QED

def is_prime(n):
  if n < 2: return False
  if n == 2: return True
  if n % 2 == 0: return False

  d = 3
  while d ** 2 <= n:
    if n % d == 0:
      return False
    d += 2
  return True

print(len([n for n in ns if is_prime(n)]))
### BUGGY CODE ###

n = int(input())
s=[]
for i in range(n):
    s.append(input())
list_s = []
for j in range(n):
    list_s.append(''.join(sorted(list(s[j]))))
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
unique_list = get_unique_list(list_s)

ans = []
for k in range(len(unique_list)):
    count = 0
    for l in range(n):
        if unique_list[k] == list_s[l]:
            count += 1
    ans.append(count * (count-1) // 2)

print(sum(ans))

### FIXED CODE ###

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

list_s = []
for j in range(n):
    #list_s.append(sorted(list(s[j])))
    list_s.append(''.join(sorted(s[j])))

m = {}
for i in range(n):
    if list_s[i] not in m:
        m[list_s[i]] = 1
    else:
        m[list_s[i]] += 1

def cmb(num):
    if num == 1:
        return 0
    elif num == 2:
        return 1
    else:
        return (num * (num-1) // 2)
  
count = 0
for k in m.keys():
        count += cmb( m[k] )


print(count)
### BUGGY CODE ###

from collections import deque

n, x, y = [int(x) for x in input().split()]
x -= 1
y -= 1
BIG = 65521
ans = [0] * n


def bfs(start_v):
    """ある始点からほかの全点に行くまでの最短距離を求める。"""
    qu = deque()
    qu_append = qu.append
    qu_popleft = qu.popleft
    qu_append(start_v)
    # 始点からvに移動するまでの最短距離: dist[v]
    dist = [BIG] * n

    def push(v, d):
        """始点からvまでの最短距離が算出されていないときに，その距離を保存し，
        キューに頂点vを追加する。"""
        if dist[v] != BIG:
            # 既に訪問済みで距離が求められている。
            return
        dist[v] = d
        qu_append(v)

    push(start_v, 0)

    while len(qu):
        v = qu_popleft()
        # 始点からvの次の頂点へ移動する距離。
        d = dist[v] + 1
        if v < n - 1:
            push(v + 1, d)
        if v > 0:
            push(v - 1, d)
        if v == x:
            push(y, d)
        if v == y:
            push(x, d)

    for i in range(n):
        ans[dist[i]] += 1


def main():
    for i in range(n):
        bfs(i)

    for i in range(1, n):
        print(ans[i] // 2)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

n, x, y = [int(x) for x in input().split()]
x -= 1
y -= 1
BIG = 65521
ans = {i: 0 for i in range(n)}


def bfs(start_v):
    """ある始点からほかの全点に行くまでの最短距離を求める。"""
    qu = deque()
    qu_append = qu.append
    qu_popleft = qu.popleft
    qu_append(start_v)
    # 始点からvに移動するまでの最短距離: dist[v]
    dist = [BIG] * n

    def push(v, d):
        """始点からvまでの最短距離が算出されていないときに，その距離を保存し，
        キューに頂点vを追加する。"""
        if dist[v] != BIG:
            # 既に訪問済みで距離が求められている。
            return
        dist[v] = d
        qu_append(v)

    push(start_v, 0)

    while len(qu):
        v = qu_popleft()
        # 始点からvの次の頂点へ移動する距離。
        d = dist[v] + 1
        if v < n - 1:
            push(v + 1, d)
        if v > 0:
            push(v - 1, d)
        if v == x:
            push(y, d)
        if v == y:
            push(x, d)

    for i in range(n):
        if dist[i] != 0:
            ans[dist[i]] += 1


def main():
    for i in range(n):
        bfs(i)

    for i in range(1, n):
        print(ans[i] // 2)


if __name__ == '__main__':
    main()

# TLE
### BUGGY CODE ###

n=int(input())
import collections
c=collections.Counter()
from math import gcd
mod=10**9+7
for _ in range(n):
    a,b=map(int,input().split())
    g=abs(gcd(a,b))
    if g==0:
        g=1
    a//=g
    b//=g
    c[(a,b)]+=1
ans=1
s=set()
for i,j in c:
    if (i,j)==(0,0):
        continue
    if (i,j) not in s:
        s.add((i,j))
        s.add((-i,-j))
        s.add((-j,i))
        s.add((j,-i))
        ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
print((ans-1+c[(0,0)])%mod)

### FIXED CODE ###

import collections
from math import gcd
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

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

import math
k = int(input())
total = 0
gcd_ab = 0

for a in range(1,k+1):
  for b in range(1, k+1):
    for c in range(1,k+1):
      gcd_ab = math.gcd(a,b)
      total += math.gcd(gcd_ab, c)

print(total)

### FIXED CODE ###

import math
k = int(input())
total = 0
gcd_ab = 0

for a in range(1,k+1):
  for b in range(1, k+1):
    for c in range(1,k+1):
      gcd_ab = math.gcd(a,b)
      total += math.gcd(gcd_ab, c)

print(total)
### BUGGY CODE ###

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

ok, ng = a[-1]*f[0], -1
while ok-ng > 1:
	x = (ok+ng)//2
	tmp = 0
	for i in range(n):
		tmp += max(0, a[i] - x//f[i])
	if tmp > k:
		ng = x
	else:
		ok = x
print(ok)

### FIXED CODE ###

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

ok, ng = a[-1]*f[0], -1
while ok-ng > 1:
	x = (ok+ng)//2
	tmp = 0
	for i in range(n):
		tmp += max(0, a[i] - x//f[i])
	if tmp > k:
		ng = x
	else:
		ok = x
print(ok)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
l = len(s)
ans = 0
for i in range(l):
    for j in range(i + 1, l + 1):
        n = int(s[i:j])
        if sum(list(map(int, str(n)))) % 3 == 0:
            if int(s[i:j]) % 673 == 0:
                ans += 1
print(ans)


### FIXED CODE ###

s = input()
l = len(s)
mod = [1] + [0 for _ in range(2019)]
ml = [0 for _ in range(l + 1)]
ans = 0

tmp = 0
for idx, degit in enumerate(s[::-1]):
    m = int(degit) * pow(10, idx, 2019)
    m = (m + tmp) % 2019
    tmp = m
    ans += mod[m]
    mod[m] += 1

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

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
ans = 0
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    A_new = A[:i] + A[i+1:]
    ans = max(ans, gcd(*A_new))
print(ans)


### FIXED CODE ###

import fractions

N = int(input())
a = list(map(int,input().split()))
a1 = [0] * N
a2 = [0] * N
a1[0] = 0
a2[-1] = 0
a1[1] = a[0]
a2[-2] = a[-1]
ans = 0
for i in range(2,N):
    a1[i] = fractions.gcd(a1[i-1], a[i-1])
    a2[-(i+1)] = fractions.gcd(a2[-i], a[-i])
for a,b in zip(a1, a2):
    if a == 0:
        ans = max(ans, b)
    elif b == 0:
        ans = max(ans, a)
    else:
        ans = max(ans, fractions.gcd(a, b))
print(ans)
### BUGGY CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def dfs(a, x, y):
  if len(x)+len(y)==len(a):
    if len(x)==0 or len(y)==0:
      a_ = a[0]
      for i in range(1, len(a)):
        a_ *= a[i]
      return a_ + 1
    else:
      x_ = x[0]
      y_ = y[0]
      for i in range(1, len(x)):
        x_ *= x[i]
      for i in range(1, len(y)):
        y_ *= y[i]
      return x_ + y_
  res1 = dfs(a, x + [a[len(x)+len(y)]], y)
  res2 = dfs(a, x, y + [a[len(x)+len(y)]])
  return min(res1, res2)

n = int(input())
primes = prime_factorize(n)
print(dfs(primes, [], [])-2)

### FIXED CODE ###

n = int(input())
ans = n - 1
for i in range(1, int(n**0.5)+2):
  if n%i!=0:
    continue
  ans = min(ans, i + n//i - 2)
print(ans)
### BUGGY CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            for k in range(1, n + 1):
                if i != j and i != k and j != k and i + j + k == x:
                    ans += 1
    print(ans // 6)

### FIXED CODE ###

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B "How many ways?" ????§£??????
# 
import itertools
while True:
    n, x = map(int, input().split())
    if not n:
        break
    print(list(map(sum, itertools.combinations(range(1, n + 1), 3))).count(x))
### BUGGY CODE ###

from collections import defaultdict

if __name__ == "__main__":
    n = int(input())
    s = input()

    rgb = defaultdict(list)

    for i in range(n):
        if s[i] == 'R':
            rgb[0].append(i)
        elif s[i] == 'G':
            rgb[1].append(i)
        else:
            rgb[2].append(i)

    ans = len(rgb[0]) * len(rgb[1]) * len(rgb[2])

    for r in rgb[0]:
        for g in rgb[1]:
            tmp = sorted([r, g])
            if tmp[0] - (tmp[1]-tmp[0]) in rgb[2]:
                ans -= 1
            if tmp[1] + (tmp[1]-tmp[0]) in rgb[2]:
                ans -= 1
            if (tmp[1]+tmp[0]) % 2 == 0 and (tmp[1]+tmp[0])//2 in rgb[2]:
                ans -= 1

    print(ans)


### FIXED CODE ###

from collections import defaultdict

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

rgb = defaultdict(list)
blue = defaultdict(int)

for i in range(n):
    if s[i] == 'R':
        rgb[0].append(i)
    elif s[i] == 'G':
        rgb[1].append(i)
    else:
        blue[i] = i

ans = len(rgb[0]) * len(rgb[1]) * len(blue)

for r in rgb[0]:
    for g in rgb[1]:
        tmp = sorted([r, g])
        if tmp[0] - (tmp[1]-tmp[0]) in blue:
            ans -= 1
        if tmp[1] + (tmp[1]-tmp[0]) in blue:
            ans -= 1
        if (tmp[1]+tmp[0]) % 2 == 0 and (tmp[1]+tmp[0])//2 in blue:
            ans -= 1

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

def readinput():
    s=input()
    return s

def printTbl(tbl):
    for l in tbl:
        print(l)

def main(s):
    MOD=10**9+7

    Rtbl=[]
    for _ in range(10):
        Rtbl.append([0]*13)
    for i in range(1,10):
        for j in range(13):
            Rtbl[i][j]=(Rtbl[i-1][j]+j)%13
    #printTbl(Rtbl)

    n=len(s)
    p0=0
    q=[]
    for i in range(n):
        if s[i]!='?':
            p0=(p0*10+int(s[i]))%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
        else:
            p0=(p0*10)%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
            q.append(1)
    #print(p0,q)

    nq=len(q)
    if nq==0:
        if p0==5:
            return 1
        else:
            return 0

    Ptbl=[]
    for _ in range(13):
        Ptbl.append([0]*nq)
    q0=q[0]
    for i in range(10):
        Ptbl[(Rtbl[i][q0]+p0)%13][0]+=1
    for j in range(1,nq):
        qj=q[j]
        for n in range(10):
            for i in range(13):
                if Ptbl[i][j-1]>0:
                    ii=(i+Rtbl[n][qj])%13
                    Ptbl[ii][j]=(Ptbl[ii][j]+Ptbl[i][j-1])%MOD
    #printTbl(Ptbl)
    return Ptbl[5][nq-1]

if __name__=='__main__':
    s=readinput()
    ans=main(s)
    print(ans)


### FIXED CODE ###

def readinput():
    s=input()
    return s

def printTbl(tbl):
    for l in tbl:
        print(l)

def main(s):
    MOD=10**9+7

    Rtbl=[]
    for _ in range(10):
        Rtbl.append([0]*13)
    for i in range(1,10):
        for j in range(13):
            Rtbl[i][j]=(Rtbl[i-1][j]+j)%13
    #printTbl(Rtbl)

    n=len(s)
    p0=0
    q=[]
    for i in range(n):
        if s[i]!='?':
            p0=(p0*10+int(s[i]))%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
        else:
            p0=(p0*10)%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
            q.append(1)
    #print(p0,q)

    nq=len(q)
    if nq==0:
        if p0==5:
            return 1
        else:
            return 0

    Ptbl=[]
    for _ in range(13):
        Ptbl.append([0]*nq)
    q0=q[0]
    for i in range(10):
        Ptbl[(Rtbl[i][q0]+p0)%13][0]+=1
    for j in range(1,nq):
        qj=q[j]
        for n in range(10):
            for i in range(13):
                if Ptbl[i][j-1]>0:
                    ii=(i+Rtbl[n][qj])%13
                    Ptbl[ii][j]=(Ptbl[ii][j]+Ptbl[i][j-1])%MOD
    #printTbl(Ptbl)
    return Ptbl[5][nq-1]

def main2(s):
    MOD=10**9+7
    dp=[]
    n=len(s)
    for _ in range(13):
        dp.append([0]*(n+1))
    dp[0][0]=1
    for i in range(n):
        c=s[i]
        for j in range(13):
            for k in range(10):
                if c!='?' and c!=str(k):
                   continue
                jj=(j*10+k)%13
                dp[jj][i+1]=(dp[jj][i+1]+dp[j][i])%MOD
    return dp[5][n]

if __name__=='__main__':
    s=readinput()
    ans=main2(s)
    print(ans)
### BUGGY CODE ###

from sys import stdin

def main():
  N = int(input())
  P = stdin.readline().rstrip().split()
  # print(P)
  ans = 1
  for a in P:
    ans *= int(a)
  if ans > 1000000000000000000:
    print(-1)
    return
  print(ans)

main()


### FIXED CODE ###

from sys import stdin

def main():
  N = int(input())
  P = stdin.readline().rstrip().split()
  if '0' in P:
    print(0)
    return
  # print(P)
  ans = 1
  for a in P:
    ans *= int(a)
    if ans > 1000000000000000000:
      print(-1)
      return
  print(ans)

main()