Problem:
 Score : 400 points    Problem Statement Given is a string S . Each character in S is either a digit ( 0 , ..., 9 ) or ? .  Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13 ? An integer may begin with 0 .  Since the answer can be enormous, print the count modulo 10^9+7 .      Constraints   S is a string consisting of digits ( 0 , ..., 9 ) and ? .  1 \leq |S| \leq 10^5         Input  Input is given from Standard Input in the following format:  S       Output  Print the number of integers satisfying the condition, modulo 10^9+7 .        Sample Input 1 ??2??5      Sample Output 1 768  For example, 482305, 002865, and 972665 satisfy the condition.       Sample Input 2 ?44      Sample Output 2 1  Only 044 satisfies the condition.       Sample Input 3 7?4      Sample Output 3 0  We may not be able to produce an integer satisfying the condition.       Sample Input 4 ?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???      Sample Output 4 153716888

Solution (Python):
S = input()

mod = 10 ** 9 + 7
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(10 ** 5 + 5)]
dp[0][0] = 1

for i in range(N):
    c = 0
    if S[i] == "?":
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i+1][(k * 10 + j) % 13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[N][5])

Solution (Python):
S=list(input())
L=len(S)
mod=10**9+7
dp=[[0]*13 for _ in range(2)]
dp[0][0]=1
now,next=1,0
for i in range(L):
	c=S[i]
	now,next=next,now
	for j in range(13):
		if c=='?':
			for k in range(10):
				dp[next][(j*10+k)%13]+=dp[now][j]
		else:dp[next][(j*10+int(c))%13]+=dp[now][j]
	for j in range(13):
		dp[next][j]%=mod
		dp[now][j]=0
print(dp[next][5])

Solution (Python):
d=[0]*13
d[0]=1
for c in input():
	e=[0]*13
	for k in(range(10)if c>'>'else[int(c)]):
		for j in range(13):t=(j*10+k)%13;e[t]+=d[j];e[t]%=10**9+7
	d=e
print(d[5])

Solution (Python):
def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  
    
    dp = [0] * modulo  
    dp[0] = 1  

    
    
    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  
                for j in range(modulo):
                    
                    
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        
        
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))

Solution (Python):
D = 10**9+7
S = input()
mod_table = [[0]*13]
mod_table[0][0] = 1

for i, s in enumerate(S):
    mod_table.append([0]*13)
    if s == "?":
        for num in range(10):
            for d in range(13):
                mod_table[i+1][(d*10+num)%13] += mod_table[i][d]
    else:
        num = int(s)
        for d in range(13):
            mod_table[i+1][(d*10+num)%13] += mod_table[i][d]
    mod_table[i+1] = [m%D for m in mod_table[i+1]]

print(mod_table[-1][5] % D)

Solution (Python):
d=[0]*13
d[0]=1
for c in input():
	e=[0]*13
	for k in(range(10)if c>'>'else[int(c)]):
		for j in range(13):e[(j*10+k)%13]+=d[j]
	d=[e%(10**9+7)for e in e]
print(d[5])

Solution (Python):
S=input()
m=13
d=[0]*m
d[0]=1
for s in S:
  n=[0]*m
  for j in range(m):
    for k in range(10) if s=='?' else [int(s)]:
      n[(10*j+k)%m]+=d[j]
  d=[l%(10**9+7) for l in n]
print(d[5])

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

s = ns()

dp = [0] * 13
dp[0] = 1
mod = 1000000007
for v in s:
    ndp = [0] * 13
    if v == "?":
        for j in range(13):
            for k in range(10):
                nj = (j*10+k)%13
                ndp[nj] += dp[j]
                ndp[nj] %= mod
    else:
        k = ord(v)-ord("0")
        for j in range(13):
            nj = (j*10+k)%13
            ndp[nj] += dp[j]
            ndp[nj] %= mod
    dp = ndp
print(dp[5])

Solution (Python):
t=13
S=input()
d=[0]*t
d[0]=1
for i in range(len(S)):
  n=[0]*t
  for j in range(t):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k:n[(10*j+k)%t]+=d[j]
  for j in range(t):d[j]=n[j]%(10**9+7)
print(d[5])

Solution (Python):
t=13
S=input()
d=[0]*t
d[0]=1
for i in range(len(S)):
  n=[0]*t
  for j in range(t):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k:n[(10*j+k)%t]+=d[j]
  for j in range(t): d[j]=n[j]%(10**9+7)
print(d[5])

Solution (Python):
MOD = 1000000007
m = 13
S = input()
start = int(S.replace('?', '0')) % m
dp = [0] * 13; dp[start] = 1
for i, s in enumerate(S[::-1]):
    nextDP = [0] * 13
    if (s != '?'): continue
    mul = pow(10, i, m)
    for j in range(10):
        for k in range(m):
            nextDP[(mul*j + k) % m] += dp[k]
            nextDP[(mul*j + k) % m] %= MOD
    dp = nextDP
print(dp[5])

Solution (Python):
t=13
S=input()
d=[0]*t
d[0]=1
for i in range(len(S)):
  n=[0]*t
  for j in range(t):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k: n[(10*j+k)%t]+=d[j]
  for j in range(t): d[j]=n[j]%(10**9+7)
print(d[5])

Solution (Python):
s = input()
mod = 10**9+7

dp = [[0 for j in range(13)] for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
  c = -1 if s[i] == '?' else int(s[i])
  for j in range(10):
    if (c != -1 and c != j):
      continue
    for k in range(13):
      dp[i+1][(k * 10 + j) % 13] += dp[i][k]
      dp[i+1][(k * 10 + j) % 13] %= mod
		
  for j in range(13):
    dp[i+1][j] %= mod    
  
print(int(dp[len(s)][5]))

Solution (Python):
z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  f=(t[d]=='?')
  for i in range(k):
    l=pow(z,d,k)
    for x in range(1+f*9):
      r=l*int(x if f else t[d])
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)

Solution (Python):
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))

Solution (Python):
S=input()




MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = input()

    dp = [[0] * 13  for _   in range(len(S)-1)]
    dp[0] = [ModInt(0) for _ in range(13)]
    
    if S[0] == '?':
        for i in range(10):
            dp[0][i] = ModInt(1)
    else:
        dp[0][int(S[0])] = ModInt(1)

    for i in range(1,len(S)-1):
        if S[i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j * 10 + k) % 13 ] += dp[i-1][j]
        else:
            for j in range(13):
                dp[i][ (j* 10 + int(S[i])) % 13 ] += dp[i-1][j]
        

    print(dp[len(S)-2][5])









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

Solution (Python):
S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1], start=1):
    p10 = pow(10, i - 1, 13)
    if s != '?':
        for k in range(13):
            dp[i][(int(s) * p10 + k) % 13] += dp[i - 1][k]
            dp[i][(int(s) * p10 + k) % 13] %= MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i][(j * p10 + k) % 13] += dp[i - 1][k]
                dp[i][(j * p10 + k) % 13] %= MOD

print(dp[N][5] % MOD)

Solution (Python):
mod = 10**9 + 7

S = input()
N = len(S)

dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(13):
        if s == "?":
            for k in range(10):
                l = (10*j + k) % 13
                dp[i+1][l] += dp[i][j]
                dp[i+1][l] %= mod
        else:
            l = (10*j + int(s)) % 13
            dp[i+1][l] += dp[i][j]
            dp[i+1][l] %= mod

ans = dp[N][5]
print(ans)

Solution (Python):
S = input()[::-1]
MOD = 10**9+7
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]
p = 1
for i, s in enumerate(S):
    nx = [0,]*13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
    p = (10*p)%13
print(dp[5])

Solution (Python):

S = input()

s = list(S)

s.reverse()



lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13



    for j in range(10):

        for k in range(13):

            if s[i]== "?" or j == int(s[i]):
                nlis[ (k + (j * keta)) % 13] += lis[k]

    keta *= 10
    keta = keta % 13
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)


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

Solution (Python):
s=input()
a=[0]*13
a[0]=1
for i in s:
  b=[0]*13
  for j,k in enumerate(a):
    b[(j*10)%13]+=k
  a=b[:]
  b=[0]*13
  if i=="?":
    for l in range(10):
      for j,k in enumerate(a):
        b[(j+l)%13]+=k
  else:
    for j,k in enumerate(a):
      b[(j+int(i))%13]+=k
  a=[j%(10**9+7) for j in b]
print(a[5]%(10**9+7))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
	if S[i] == '?':
		c = -1
	else:
		c = int(S[i])

	for j in range(10):
		if c != -1 and c != j:
			continue
		for k in range(13):
			dp[i+1][(k*10+j)%13] = (dp[i+1][(k*10+j)%13] + dp[i][k]) % mod


print(dp[len(S)][5])

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    mod = 10 ** 9 + 7
    s = list(input())
    n = len(s)
    s.reverse()

    dp = [[0] * 13 for _ in range(n + 1)]
    dp[0][0] = 1

    mul = 1
    for i, c in enumerate(s):
        for j in range(10):
            if (c.isdigit() and int(c) == j) or c == '?':
                m = (j * mul) % 13
                for k in range(13):
                    dp[i + 1][(m + k) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] = dp[i + 1][k] % mod
        mul *= 10
        mul %= 13
    print(dp[n][5])


if __name__ == '__main__':
    main()

Solution (Python):
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)

Solution (Python):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict






INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)








S = input()
M = 13
DP = [0] * M
DP[0] = 1

mul = 1
for i in range(len(S) - 1, -1, -1):
    s = S[i]
    newDP = [0] * M
    if s == '?':
        for k in range(10):
            for j in range(M):
                newDP[(mul * k + j) % M] += DP[j]
    else:
        k = int(s)
        for j in range(M):
            newDP[(mul * k + j) % M] += DP[j]
    DP = [x % MOD for x in newDP]
    mul *= 10
    mul %= M

print(DP[5])

Solution (Python):
import sys


fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = fin().rstrip("\n")[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
base = 1
for i, c in enumerate(S, start=1):
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
    base = base * 10 % 13
print(dp[-1][5])

Solution (Python):




MOD = 10 ** 9 + 7
S = input()[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
base = 1
for i, c in enumerate(S, start=1):
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
    base = base * 10 % 13
print(dp[-1][5])

Solution (Python):
S = input()

N = len(S)
dp = [[0 for i in range(13)] for j in range(N + 1)]
mod = 10**9 + 7

dp[0][0] = 1
for i in range(N):
    for j in range(13):
        if S[i] != "?":
            dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
        else:
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[N][5])

Solution (Python):
S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
               DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)

Solution (Python):
S = input().strip()

MOD = 10**9 + 7
dp = [[0 for i in range(13)] for j in range(100005)]
N = len(S)

dp[0][0] = 1
for i in range(N):
    c = -1
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]

    for j in range(13):
        dp[i+1][j] %= MOD

res = int(dp[N][5])

print(res)

Solution (Python):




MOD = 10 ** 9 + 7
S = input()[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = pow(10, i - 1, 13)
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
print(dp[-1][5])

Solution (Python):
MOD=10**9+7
s=input()[::-1]
l=len(s)
dp=[[0 for j in range(13)] for i in range(l)]
if s[0] == "?":
    for j in range(10):dp[0][j]=1
else:
    dp[0][int(s[0])]=1
m=1
for i in range(1,l):
    m=10*m%13
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i-1][k]%=MOD
                dp[i][(k+j*m)%13]+=dp[i-1][k]
    else:
        for k in range(13):
            dp[i-1][k]%=MOD
            dp[i][(k+int(s[i])*m)%13]+=dp[i-1][k]
print(dp[-1][5]%(10**9+7))

Solution (Python):
S = input()
dp = [[0 for j in range(13)]for i in range(10**5+1)]
dp[0][0] = 1
for i in range(len(S)):
    c = 0
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if c != -1 and c!= j:
            continue
        for ki in range(13):
            dp[i+1][(ki*10+j)%13] += dp[i][ki]
    for j in range(13):
        dp[i+1][j] %= 10**9+7
    
print(dp[len(S)][5])

Solution (Python):
S=input()
d=[0]*13
d[0]=1
for i in range(len(S)):
  n=[0]*13
  for j in range(13):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k: n[(10*j+k)%13]+=d[j]
  for j in range(13): d[j]=n[j]%(10**9+7)
print(d[5])

Solution (Python):
S = input()
MOD = 10 ** 9 + 7
N = 13
dp = [0 for _ in range(N)]
dp[0] = 1

mul = 1
for i in range(len(S)):
  c = S[len(S) - i - 1]
  nextDP = [0 for _ in range(N)]

  if c == "?":
    for k in range(10):
      for j in range(N):
        nextDP[(k * mul + j) % N] += dp[j]
        nextDP[(k * mul + j) % N] %= MOD
  else:
    k = int(c)
    for j in range(N):
      nextDP[(k * mul + j) % N] += dp[j]
      nextDP[(k * mul + j) % N] %= MOD

  mul *= 10
  mul %= N
  dp = nextDP
print(dp[5])

Solution (Python):
S=input()
d=[0]*13
d[0]=1
for i in range(len(S)):
  n=[0]*13
  for j in range(13):
    for k in range(10):
      n[(10*j+k)%13]+=(1 if S[i]=='?' or int(S[i])==k else 0)*d[j]
  for j in range(13): d[j]=n[j]%(10**9+7)
print(d[5])

Solution (Python):
M = 10**9+7
S = input()
D = 13

dp = [0 for d in range(D)]
dp[0] = 1
mul = 1
for i in range(len(S)-1, -1, -1):
    nextDP = [0 for d in range(D)]
    c = S[i]
    if c == '?':
        for k in range(10):
            for j in range(D):
                nextDP[(k*mul+j)%D] += dp[j]
                nextDP[(k*mul+j)%D] %= M
    else:
        k = int(c)
        for j in range(D):
            nextDP[(k*mul+j)%D] += dp[j]
            nextDP[(k*mul+j)%D] %= M

    mul *= 10
    mul %= D
    dp = nextDP
print(dp[5])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    N = len(S)
    S = reversed(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i, es in enumerate(S):
        c = es
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
            else:
                amari = (int(c) * pow(10, i, 13)) % 13
                for k in range(13):
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD
 
    dprint(dp)
    print(dp[N-1][5])


solve()

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0]*13 for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])] += 1
    else:
      for j in range(10):
        dp[i][j] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k*10+int(S[i]))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k*10+j)%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])

Solution (Python):

import sys
mod = 13

s = input()

num_digits = len(s)

dp = [[0 for _ in range(mod)] for _ in range(num_digits)]
if s[0] == '?':
    dp[0] = [1 for _ in range(10)] + [0 for _ in range(10, 13)]
else:
    dp[0][int(s[0])] = 1

for i, c in enumerate(s[1:]):
    if c == '?':
        targets = range(10)
    else:
        targets = [int(c)]

    for j in targets:
        for k in range(mod):
            dp[i + 1][(k * 10 + j) % mod] += dp[i][k]

    for k in range(mod):
        dp[i + 1][k] %= int(10**9 + 7)

print(dp[-1][5])

Solution (Python):
s=input()[::-1]
l=len(s)
dp=[[0 for j in range(13)] for i in range(l)]
if s[0] == "?":
    for j in range(10):dp[0][j]=1
else:
    dp[0][int(s[0])]=1
for i in range(1,l):
    mod = pow(10,i,13)
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i-1][k] %= 10**9+7
                dp[i][(k+j*mod)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i-1][k] %= 10**9+7
            dp[i][(k+int(s[i])*mod)%13] += dp[i-1][k]
print(dp[-1][5]%(10**9+7))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [0 for j in range(13)]
    dp2 = [0 for j in range(13)]

    for i, c in enumerate(S):
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[j] = 1
            else:
                dp[int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp2[k] = (dp2[k] + dp[(k-amari)%13]) % MOD
            else:
                for k in range(13):
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp2[k] = (dp2[k] + dp[(k-amari) % 13]) % MOD

            dp = dp2
            dp2 = [0 for j in range(13)]

    dprint(dp)
    print(dp[5])



solve()

Solution (Python):
import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
                ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])

Solution (Python):
S = input()
S = S[::-1]

dp = [[0]*13 for _ in range(len(S)+1)]

dp[0][0]=1

q=1
for i in range(1,len(S)+1): 
  s = S[i-1]
  if s=='?':
    for j in range(13):
      for n in range(10):
      	dp[i][(j+n*q)%13] += dp[i-1][j]
    for j in range(12):
      dp[i][j] %= 10**9+7
  else:
    n = int(s)
    for j in range(13):
      dp[i][(j+n*q)%13] = dp[i-1][j]
  q = (10*q)%13
  
print(dp[len(S)][5])

Solution (Python):
S = input()
MOD = 10**9 + 7
lenS = len(S)

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10
    digitMask %= 13

ans = (dp[len(S)][5]) % MOD
print(ans)

Solution (Python):
S = list(input())
MOD = 10 ** 9 + 7

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])

Solution (Python):
import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])

Solution (Python):
S = input()
N = len(S)

mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S):
    keta = (N-i-1)%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)

Solution (Python):
s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)

Solution (Python):
S=input()
N=len(S)
X=[1,10,9,12,3,4]
Y=[0,0,0,0,0,0]
nowmod=0
modprime=10**9+7
for i in range(N):
    if S[-i-1]=="?":
        Y[i%6]+=1
    else:
        nowmod+=X[i%6]*int(S[-i-1])
        nowmod%=13


M=max(Y)
dp=[[0 for j in range(13)]for i in range(M+1)]

dp[0][0]=1
for i in range(M):
    for k in range(10):
        for j in range(13):
            dp[i+1][(k+j)%13]+=dp[i][j]
            dp[i+1][(k+j)%13]%=modprime
table=[[dp[Y[i]][j] for j in range(13)]for i in range(6)]
ans=[[0 for j in range(13)] for i in range(7)]
ans[0][0]=1
for i in range(6):
    for j in range(13):
        for k in range(13):
            ans[i+1][(j+(X[i]*k))%13]+=ans[i][j]*table[i][k]
            ans[i+1][(j+(X[i]*k))%13]%=modprime
print(ans[6][(5-nowmod)%13])

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

S = input()
n = len(S)
dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    c = 0
    if S[i]=="?":
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki*10+j)%13] += dp[i][ki]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[n][5])

Solution (Python):
"""
AtCoder
    :author: vierbein
"""
from __future__ import absolute_import, division, print_function


import collections
import sys

BIGINT = int(1e9) + 7

def pp(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

S = input().strip()

slots = [0] * 13
slots[0] = 1

for p, c in enumerate(reversed(S)):
    xx = pow(10, p, 13)
    new_slots = [0] * 13
    if c == "?":
        for i in range(10):
            for k in range(13):
                idx = (i * xx + k) % 13
                new_slots[idx] = (new_slots[idx] + slots[k]) % BIGINT
    else:
        n = int(c)
        for k in range(13):
            new_slots[(n * xx + k) % 13] = slots[k]
    slots = new_slots

print(slots[5])

Solution (Python):
s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]

mod = 10 ** 9 + 7
power = 1

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = (j * power) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = (val * power)% 13
            for k in range(13):
                dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    power = (power * 10) % 13
print(dp[digits-1][5])