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):
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    s = input()
    ques_count = s.count('?')
    base_num = 1
    rem_list = []
    for _ in range(len(s)):
        rem_list.append(base_num % 13)
        base_num = base_num * 10 % 13
    rem_list = rem_list[::-1]

    rem1 = 0
    for index, si in enumerate(s):
        if si != '?':
            si_int = int(si)
            rem1 = rem1 + si_int * rem_list[index]
    rem1 = rem1 % 13

    dp = [[0] * 13 for _ in range(ques_count + 1)]
    dp[0][rem1] = 1
    dp_index = 1
    for index, si in enumerate(s):
        if si == '?':
            rem_cdd_list = [rem_list[index] * i % 13 for i in range(10)]
            for rem in rem_cdd_list:
                for i in range(13):
                    dp[dp_index][i] = (dp[dp_index][i] + dp[dp_index - 1][(i - rem) % 13]) % (10 ** 9 + 7)
            dp_index = dp_index + 1
    
    print(dp[ques_count][5])

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

text=input()
lst=list(text)
lst.reverse()
digit=len(lst)
six=[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]
for i in range(digit):
  if(lst[i]=="?"):
    six[i%6][1]=six[i%6][1]+1
  else:
    six[i%6][0]=(six[i%6][0]+int(lst[i]))%13
rem=-(six[0][0]+10*six[1][0]+9*six[2][0]+12*six[3][0]+3*six[4][0]+4*six[5][0]-5)%13


modulos=[1,0,0,0,0,0,0,0,0,0,0,0,0]
def mat1(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-1)%13]+ls[(i-2)%13]+ls[(i-3)%13]+ls[(i-4)%13]+ls[(i-5)%13]+ls[(i-6)%13]+ls[(i-7)%13]+ls[(i-8)%13]+ls[(i-9)%13])%M
  return val_ls
def mat10(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-10)%13]+ls[(i-20)%13]+ls[(i-30)%13]+ls[(i-40)%13]+ls[(i-50)%13]+ls[(i-60)%13]+ls[(i-70)%13]+ls[(i-80)%13]+ls[(i-90)%13])%M
  return val_ls
def mat100(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-9)%13]+ls[(i-18)%13]+ls[(i-27)%13]+ls[(i-36)%13]+ls[(i-45)%13]+ls[(i-54)%13]+ls[(i-63)%13]+ls[(i-72)%13]+ls[(i-81)%13])%M
  return val_ls
def mat1000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+1)%13]+ls[(i+2)%13]+ls[(i+3)%13]+ls[(i+4)%13]+ls[(i+5)%13]+ls[(i+6)%13]+ls[(i+7)%13]+ls[(i+8)%13]+ls[(i+9)%13])%M
  return val_ls
def mat10000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-3)%13]+ls[(i-6)%13]+ls[(i-9)%13]+ls[(i-12)%13]+ls[(i-15)%13]+ls[(i-18)%13]+ls[(i-21)%13]+ls[(i-24)%13]+ls[(i-27)%13])%M
  return val_ls
def mat100000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-4)%13]+ls[(i-8)%13]+ls[(i-12)%13]+ls[(i-16)%13]+ls[(i-20)%13]+ls[(i-24)%13]+ls[(i-28)%13]+ls[(i-32)%13]+ls[(i-36)%13])%M
  return val_ls
for j in range(six[0][1]):
  modulos=mat1(modulos)
for j in range(six[1][1]):
  modulos=mat10(modulos)
for j in range(six[2][1]):
  modulos=mat100(modulos)
for j in range(six[3][1]):
  modulos=mat1000(modulos)
for j in range(six[4][1]):
  modulos=mat10000(modulos)
for j in range(six[5][1]):
  modulos=mat100000(modulos)
print(modulos[rem])

Solution (Python):
inf = 10 ** 18
P = 10 ** 9 + 7

S = input()
N = len(S)

tmp = 1
modrow = [1] * 6
for i in range(5):
    tmp = (tmp * 10) % 13
    modrow[1 + i] = tmp

modtab = [[None] * 10 for i in range(6)]
for i in range(6):
    for j in range(10):
        modtab[i][j] = (modrow[i] * j) % 13





X = 0
q_idx = []
for i, Si in enumerate(S[::-1]):
    if Si == '?':
        q_idx.append(i)
    else:
        X = (X + modtab[i % 6][int(Si)]) % 13


M = len(q_idx)
ans_tab = [[0] * 13 for _ in range(M + 1)]

ans_tab[0][0] = 1
for i, idx in enumerate(q_idx):
    for src in range(13):
        for coeff in range(10):
            dst = (src + modtab[idx % 6][coeff]) % 13
            ans_tab[1 + i][dst] = (ans_tab[1 + i][dst] + ans_tab[i][src]) % P
        

idx_ans = (5 - X) % 13
print(ans_tab[-1][idx_ans])

Solution (Python):
s=list(input())
s.reverse()
l=[1,10,9,12,3,4]
p=10**9+7
dp=[[0 for i in range(13)] for j in range(len(s))]
if s[0]=='?':
  for i in range(10):
    dp[0][i]+=1
else:
  dp[0][int(s[0])]+=1
for i in range(1,len(s)):
  if s[i]!='?':
    for j in range(13):
      dp[i][j]+=dp[i-1][(j-(int(s[i])*l[i%6]))%13]
      dp[i][j]%=p
  else:
    for j in range(13):
      for k in range(10):
        dp[i][j]+=dp[i-1][(j-k*l[i%6])%13]
        dp[i][j]%=p
print(dp[len(s)-1][5])

Solution (Python):


from functools import lru_cache

PRIME = 10 ** 9 + 7


@lru_cache(maxsize=None)
def digitmod13(y):
    if y == 0:
        return 1
    elif y == 1:
        return 10 % 13
    elif y % 2 == 0:
        return digitmod13(y // 2) ** 2 % 13
    else:
        return digitmod13(y // 2) ** 2 * 10 % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    
    
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    
    
    table = [[[(i + (j * k)) % 13 for k in range(13)] for j in range(10)] for i in range(13)]
    
    
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    mod = table[d][k][digitmod13(i)]
                    dp[i][mod] += dp[i - 1][d]
                    dp[i][mod] %= PRIME
        else:
            c = int(c)
            for d in range(13):
                mod = table[d][c][digitmod13(i)]
                dp[i][mod] += dp[i - 1][d]
                dp[i][mod] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


if __name__ == "__main__":
    main()

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

rs = [[0] * 10 for i in range(len(S))]
for i in reversed(range(len(S))):
    if i == len(S) - 1:
        for j in range(10):
            rs[i][j] = j % 13
        continue

    for j in range(10):
        rs[i][j] = rs[i+1][j] * 10 % 13


for i in reversed(range(len(S))):
    if i == len(S) - 1:
        if S[i] == '?':
            for v in range(10):
                r = v % 13
                dp[i][r] += 1
        else:
            v = int(S[i])
            r = v % 13
            dp[i][r] += 1
        continue

    if S[i] == '?':
        for v in range(10):
            for r in range(13):
                s = (rs[i][v] + r) % 13
                dp[i][s] += dp[i+1][r]
                dp[i][s] %= MOD
    else:
        v = int(S[i])
        for r in range(13):
            s = (rs[i][v] + r) % 13
            dp[i][s] += dp[i+1][r]
            dp[i][s] %= MOD

print(dp[0][5])

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

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])

Solution (Python):
mod=10**9+7
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
      DP[i+1][k]%=mod
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)

Solution (Python):
s = list(input())[::-1]

mod = 10**9 + 7

rest = []
for i in range(6):
    res = []
    for j in range(10):
        res.append(((10**i)*j) % 13)
    rest.append(res)

nowtable = [0] * 13
nowtable[0] = 1

for i in range(len(s)):
    degree = i % 6
    nextable = [0] * 13
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                index = (k + rest[degree][j]) % 13
                nextable[index] = (nextable[index] + nowtable[k]) % mod
    else:
        num = int(s[i])
        for k in range(13):
            index = (k + rest[degree][num]) % 13
            nextable[index] = (nextable[index] + nowtable[k]) % mod
    nowtable = nextable

print(nowtable[5])

Solution (Python):
S=input()
L=len(S)
mod=10**9+7
DP=[0]*13
DP[0]=1

for i in range(L):
    NDP=[0]*13
    POW=pow(10,L-i-1,13)

    

    if S[i]=="?":
        
        for j in range(10):
            plus=POW*j%13

            for k in range(13):
                NDP[(k+plus)%13]=(NDP[(k+plus)%13]+DP[k])%mod

    else:
        plus=POW*int(S[i])%mod

        for k in range(13):
            NDP[(k+plus)%13]=(NDP[(k+plus)%13]+DP[k])%mod
        

    DP=NDP
    

print(DP[5])

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
dp = [[0] * 13 for i in range(N+1)]
if S[N-1] != '?':
    dp[N-1][int(S[N-1])] = 1
else:
    for i in range(10):
        dp[N-1][i] = 1
for k in range(N-1)[::-1]:
    d = D[N-k-1]
    for m in range(13):
        if S[k] != '?':
            dp[k][m] += dp[k+1][(m-d*int(S[k]))%13]
            dp[k][m] %= mod
        else:
            for i in range(10):
                dp[k][m] += dp[k+1][(m-i*d)%13]
                dp[k][m] %= mod
print(dp[0][5])

Solution (Python):
MOD = int(1e9 + 7)

s = input()
digits = len(s)

cnt = 0
for i, c in enumerate(reversed(s)):
    if c == '?':
        continue
    n = int(c) * pow(10, i, 13) % 13
    cnt += n


before = [0] * 13
first_time = True
for i, c in enumerate(reversed(s)):
    if c != '?':
        continue
    if first_time:
        for j in range(10):
            n = j * pow(10, i, 13) % 13
            before[n] += 1
        first_time = False
        continue
    current = [0] * 13
    for j in range(10):
        n = j * pow(10, i, 13) % 13
        current[n] += 1
    after = [0] * 13
    for j in range(13):
        for k in range(13):
            after[j] += before[k] * current[(13 - k + j) % 13]
        after[j] %= MOD
    before = after

if first_time:
    if cnt % 13 == 5:
        print(1)
    else:
        print(0)
else:
    print(before[(5 - (cnt % 13)) % 13])

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9+7
s = list(input())[:-1]

s = s[::-1]

ls = len(s)

mod_13_list = [ (10**i) % 13 for i in range(6) ]

dp_list = [ 0 for i in range(13) ]
if  s[0] != "?":
    p = int(s[0])
    dp_list[p] += 1
else:
    for i in range(10):
        dp_list[i] += 1

t = 1
for i in range(1,ls):
    r = mod_13_list[t]
    t = ( t + 1 ) % 6
    new_dp_list = [ 0 for i in range(13) ]
    if s[i] != "?":
        p = int(s[i])
        q = ( p * r ) % 13
        for j in range(13):
            new_dp_list[(j+q)%13] += dp_list[j]
    
    else:
        for k in range(10):
            q = (k * r ) % 13
            for j in range(13):
                new_dp_list[(j+q)%13] += dp_list[j]
    
    dp_list = [ i % mod for i in new_dp_list ]

print(dp_list[5])

Solution (Python):
s = input()
t = s[::-1]
mod = 10**9 + 7

digit = [0] * (10**5+10)
digit[0] = 1  
for i in range(1, 10**5+10):
    digit[i] = (digit[i-1] * 10) % 13

dp = [[0 for _ in range(13)] for i in range(10**5+10)]
dp[0][0] = 1

for i in range(1, len(s)+1):
    for j in range(13):
        if t[i-1] != '?':
            num = int(t[i-1])
            dp[i][(j+(num*digit[i-1])%13)%13] += dp[i-1][j]
            dp[i][(j + (num * digit[i - 1]) % 13) % 13] %= mod
        else:
            for k in range(10):
                dp[i][(j + (k * digit[i - 1]) % 13) % 13] += dp[i-1][j]
                dp[i][(j + (k * digit[i - 1]) % 13) % 13] %= mod

print(dp[len(s)][5] % mod)

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

dp=[[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0]=1

for i in range(len(S)):
    if S[i]=="?":
        for j in range(13):
            
            for k in range(10):
                dp[i+1][(10*j+k)%13]+=dp[i][j]
                dp[i+1][(10*j+k)%13]%=(10**9+7)
    else:
        for j in range(13):
            dp[i+1][(10*j+int(S[i]))%13]+=dp[i][j]
            dp[i+1][(10*j+int(S[i]))%13]%=(10**9+7)
print(dp[-1][5])

Solution (Python):


Q = 10**9+7
def main():
    S = input()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        s = S[N-1-i]
        r = pow(10, i, 13)                
        if s == '?':
            for k in range(10):
                t = k*r%13
                for j in range(13):
                    dp[i+1][(j+t)%13] = (dp[i+1][(j+t)%13] + dp[i][j])%Q
            continue
        t = int(s)*r%13
        for j in range(13):
            dp[i+1][(j+t)%13] = dp[i][j]
    print(dp[N][5])
if __name__ == '__main__':
    main()

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, ss in enumerate(s, 1):
    
    p = pow(10, n - i, 13)
    if ss == '?':
        for c in '0123456789':
            to_add = (int(c) * p) % 13
            for r in range(13):
                dp[i][(r + to_add) % 13] += dp[i - 1][r]
                dp[i][(r + to_add) % 13] %= mod
    else:
        to_add = (int(ss) * p) % 13
        for r in range(13):
            dp[i][(r + to_add) % 13] += dp[i - 1][r]
            dp[i][(r + to_add) % 13] %= mod
print(dp[n][5])

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

p = [ (10**k)%13 for k in range(6) ]
mod_tb = [ [i*p[k]%13 for i in range(10)] for k in range(6) ]
n = [0]*6
base = 0
for k in range(len(S)):
    s = S[-(k+1)]
    if s == '?':
        n[k%6] += 1
    else:
        base += p[k%6]*int(s)
        base %= 13

DP = [ [0] * 13 for _ in range(sum(n)+1) ]
DP[0][base] = 1
i = 1
for k in range(6):
    for _ in range(n[k]):
        for m in range(13):
            for d in range(10):
                DP[i][(m + mod_tb[k][d])%13] += DP[i-1][m]
        for m in range(13):
            DP[i][m] %= MOD
        i += 1
print(DP[-1][5])

Solution (Python):
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    S = input().rstrip("\n")
    dp = [[0 for i in range(13)] for i in range(len(S)+1)]
    dp [0][0] = 1
    modi = 1%13
    for i in range(1,len(S)+1):
        
        s = S[len(S)-i]
        if s!= '?':
            mod_q = (int(s)*modi)%13
            for k in range(13):
                dp[i][(k+mod_q) % 13] = (dp[i][(k+mod_q) % 13]+dp[i-1][k]) % DIV
        else:
            for j in range(10):
                mod_q = (j*modi) % 13
                for k in range(13):
                    dp[i][(k+mod_q) % 13] = (dp[i]
                                             [(k+mod_q) % 13]+dp[i-1][k]) % DIV
        modi = (modi*10)%13
    return dp[len(S)][5]
print(main())

Solution (Python):

from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

MOD = 10**9 + 7


def main():
    s = input()
    t = s[::-1]

    n = len(s)

    rem = 0
    filler = []
    for i in range(n):
        if t[i] == '?':
            filler.append(pow(10, i, 13))
        else:
            rem += pow(10, i, 13) * int(t[i])

    rem %= 13

    if not filler:
        if rem == 5:
            print(1)
        else:
            print(0)
        return

    dp = [0] * 13
    for i in range(10):
        dp[i * filler[0] % 13] += 1

    for i in range(1, len(filler)):
        dp_row = [0] * 13
        for j in range(10):
            dp_row[filler[i] * j % 13] += 1

        dp_copy = [0] * 13
        for i in range(13):
            for j in range(13):
                dp_copy[(i + j) % 13] = (dp[i] * dp_row[j] + dp_copy[(i + j) % 13]) % MOD
        dp = dp_copy

    print(dp[(5 - rem) % 13])




BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
s = input()[::-1]
m = 13
mod = 10**9+7

r = [1]
for i in range(10**5):
    r.append(r[-1]*10 % m)

dp = [0]*m
dp[0] = 1
for i, c in enumerate(s):
    nxt = [0]*m
    if c == "?":
        for j in range(m):
            for k in range(10):
                nxt[(j+k*r[i])%m] += dp[j]
                nxt[(j+k*r[i])%m] %= mod
    else:
        n = int(c)
        for j in range(m):
            nxt[(j+n*r[i])%m] += dp[j]
            nxt[(j+n*r[i])%m] %= mod
    dp = nxt
print(dp[5])

Solution (Python):
modarr11=[77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 76]
modarr21=[8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 7]
modarr22=[7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7]
modarr23=[8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7]
modarr31=[1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
modarr32=[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1]
modarr33=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]

s=input()
l=len(s)
if l%3!=0:
  s='0'*(3-l%3)+s
  l+=(3-l%3)
mod=10**9+7
cnt=0
dp=[[0]*13 for _ in range(l//3+1)]
for i in range(l-1,-1,-3):
  num=0
  qpos=0
  for j in range(3):
    if s[i-j]=='?':
      qpos+=1*(10**j)
    else:
      num+=int(s[i-j])*(10**j)
  if qpos==0:
    tmod=[0]*13
    tmod[num%13]=1
  elif qpos==1:
    tpos=num%13
    tmod=modarr33[-tpos:]+modarr33[:-tpos]
  elif qpos==10:
    tpos=num%13
    tmod=modarr32[-tpos:]+modarr32[:-tpos]
  elif qpos==100:
    tpos=num%13
    tmod=modarr31[-tpos:]+modarr31[:-tpos]
  elif qpos==11:
    tpos=num%13
    tmod=modarr23[-tpos:]+modarr23[:-tpos]
  elif qpos==101:
    tpos=num%13
    tmod=modarr22[-tpos:]+modarr22[:-tpos]
  elif qpos==110:
    tpos=num%13
    tmod=modarr21[-tpos:]+modarr21[:-tpos]
  elif qpos==111:
    tmod=modarr11
  if cnt==0:
    dp[1]=tmod
  elif cnt%2==0:
    for k in range(13):
      for l in range(13):
        dp[cnt+1][(k+l)%13]+=(tmod[k]*dp[cnt][l])%mod
  else:
    for k in range(13):
      for l in range(13):
        dp[cnt+1][(l-k)%13]+=(tmod[k]*dp[cnt][l])%mod
  cnt+=1
print(dp[cnt][5]%mod)

Solution (Python):
MOD = 10**9 + 7
def solve(A):
    N = len(A)
    dp = [1] + [0] * 12
    pwr = 1
    for i in xrange(N-1, -1, -1):
        if A[i] == '?':
            dp2 = [0] * 13
            for k, v in enumerate(dp):
                for d in xrange(10):
                    k2 = (k + d * pwr) % 13
                    dp2[k2] += v
                    dp2[k2] %= MOD
            dp = dp2
        else:
            shift = int(A[i]) * pwr % 13
            dp2 = [0] * 13
            for k, v in enumerate(dp):
                k2 = (k + shift) % 13
                dp2[k2] += v
            dp = dp2
        pwr *= 10
        pwr %= 13
    
    return dp[5] % MOD
        
print solve(raw_input().rstrip())

Solution (Python):
MOD = 10**9 + 7
mod13 = [[0] * 10 for _ in range(6)]
for i in range(6):
    mod13[i] = [(10**i * item) % 13 for item in range(10)]

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

for i, item in enumerate(s[::-1]):
    if item == "?":
        for j in range(13):
            for modval in mod13[i%6]:
                dp[(j+modval)%13][i+1] += dp[j][i]
            dp[j][i+1] %= MOD
    else:
        modval = mod13[i%6][int(item)]
        for j in range(13):
            dp[(j+modval) % 13][i+1] += dp[j][i]
            dp[j][i+1] %= MOD

print(dp[5][-1] % MOD)

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


def solve_a(test=False, a=2, b=16):

    if not test:
        a, b = map(int, input().split())
    if (b - a) % 2 == 0:
        print((a + b) // 2)
    else:
        print("IMPOSSIBLE")


def solve_b(test=False, n=5, p_list=[5, 2, 3, 4, 1]):

    if not test:
        n = int(input())
        p_list = list(map(int, input().split()))

    r = 0
    for i in range(n):
        if p_list[i] != i + 1:
            r += 1
    if r == 0 or r == 2:
        print("YES")
    else:
        print("NO")


def solve_c(test=False, n=2, a_list=[3, 5, 2], b_list=[4, 5]):

    if not test:
        n = int(input())
        a_list = list(map(int, input().split()))
        b_list = list(map(int, input().split()))

    res = 0
    for i in range(n):
        if b_list[i] <= a_list[i]:
            res += b_list[i]
            a_list[i] -= b_list[i]
        elif b_list[i] < a_list[i] + a_list[i + 1]:
            res += b_list[i]
            a_list[i + 1] -= b_list[i] - a_list[i]
            a_list[i] = 0
        else:
            res += a_list[i] + a_list[i + 1]
            a_list[i] = 0
            a_list[i + 1] = 0

    print(res)


def solve_d(test=False, s='??2??5'):

    if not test:
        s = input()

    l = len(s)
    res_list_new = [0] * 13
    res_list_old = [0] * 13
    zero_mod = int(s.replace('?', '0')) % 13
    res_list_new[zero_mod] += 1

    for i in range(1, l + 1):
        if s[-i] == '?':
            for k in range(13):
                res_list_old[k] = res_list_new[k] % LARGE
            base_mod = pow(10, i-1, 13)
            for j in range(1, 10):
                for k in range(13):
                    res_list_new[(k + base_mod * j) % 13] += res_list_old[k]

    print(res_list_new[5] % LARGE)



















solve_d()

Solution (Python):
s=input()

d=[[1,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0]]
t=1
p=0
for i in range(len(s)-1,-1,-1): 
  
  
  c=s[i]
  if c=="?":
    for k in range(13):
      for j in range(10):
        
        
        d[1-p][(t*j+k)%13]+=d[p][k]
  else:
    x=int(c)
    for k in range(13):
      d[1-p][(k+t*x)%13]+=d[p][k]
  for k in range(13):
    d[p][k]=0
  for k in range(13):
    d[1-p][k]%=1000000007
  p=1-p
  t=t*10%13

print(d[len(s)%2][5])

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    dpn = [0]*13
    keta = 1
    zero = 0
    
    for c in reversed(S):
        if c == "?":
            dpn = [0]*13
            for i in range(10):
                for j in range(13):
                    dpn[j] += dp[(j - i*keta) % 13]
                    dpn[j] %= MOD
            dp = dpn
        else:
            shift = (int(c)*keta) % 13
            dpn = [0]*13
            for i in range(13):
                dpn[i] = dp[(i-shift) % 13]
            
            dp = dpn

        
        keta *= 10
        keta %= 13

    print(dp[5])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    solve(S)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()
n = len(s)
MOD = 10**9 + 7

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

for i, si in enumerate(s):
    if si == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j + k) % 13] += dp[i][j]
                dp[i + 1][(10 * j + k) % 13] %= MOD

    else:
        k = int(si)
        for j in range(13):
            dp[i + 1][(10 * j + k) % 13] += dp[i][j]
            dp[i + 1][(10 * j + k) % 13] %= MOD

print(dp[n][5])

Solution (Python):
import sys
input=sys.stdin.readline
s=input()
n=len(s)
n=n-1
INF=10**9+7
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    if s[i]=='?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j+k)%13]=(dp[i+1][(10*j+k)%13]+dp[i][j])%INF
    else:
        num=int(s[i])
        for j in range(13):
            dp[i+1][(10*j+num)%13]=dp[i][j]%INF
print(dp[n][5])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b = LI()
    if (a + b) % 2:
        print("IMPOSSIBLE")
        return
    print((a + b) // 2)
    return


def B():
    n = II()
    p = LI()
    for i in range(n):
        for k in range(i+1, n):
            pi = p[::1]
            pi[i], pi[k] = pi[k], pi[i]
            for j in range(n-1):
                if pi[j] > pi[j + 1]:
                    break
            else:
                print("YES")
                return
    print("NO")
    return


def C():
    n = II()
    a = LI()
    b = LI()
    ans = 0
    for i in range(n):
        if a[i] >= b[i]:
            ans += b[i]
            continue
        ans += a[i]
        b[i] -= a[i]
        if a[i + 1] >= b[i]:
            ans += b[i]
            a[i + 1] -= b[i]
            continue
        ans += a[i + 1]
        a[i + 1] = 0
    print(ans)
    return


def D():
    s = S()
    s = s[::-1]
    dp = [[0] * 13 for _ in range(len(s))]
    remain = 1
    if s[0] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s[0])] = 1
    for i in range(1, len(s)):
        remain = (remain * 10) % 13
        dpi = dp[i]
        dpi1 = dp[i-1]
        if s[i] == "?":
            for k in range(10):
                for j in range(13):
                    dpi[(j + remain * k) % 13] += dpi1[j]
                    dpi[(j + remain * k) % 13] %= mod
        else:
            for j in range(13):
                dpi[(j + remain * int(s[i])) % 13] += dpi1[j]
    print(dp[-1][5])
    return


def E():
    return


def F():
    return


if __name__ == '__main__':
    D()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(S):
    M = Mod(10**9 + 7)
    M13 = Mod(13)
    t = [0] * 13
    t[0] = 1
    for i, c in enumerate(reversed(S)):
        if c != '?':
            n = M13.mul(M13.pow(10, i), int(c))
            nt = [0] * 13
            for k in range(13):
                nt[(k+n) % 13] = t[k]
            t = nt
        else:
            nt = [0] * 13
            for j in range(10):
                n = M13.mul(M13.pow(10, i), j)
                for k in range(13):
                    nt[(k+n) % 13] = M.add(nt[(k+n) % 13], t[k])
            t = nt
    return t[5]


def main():
    S = read_str()
    print(slv(S))


if __name__ == '__main__':
    main()