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

import time
import math
import collections

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table



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

factors = collections.Counter(prime_decomposition(M))
num_pattern = 1;
for exponent in factors.values():
    tmp_num_pattern = math.factorial(exponent + N -1) \
                        // (math.factorial(exponent)*math.factorial(N-1))  
    num_pattern = num_pattern * int(tmp_num_pattern)
    
print(num_pattern%(10**9+7))

### FIXED CODE ###

import time
import collections
import scipy.misc

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

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

factors = collections.Counter(prime_decomposition(M))
t_elps = time.time()
#print(f"{t_elps - t_strt} [sec]")
num_pattern = 1;

for exponent in factors.values():
    tmp_num_pattern = scipy.misc.comb(exponent + N -1, N-1, exact = True) 
    num_pattern = num_pattern * int(tmp_num_pattern)
    
print(num_pattern%(10**9+7))
### BUGGY CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[]
while (j<len(x)-1):
  if (x[j]=="A"):
    if (x[j+1]=="C"):
      s.append(1)
      s.append(0)
      j+=1
    else:s.append(0)
  else:s.append(0)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][0]-1:a[i][1]-1]
  answer=0
  for j in range(len(p)):
    if p[j]==1:answer+=1
  print(answer)





### FIXED CODE ###

N,Q=(int(i) for i in input().split())
x=input()
a=[]

j=0
s=[0]
t=0
while (j<N-1):
  if (x[j]=="A") and (x[j+1]=="C"):
    t+=1
    s.append(t)
  else:s.append(t)
  j+=1
for i in range(0,Q):
  a.append([int(j) for j in input().split()])
  p=s[a[i][1]-1]-s[a[i][0]-1]
  print(p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n,q = map(int,input().split())
ki = [[]for _ in range(n)]
def dfs(now,last ,add):
    for next in ki[now]:
        if next == last:continue
        cnt[next] += add 
        dfs(next,now,cnt[next])

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
cnt = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    p-=1
    cnt[p]+=x
dfs(0,-1,cnt[0])
print(*cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N,Q = map(int,input().split())
 
AB = [[int(x) for x in input().split()] for _ in range(N-1)] 
PX = [[int(x) for x in input().split()] for _ in range(Q)]

ki = [[]for _ in range(N)]
for a,b in AB:
    a-=1
    b-=1
    ki[a].append(b)
    ki[b].append(a)
point = [0]*(N)
for p,x in PX:
    p-=1
    point[p]+=x
def dfs(now, last ,add):
    point[now]+= add
    for x in ki[now]:
        if (x == last):continue
        dfs(x,now,point[now])
dfs(0,0,0)
print(*point)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)

prev = [None for _ in range(n)]
dist = [float('inf') for _ in range(n)]


def dfs(start):
    for n_r in edge[start]:
        if dist[n_r] > dist[start] + 1:
            dist[n_r] = dist[start] + 1
            prev[n_r] = start
        else:
            continue
        dfs(n_r)


dist[0] = 0
dfs(0)
if None in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)


### FIXED CODE ###

import heapq


def dijkstra_heap(s):
    d = [float("inf")] * n
    prev = [float("inf")] * n
    d[s] = 0
    edgelist = [[d[s], s]]
    heapq.heapify(edgelist)

    while edgelist:
        dis, v = heapq.heappop(edgelist)
        if d[v] < dis:
            continue

        for e in edge[v]:
            if d[e] > dis + 1:
                d[e] = dis + 1
                heapq.heappush(edgelist, [dis + 1, e])
                prev[e] = v
    return d, prev


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

edge = [[] for i in range(n)]
for i in range(w):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    edge[y].append(x)
d, prev = dijkstra_heap(0)

if float('inf') in prev[1:]:
    print('No')
else:
    print('Yes')
    for i in prev[1:]:
        print(i + 1)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
D = []
for _ in range(a):
    D.append(1)
for _ in range(b):
    D.append(0)
for _ in range(c):
    D.append(-1)
c = 0
for i in range(k):
    c += D[i]

print(c) 

### FIXED CODE ###

a, b, c, k = map(int, input().split())
if k <= a:
    print(k)
if a < k <= a + b:
    print(a)
if a + b < k:
    d = 2*a + b - k
    print(d)
### BUGGY CODE ###

S = input()
S = S[::-1]
divide = list(map(lambda phrase:phrase[::-1], ['dream', 'dreamer', 'erase', 'eraser']))

flag = False
i = 0
while i != len(S):
    for d in divide:
        if S[i:i+len(d)] == d:
            flag = True
            i += len(d)
            break

    if flag == False:
        break

print('YES' if flag else 'NO')

### FIXED CODE ###

S = input()
S = S[::-1]
divide = list(map(lambda phrase:phrase[::-1], ['dream', 'dreamer', 'erase', 'eraser']))

flag = False
i = 0
while i != len(S):
    flag = False
    for d in divide:
        if S[i:i+len(d)] == d:
            flag = True
            i += len(d)
            break

    if flag == False:
        break

print('YES' if flag else 'NO')
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
num = []
for i in a:
    if i in num:
        num.remove(i)
    else:
        num.append(i)
print(len(num))

### FIXED CODE ###

import collections
n = int(input())
a = [int(input()) for _ in range(n)]
A = collections.Counter(a)
ans = 0
for i in A.values():
    if i % 2 != 0:
        ans += 1
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
def t(s):
  return [[s[i][j] for i in range(len(s))] for j in range(len(s[0]))]
def calc(s):
  res = []
  for v in s:
    v.append('-')
    tmp = []
    nc = ''
    nn = 0
    for c in v:
      if nc == '':
        nc = c
        nn += 1
        continue
      if nc == c:
        nn += 1
        continue
      else:
        if nc == '#':
          tmp = tmp + [0 for _ in range(nn)]
        else:
          tmp = tmp + [nn for _ in range(nn)]
        nc = c
        nn = 1
    res.append(tmp)
  return res

tate = t(calc(t(S)))
yoko = calc(S)
print(max([tate[i][j] + yoko[i][j] - 1 for i in range(h) for j in range(w)]))

### FIXED CODE ###

h, w = map(int, input().split())
S = [input() for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

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

j = 1000000000000000000

ans = 1

for i in range(n):
    ans *=  An[i]


if ans <= j:
    print(ans)
    
else :
    print('-1')



### FIXED CODE ###


n = int(input())
An = [int(x) for x in input().split()]
An.sort(reverse=True)

if 0 in An:
    print(0)
    exit()

j = 10 ** 18
ans = 1
for i in range(n):
    if ans > j:
        print(-1)
        quit()
    ans *= An[i]

if ans > j :
    print(-1)
    
else :
    print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
if N == 1:
    for _ in range(Q):
        v, w = map(int, input().split())
        print(min(v, w))
else:
    L = [1]
    aa = 1
    def ch(k):
        return (k-2)//N+1
    
    def chh(a, b):
        if a == b:
            return a
        
        if a > b:
            a, b = b, a
        
        return chh(a, ch(b))
        
    for _ in range(Q):
        v, w = map(int, input().split())
        print(chh(v, w))


### FIXED CODE ###

N, Q = map(int, input().split())
if N == 1:
    for _ in range(Q):
        v, w = map(int, input().split())
        print(min(v, w))
else:
    L = [1]
    aa = 1
    def ch(k):
        return (k-2)//N+1
    
    def chh(a, b):
        if a == b:
            return a
        
        if a > b:
            a, b = b, a
        
        return chh(a, ch(b))
        
    for _ in range(Q):
        v, w = map(int, input().split())
        print(chh(v, w))
### BUGGY CODE ###

N = input()
li = list(map(int,input().split()))
n = 1

for i in li:
    n *= i

if n > 1000000000000000000:
    print("-1")
else:
	print(n)

### FIXED CODE ###

N = input()
l = list(map(int,input().split()))
li = sorted(l)
n = 1

for i in li:
    n *= i
    if n > 1000000000000000000:
        break

if n > 1000000000000000000:
    print("-1")
else:
	print(n)
### BUGGY CODE ###

N=int(input())
L=list(int(x) for x in input().split())
sum=1
for i in range(N):
	sum=sum*L[i]
if sum > 10**18:
	print("-1")
else:
	print(sum)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
if 0 in L:
	print(0)
	exit()
sum=1
for i in range(N):
	sum=sum*L[i]
	if sum > 10**18:
		print(-1)
		exit()
print(sum)
### BUGGY CODE ###

import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
B, C = zip(*[list(map(int, input().split())) for _ in range(M)])

heap = A
heapq.heapify(heap)


for b, c in zip(B, C):
    for _ in range(b):
        if heap[0] < c:
            heapq.heapreplace(heap, c)
        else:
            break

print(sum(heap))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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

A.sort()
CB.sort()

ans = 0
for _ in range(N):
    a = A[-1] if A else -INF
    c, b = CB[-1] if CB else (-INF, -INF)
    if a > c:
        ans += a
        A.pop()
    else:
        ans += c
        CB[-1][1] -= 1
        if CB[-1][1] <= 0:
            CB.pop()
print(ans)
### BUGGY CODE ###

S = input()[::-1]
P = 13
qs = [0]*13
tmp = 1
rest = 0
for i, s in enumerate(S):
    if s == '?':
        qs[tmp] += 1
    else:
        rest = (rest + int(s) * tmp) % P
    tmp = (tmp * 10) % P

dp = [0] * 13
dp[rest] = 1
for i, cnt in enumerate(qs):
    for _ in range(cnt):
        dp_new = [0]*13
        for j in range(10):
            tmp = (i * j) % P
            for k in range(P):
                dp_new[(k + tmp) % P] += dp[k]
        dp = dp_new
print(dp[5]%int(1e9+7))


### FIXED CODE ###

S = input()[::-1]
P = 13
qs = [0]*13
tmp = 1
rest = 0
for i, s in enumerate(S):
    if s == '?':
        qs[tmp] += 1
    else:
        rest = (rest + int(s) * tmp) % P
    tmp = (tmp * 10) % P

dp = [0] * 13
dp[rest] = 1
for i, cnt in enumerate(qs):
    for _ in range(cnt):
        dp_new = [0]*13
        for j in range(10):
            tmp = (i * j) % P
            for k in range(P):
                dp_new[(k + tmp) % P] = (dp_new[(k + tmp) % P] + dp[k])%int(1e9+7)
        dp = dp_new
print(dp[5]%int(1e9+7))
### BUGGY CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

from functools import reduce
max_val = reduce(gcd, a[1:])
for i in range(1, N):
    tmp = a[i]
    a[i] = a[0]
    val = reduce(gcd, a)
    if max_val < val:
        max_val = val
        
    a[i] = tmp
print(max_val)

### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

L = []
for i in range(len(a)):
    if i==0:
        L.append(None)
    elif i ==1:
        L.append(a[i-1])
    else:
        L.append(gcd(L[-1], a[i-1]))
        
R = []
for i in range(len(a)):
    if i==0:
        R.append(None)
    elif i ==1:
        R.append(a[-i])
    else:
        R.append(gcd(R[-1], a[-i]))
R = R[::-1]


max_val = 0
for r, l in zip(L,R):
    if r==None:
        val = l
    elif l==None:
        val = r
    else:
        val = gcd(r, l)
        
    if val > max_val:
        max_val = val
print(max_val)
### BUGGY CODE ###

n,m = map(int,input().split())
l = list(map(int,input().split()))
dp = [0]+ [100000000000]*(n-1)

for i in range(1,n):
    
    for j in range(1,m+1):
        if i-j >= 0:
            dp[i] = min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
    
print(dp[n-1])

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    l = list(map(int,input().split()))
    dp = [0]+ [100000000000]*(n-1)

    for i in range(1,n):
        
        for j in range(1,m+1):
            if i-j >= 0:
                dp[i] = min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
        
    print(dp[n-1])

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

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
ans = []
for i in reversed(range(n)):
    if A[i]:
        ans.append(i+1)
        tmp = 1
        n = i+1
        while tmp*tmp <= n:
            if n%tmp == 0:
                A[tmp-1] ^= 1
                if tmp != n//tmp:
                    A[n//tmp-1]^=1
            tmp += 1
if len(ans) > 0:
    print(len(ans))
    print(*ans)
else:
    print(0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
ans = []
for i in reversed(range(n)):
    if A[i]:
        ans.append(i+1)
        tmp = 1
        n = i+1
        while tmp*tmp <= n:
            if n%tmp == 0:
                A[tmp-1] ^= 1
                if tmp != n//tmp:
                    A[n//tmp-1]^=1
            tmp += 1
if len(ans) > 0:
    print(len(ans))
    print(*ans)
else:
    print(0)
### BUGGY CODE ###

from sys import stdin
from collections import deque
from collections import Counter
N,X,Y = [int(x) for x in stdin.readline().rstrip().split()] 
ans = Counter()

for k in range(1,N+1):
    dist = [0] + [10**9]*(N)
    visited = [False for i in range(N+1)]
    visit_p = deque()
    visit_p.append((k,0))

    while visit_p:
        #print(visit_p)
        node,cnt = visit_p.popleft()
        dist[node] = min(cnt,dist[node])

        if node == X:
            #print(node,cnt,"s")
            if not visited[Y]:
                visit_p.append((Y,cnt+1))
                visited[Y] = True

        if node == Y:
            #print(node,cnt,"s")
            if not visited[X]:
            #ans[cnt+1] += 1
                visit_p.append((X,cnt+1))
                visited[X] = True
        #print(visit_p,"e")   
        for d in [-1,1]:
            if node + d < 1 or node + d > N:
                continue
            if visited[node+d]:
                continue
            #print(node+d,cnt,"e")
            #ans[cnt+1] += 1
            visited[node+d] = True
            visit_p.append((node+d,cnt+1))
        
    ans += Counter(dist)
    
for i in range(1,N):
    print(ans[i]//2)

### FIXED CODE ###

from sys import stdin
from collections import deque
from collections import Counter
N,X,Y = [int(x) for x in stdin.readline().rstrip().split()] 
ans = Counter()

for k in range(1,N+1):
    dist = [0] + [10**9]*(N)
    visited = [False for i in range(N+1)]
    visit_p = deque()
    visit_p.append((k,0))

    while visit_p:
        #print(visit_p)
        node,cnt = visit_p.popleft()
        dist[node] = min(cnt,dist[node])

        if node == X:
            #print(node,cnt,"s")
            if not visited[Y]:
                visit_p.append((Y,cnt+1))
                visited[Y] = True

        if node == Y:
            #print(node,cnt,"s")
            if not visited[X]:
            #ans[cnt+1] += 1
                visit_p.append((X,cnt+1))
                visited[X] = True
        #print(visit_p,"e")   
        for d in [-1,1]:
            if node + d < 1 or node + d > N:
                continue
            if visited[node+d]:
                continue
            #print(node+d,cnt,"e")
            #ans[cnt+1] += 1
            visited[node+d] = True
            visit_p.append((node+d,cnt+1))
        
    ans += Counter(dist)
    
for i in range(1,N):
    print(ans[i]//2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i == 2:
        return True
    p = 2
    tmp = i ** 0.5
    while i != 1:
        if i % p == 0:
            return False
        elif p > tmp:
            return True
        else:
            p += 1
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        if left % 2 == 1:
            tmpl = 0
        else:
            tmpl = -1 * self.tree[left-1]
            left -= 1

        if right % 2 == 1:
            tmpr = self.tree[right]
            right -= 1
        else:
            tmpr = 0
        # print(left, right)
        return tmpl + tmpr + self.sum_find((left-1)//2, (right-1)//2)
    
    def make_sum(self):
        for i in reversed(range(self.bottom)):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


def inpl(): return list(map(int, input().split()))

Q = int(input())
query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for l, r in query:
    print(rsq.sum_find(l, r, first=True))

### FIXED CODE ###

def isPrime(i):
    if i < 2:
        return False
    elif i == 2:
        return True
    elif i % 2 == 0:
        return False
    for j in range(3, int(i**0.5)+1, 2):
        if i % j == 0:
            return False
    return True

def inpl(): return list(map(int, input().split()))

Q = int(input())
# query = [inpl() for i in range(Q)]
N = 10 ** 5


prime = [True] * (N+1)
prime[0] = False
prime[1] = False
for i in range(2, N+1):
    if prime[i] is False:
        continue
    
    tmp = i * 2
    while tmp <= N:
        prime[tmp] = False
        tmp += i

dst = [0] * (N+1)
for i in range(1, N+1):
    dst[i] = dst[i-1] + int(prime[i] and prime[(i+1)//2])

# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print(dst[r]-dst[l-1])
### BUGGY CODE ###

import math
N = int(input())
ans = 0
if N > 10**3:
    upper = int(math.sqrt(N/6)) + 1
else:
    upper = int(math.sqrt(N))
for n in range(1, N+1):
    ans = 0
    for x in range(1, upper):
        for y  in range(1, upper):
            for z in range(1, upper):
                v = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if  v == n:
                    ans += 1
                    #print((x, y, z))
                elif v > n:
                    break
    print(ans)

### FIXED CODE ###

import math
N = int(input())
ans = 0
num = {i:0 for i in range(1, N+1)}
upper = int(math.sqrt(N)) + 1
for x in range(1, upper):
    for y  in range(1, upper):
        z = 1
        v = x**2 + y**2 + z**2 + x*y + y*z + z*x
        if v > N:
            break
        for z in range(1, upper):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v in num.keys():
                num[v] += 1
            if v > N:
                break
for n in range(1, N+1):
    print(num[n])
### BUGGY CODE ###

N = int(input())

num = 1
for i in range(1, N+1):
  	num = num * i

if num < (10**9 + 7):
  print(num)
else:
  print(num % (10**9 + 7))

### FIXED CODE ###

N = int(input())

num = 1
for i in range(1, N+1):
  	num = i * num % (10**9 + 7)

print(num)
### BUGGY CODE ###

import numpy as np

S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = np.zeros(N)
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
for i in range(len(S) - 1, -1, -1):
    nextDP = np.zeros(N)
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP
 
print(int(DP[5]))
 
 

### FIXED CODE ###

S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = [0] * N
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
for i in range(len(S) - 1, -1, -1):
    nextDP = [0] * N
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP[:]
 
print(DP[5])
 
"""
??2??5

"""