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

from functools import reduce
from operator import mul
import math
 
def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under
n = int(input())
l = list(map(int, input().split()))
d = {}
s_sum = {}
s_ans = {}
s = list(set(l))
m = 0
for i in range(len(s)):
    v = l.count(s[i])
    d[s[i]] = v
    if v > 1:
        a = cmb(v, 2)
        s_ans[s[i]] = a
        m += a
    else:
        s_ans[s[i]] = 0
for i in range(len(l)):
    if not d[l[i]] > 1:
        print(m)
    elif l[i] in s_sum:
        print(s_sum[l[i]])
    else:
        a = d[l[i]] - 1
        ans = m - s_ans[l[i]]
        if a > 1:
            ans += cmb(a, 2)
        s_sum[l[i]] = ans
        print(ans)

### FIXED CODE ###

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

_ = int(input())
l = list(map(int, input().split()))
all_sum = 0
count = count_defaultdict(l)
for _, v in count.items():
    all_sum += v * (v - 1) // 2
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)
### BUGGY CODE ###

n = int(input())
nums = [int(x) for x in input().split()]
multinums = []

for i in range(0,n-1):
    for j in range(i+1,n):
        #print(nums[i],nums[j])
        multinums.append(nums[i]*nums[j])

print(sum(multinums)%(10**9+7))

### FIXED CODE ###

n = int(input())
nums = [int(x) for x in input().split()]
multinums = [0]
total = 0

for i in range(0,n):  #累積和配列を作成する
    multinums.append(multinums[i]+nums[i])

#print(multinums)

for i in range(0,n):
    #print(nums[i],multinums[n]-multinums[i+1],nums[i] * (multinums[n]-multinums[i+1]))
    total += nums[i] * (multinums[n]-multinums[i+1])

print(total%(10**9+7))
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
for i in range(N):
    if S[i]=="R":
        r.append(i)
    elif S[i]=="G":
        g.append(i)
    else:
        b.append(i)

t=0
k=0
A=len(r)
B=len(g)
for i in range(A):
    x = r[i]
    for j in range(B):

        y=g[j]
        if 2*x-y in b:
            k+=1
        if 2*y-x in b:
            k+=1
        if (x+y)/2 in b:
            k+=1


print(A*B*len(b)-k)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

N,W=map(int,input().split())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]
for i in range(1,110000):
    dp[0][i]=10**15

for i in range(1,N+1):
    for j in range(110000):
        dp[i][j]=dp[i-1][j]
        if j-v[i]>=0:
            dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i])

ans=0
for V in range(110000):
    if dp[N][V]<=W:
        ans=max(ans,V)

print(ans)

### FIXED CODE ###

N,W=map(int,input().split())
w=[0 for _ in range(110)]
v=[0 for _ in range(110)]
for i in range(1,N+1):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(110000)] for j in range(110)]
for i in range(1,110000):
    dp[0][i]=10**15

for i in range(1,N+1):
    for j in range(110000):
        dp[i][j]=dp[i-1][j]
        if j-v[i]>=0:
            dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i])

ans=0
for V in range(110000):
    if dp[N][V]<=W:
        ans=max(ans,V)

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

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[None] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = {}
    dp[0] = set()
    dp[0].add(X[0][0])
    dp[0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            threshold = ((H - h) + (W - w)) * 79
            if W * h + w > W - 1:
                for d in dp[W * (h - 1) + w]:
                    
                    if d + x <= threshold:
                        s.add(d + x)
                    if d - x >= -threshold:
                        s.add(d - x)

            if (W * h + w) % W != 0:
                for d in dp[W * h + w - 1]:
                    if d + x <= threshold:
                        s.add(d + x)
                    if d - x >= -threshold:
                        s.add(d - x)

            dp[W * h + w] = s

    ans = min([abs(s) for s in dp[W * H - 1]])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


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

import fractions
a,b=map(int,input().split())
c=list()
cnt=1
if fractions.gcd(a,b)==1:
  print(1)
elif fractions.gcd(a,b)==2:
  print(2)
else:
  for i in range(2,fractions.gcd(a,b)+1):
    if a%i==0 and b%i==0:
      if i==2:
        cnt+=1
      else:
        c.append(i)
  for j in c:
      ok=True
      for k in range(2,j):
        if j%k==0:
            ok=False
      if ok:
        cnt+=1
  print(cnt)

### FIXED CODE ###

A, B = map(int, input().split())
ans = 1
for i in range(2, 1+int(min(A**.5, B**.5))):
    if A % i == 0 and B % i == 0:
        ans += 1
    while A % i == 0:
        A //= i
    while B % i == 0:
        B //= i
if A != 1 and B != 1 and (A % B == 0 or B % A == 0):
    ans += 1
print(ans)
### BUGGY CODE ###

def divs(p):
  divs = []
  for i in range(1,int(p**.5)+1):
    if p%i==0:
      if p%i**N==0:
        divs.append(i)
      if i != p//i and p%(p//i)**N==0:
        divs.append(p//i)
        return divs
  return divs  

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

divs = sorted(divs(P))
if len(divs) == 0:print(1)
else:print(divs[-1])

### FIXED CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,int(n**.5)+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
  
  if n!=1:
    ps[n] = 1
  
  return ps
  
N,P = map(int,input().split())
if N==1:
  print(P)
  exit()
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = float('Inf')
for i in range(n):
    w = s[:i].count("W")
    e = s[i:].count("E")
    ans = min(ans,w+e)
print(ans)


### FIXED CODE ###

from itertools import accumulate
n = int(input())
s = str(input())
tt = [1 if i  == "W" else 0 for i in s]
B = [0] + tt
B = list(accumulate(B))
#print(B)
ans = float('Inf')
for i in range(0,n+1):
    #w = s[:i].count("W")
    ##W = sum(tt[:i])
    w = B[i]
    #print(W,w)
    #e = s[i:].count("E")
    #E = len(tt[i:]) - sum(tt[i:])
    e = n - i - B[-1] + B[i]
    #print(E,e)
    #ans = min(ans,W+E)
    ans = min(ans,w+e)
print(ans)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
a=sorted(list(map(int,input().split())), reverse=True)
cnt=0
for i in a:
    l=make_divisors(i)
    if len(set(a) & set(l))==1 and a.count(i)==1:
        cnt+=1
print(cnt)

### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))+[10**6+1]
a=sorted(a)
flag=np.array([0 for i in range(10**6+1)])
ans=0
for i in range(n):
    if flag[a[i]]==0:
        flag[::a[i]]=1
        if a[i]!=a[i+1]:
            ans+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    graph = [[] for i in range(N)]
    colors = [[-1 for j in range(N)] for i in range(N)]
    prev = [-1 for i in range(N)]
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        unused_colors = set(list(range(1, max_edge+1)))
        if pre != -1:
            unused_colors.remove(colors[target][pre])

        connecteds = graph[target]

        for connected in connecteds:
            if colors[target][connected] != -1:
                unused_colors.discard(colors[connected][target])
                continue

            color = min(unused_colors)
            colors[target][connected] = color
            colors[connected][target] = color
            prev[connected] = target
            deque.append(connected)
            unused_colors.remove(color)

    print(max_edge)

    for edge in edges:
        print(colors[edge[0]][edge[1]])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        pre_key = (target, pre) if target < pre else (pre, target)
        used_color = 0
        if pre != -1:
            used_color = colors[pre_key]

        connecteds = graph[target]
        color = 1
        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                continue
            if color == used_color:
                color += 1
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            color += 1

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()
### BUGGY CODE ###

import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])


#print(k,s)

cnt = 0
    
x = 0
while x <= k:

    if x > s:
        
        break
        
    y = 0
    while y <= k:
        
        if y > s or x + y > s or s-x > 2*k:
        
            break
            
#        print(x,y,s-x-y)    
        if s-x-y <= k:    

            cnt += 1

        y += 1

    x += 1

print(cnt)
    
    


### FIXED CODE ###

def getinputdata():

    array_result = []
    
    data = input()
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result

arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])

cnt = 0

for x in range(0, k + 1):
    
    for y in range(0, k + 1):
        
        z = s-x-y
        
        if z >= 0 and z <= k:
            
            cnt += 1
            
print(cnt)
### BUGGY CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [defaultdict(int) for _ in range(S)]
    ans = 0
    for right in range(N):
        num = A[right]
        if num > S:
            continue
        elif num == S:
            ans = (ans + (right+1) * (N-right)) % MOD
            continue
        for left in dp[S-num]:
            cnt = dp[S-num][left]
            ans = (ans + (left+1) * (N-right) * cnt) % MOD
        for i in range(S-num-1, -1, -1):
            for left in dp[i]:
                dp[i+num][left] += dp[i][left]
        dp[num][right] = 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import defaultdict

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
#    dp = [defaultdict(int) for _ in range(S)]
    dp = [0] * S
    ans = 0
    for right in range(N):
        num = A[right]
        if num > S:
            continue
        elif num == S:
            ans = (ans + (right+1) * (N-right)) % MOD
            continue
        # for left in dp[S-num]:
        #     cnt = dp[S-num][left]
        #     ans = (ans + (left+1) * (N-right) * cnt) % MOD
        # for i in range(S-num-1, -1, -1):
        #     for left in dp[i]:
        #         dp[i+num][left] += dp[i][left]
        # dp[num][right] = 1
        ans = (ans + dp[S-num] * (N-right)) % MOD
        for i in range(S-num-1, -1, -1):
            dp[i+num] += dp[i]
        dp[num] += right + 1
    print(ans)


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

#a_1+a_2+...+a_N = M   Find greatest common divisor of a
N,M=map(int,input().split())

Q=M//N #Quotient
R=M%N  #Reminder

while R%Q != 0:
    Q -= 1
    R += N

print(Q)

### FIXED CODE ###

#a_1+a_2+...+a_N = M   Find greatest common divisor of a
N,M=map(int,input().split())

Q=M//N #Quotient
R=M%N  #Reminder
'''
if Q>R :
    k=int((Q-R)//(1+N))
    k-=1
    Q -= k
    R += k*N
    '''
memo=0
while R%Q != 0:
    k= int((Q-R%Q)//(N+R//Q+1))   #max k:k*(N+R//Q)<Q-k
    #print(R,Q,R%Q,R//Q,k)
    while (R+k*N)//(Q-k) > memo:
        k -= 1
        #print(k,memo,(R+k*N)//(Q-k))
    if k > 0:
        Q -= k
        R += k*N
        memo=R//Q
    else:
        Q -= 1
        R += N
        memo=R//Q

print(Q)
### BUGGY CODE ###

import numpy as np
import functools
import math
import scipy
import fractions
import itertools

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def solve():
    a, b = map(int, input().split())
    ans = 0
    for i in cf(a, b):
        if is_prime(i):
            ans += 1
    print(ans+1)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from fractions import gcd
from collections import Counter


def prime_factorization(n):
    """nを素因数分解する

    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す

    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:
        d[n] += 1
    return d


def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)


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

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

answer = [0] * kn[1]

for j in range(kn[1]):
    for i in range(kn[1]-1):
        if i+j != kn[1]-1:
            answer[j] += A[(i+j+1)%3] - A[(i+j)%3]
        else:
            answer[j] += kn[0] - A[-1] + A[0]
print(min(answer))

### FIXED CODE ###

k,n = map(int,input().split())
a = list(map(int,input().split()))
dis = [0]*n
for i in range(n):
    if i == 0:
        dis[i] = a[-1] - a[0]
    else:
        dis[i] = k - a[i] + a[i-1]
print(min(dis))
### BUGGY CODE ###

import math
def f(N, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,a,b=map(int,input().split())
mod=1000000007
x=n//100
y=n%100
s=((x*976371285)%mod+(2**y)%mod)%mod
A=f(n,a)%mod
B=f(n,b)%mod
print(s-A-B-1)

### FIXED CODE ###

def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  
    denomi = 1  

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod

n,a,b=map(int,input().split())
mod=1000000007
print((pow(2,n,mod)-1-binomial_coefficients(n, a)-binomial_coefficients(n, b))%mod)
### BUGGY CODE ###

a=list(map(int,input().split()))
ans=0
for i in range(a[0]+1):
    for j in range(a[0]+1):
        if a[1]-i-j < a[0]+1 and a[1]-i-j > -1:
            ans+=1
print(str(ans))

### FIXED CODE ###

a=list(map(int,input().split()))
ans=0
for i in range(a[0]+1):
    for j in range(a[0]+1):
        if a[1]-i-j <= a[0] and a[1]-i-j >= 0:
            ans+=1
print(str(ans))
### BUGGY CODE ###

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

ans = 1
flag = False
A.sort()
for i in range(N):
  ans *= A[i]
  if(ans>1000000000000000000):
    flag = True

if(flag):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

ans = 1
flag = False
A.sort()
for i in range(N):
  ans *= A[i]
  if(ans>1000000000000000000):
    flag = True
    break

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

a=list(map(int,input().split()))
ans=0
for i in range(a[0]+1):
    for j in range(a[0]+1):
        if a[0]*2<a[1]-i:
            break
        if a[1]-i-j <= a[0] and a[1]-i-j >= 0:
            ans+=1
print(str(ans))

### FIXED CODE ###

a=list(map(int,input().split()))
ans=0
for i in range(a[0]+1):
    for j in range(a[0]+1):
        if a[1]-i-j <= a[0] and a[1]-i-j >= 0:
            ans+=1
print(str(ans))
### BUGGY CODE ###

from collections import Counter

N=int(input())
S=input()

dup=0

for width in range(2010):
    for i in range(N):
        try:
            if set((S[i],S[i+width],S[i+width*2]))==set(('R','G','B')):
                dup+=1
        except IndexError:
            break

c=Counter(S)
retval=c['R']*c['G']*c['B']-dup
print(retval)


### FIXED CODE ###

from collections import Counter

N=int(input())
S=input()

dup=0
RGB=set(('R','G','B'))

for width in range(N//2+10):
    for i in range(N):
        try:
            if set((S[i],S[i+width],S[i+width*2]))==RGB:
                dup+=1
        except IndexError:
            break

c=Counter(S)
retval=c['R']*c['G']*c['B']-dup
print(retval)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    I=10**18
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=[I]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
#b=np.zeros((n+1, 13), dtype = 'int64')
#p=np.zeros(n,dtype=int)

b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


p=1
#for i in reversed(range(n)):
#	p[i]=x%13
#	x=p[i]*10
	
for i in range(n):
	ix=n-1-i
	if(s[ix]=="?"):
		c=-1
	else:
		c=int(s[ix])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p*j)%13]=1
		else:
			b[0][(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p*c)%13]+=b[i-1][k]

	if (i%30==0 or i==n-1):
		for k in range(13):b[i][k]%=MOD
	p=p*10%13
#	print (b[i])
#	print (b[i+1])

print (b[n-1][5])



### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)