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):
MOD = 10 ** 9 + 7

S = input().strip()

N = 13

dp = [0] * N
dp[0] = 1

for i in range(len(S)):
  next_dp = [0] * N
  c = S[i]
  if c == '?':
    for k in range(10):
      for j in range(N):
        next_dp[(j * 10 + k) % N] += dp[j]
        next_dp[(j * 10 + k) % N] %= MOD
  else:
    k = int(c)
    for j in range(N):
      next_dp[(j * 10 + k) % N] += dp[j]
      next_dp[(j * 10 + k) % N] %= MOD

  dp = next_dp

print(dp[5])

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

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


mod = 10**9+7

table = [1,10,9,12,3,4]



dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*table[i%6]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

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


mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Solution (Python):
import copy

s = input()
dp = [0 for i in range(13)]
dp[0] = 1
num = 0
c = 1000000007
mul = 1
for i in range(len(s) - 1, -1, -1):
    nextdp = [0 for i in range(13)]
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                nextdp[(j * mul + k) % 13] += dp[k]
                nextdp[(j * mul + k) % 13] %= c
    else:
        j = int(s[i])
        for k in range(13):
            nextdp[(j * mul + k) % 13] += dp[k]
            nextdp[(j * mul + k) % 13] %= c
    dp = copy.copy(nextdp)
    mul *= 10
    mul %= 13

print(dp[5])

Solution (Python):


import sys

sys.setrecursionlimit(10**7)


input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    S, = read_h(typ=str)
    n = len(S)

    MOD = 10**9 + 7

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

    for i, s in enumerate(S):
        c = -1 if s == '?' else ord(s) - ord('0')
        

        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

        

    res = dp[n][5]
    print(res)


if __name__ == '__main__':
    main()

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)
    t = [0] * 13
    t[0] = 1
    m = 1
    for i, c in enumerate(reversed(S)):
        if c != '?':
            n = (m * int(c)) % 13
            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 = (m * j) % 13
                for k in range(13):
                    nt[(k+n) % 13] = M.add(nt[(k+n) % 13], t[k])
            t = nt
        m *= 10
        m %= 13
    return t[5]


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


if __name__ == '__main__':
    main()

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

mod = [0] * (L+1)
mod[0] = 1
for i in range(1, L+1):
  mod[i] = (mod[i-1] * 10) % 13
MOD = 10 ** 9 + 7

dp = [[0]*13 for i in range(L)]
flag = True

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

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

print(dp[-1][5])

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

case = [1] + [0] * 12
temp = [0] * 13
unit = 1
before = 0
for i in reversed(range(len(S))):
    if(S[i] == '?'):
        for k in range(13):
            for j in range(10):
                before = (k - unit * j) % 13
                temp[k] += case[before]
            temp[k] %= M
    else:
        for k in range(13):
            before = (k - unit * int(S[i])) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13
    temp = [0] * 13

print(case[5])

Solution (Python):
import sys
import numpy as np

MOD = 1000000007
S = np.frombuffer(sys.stdin.buffer.read(), dtype=np.int8)
S = S[:-1][::-1] - 48

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10), (6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
    f[i, 0, c[i]] = 1
    for j in range(12):
        f[i, j + 1] = np.roll(f[i, j], 1)

dp = np.zeros(13, dtype=np.int64)
dp[0] = 1
digit = 0
count = 0

for i, c in enumerate(S):
    k = i % 6
    if c == 15:
        dp = np.dot(dp, f[k]) % MOD
    else:
        digit += a[k] * c

m = (5 - digit) % 13
print(dp[m])

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

S = input()

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

for i, s in enumerate(S):
	pattern = range(10) if s == "?" else [int(s)]
	for p in pattern:
		for j in range(13):
			mod = (j * 10 + p) % 13
			dp[i + 1][mod] += dp[i][j]
			dp[i + 1][mod] %= MOD
print(dp[-1][5])

Solution (Python):
s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])

Solution (Python):


S = input()
N = len(S)
mod = 10**9+7


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

dp[0][0] = 1

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

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

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

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

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

print(dp[n][5])

Solution (Python):
S = input()

MOD = 10 ** 9 + 7

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

Solution (Python):
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mod = 10 ** 9 + 7
    mul = 1
    s.reverse()

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mod = 10 ** 9 + 7

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(j*10+k)%13] += dp[j]
                    next_dp[(j*10+k)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[(j*10+k)%13] += dp[j]
                    next_dp[(j*10+k)%13] %= mod

    
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Solution (Python):
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


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

Solution (Python):
d={i:0 for i in range(13)}
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2={i:0 for i in range(13)}
        for i in range(10):
            u=i*pow(10,k,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,k,13)
        d2={i:0 for i in range(13)}
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

Solution (Python):
d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=i*pow(10,k,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,k,13)
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

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

s = input()

cur = [0] * 13
cur[0] = 1
d = 1
for c in s[::-1]:
    if c != '?':
        l = [int(c)]
    else:
        l = [j for j in range(10)]
    tmp = [0] * 13
    for j in l:
        for k in range(13):
            ind = (j * d + k) % 13
            tmp[ind] += cur[k]
            tmp[ind] %= mod
    cur = tmp
    d *= 10
    d %= 13
print(cur[5])

Solution (Python):
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)

Solution (Python):
import numpy as np

MOD = 1000000007
S = input()[::-1]

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10),(6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
    f[i, 0, c[i]] = 1
    for j in range(12):
        f[i, j + 1] = np.roll(f[i, j], 1)

prev = np.zeros(13, dtype=np.int64)
prev[0] = 1
digit = 0

for i, c in enumerate(S):
    k = i % 6
    if c == '?':
        cur = np.dot(prev, f[k]) % MOD
        prev, cur = cur, prev
    else:
        digit += a[k] * (ord(c) - ord('0'))

m = (5 - digit) % 13
print(prev[m])

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

Solution (Python):
def resolve():

    s = input()
    n = len(s)

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

    for i in range(n):

        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] %= 1000000007

    print(dp[n][5])
    
resolve()

Solution (Python):

MOD=10**9+7
s=input()
s.rstrip()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1

coef=1
for i in range(len(s)):
    if s[i]=='?':
        for j in range(13):
            for k in range(10):
                ind=(j+coef*k)%13
                temp=dp[i+1][ind]+dp[i][j]
                dp[i+1][ind] = temp-MOD if temp>=MOD else temp
    else:
        si=int(s[i])
        for j in range(13):
            ind=(j+coef*si)%13
            temp=dp[i+1][ind]+dp[i][j]
            dp[i+1][ind] = temp-MOD if temp>=MOD else temp
    coef=coef*10%13


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

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = [x % 13 for x in range(0, p * 10, p)] if c == '?' else (p * int(c) % 13,)
    a = [sum(a[(i - j, i - j + 13)[i < j]] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
def resolve():
    ss = input()

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

    mod = 10 ** 9 + 7
    mul = 1

    
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod

        mul *= 10
        mul %= 13
        dp = next_dp

    print(dp[5])
    
resolve()

Solution (Python):

MOD = 10 ** 9 + 7

S = input()

mods = [0] * 13
mods[0] = 1

digit = 1
for s in S[::-1]:
    next_mods = [0] * 13
    if s == '?':
        for i in range(10):
            for m in range(13):
                next_mods[(m + i * digit) % 13] += mods[m]
    else:
        for m in range(13):
            next_mods[(m + int(s) * digit) % 13] += mods[m]

    for m in range(13):
        next_mods[m] %= MOD
    mods = next_mods
    digit *= 10
    digit %= 13    

ans = mods[5]

print(ans)

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c == '?':
        b = a[:]
        for j in range(-p, -p * 10, -p):
            j %= 13
            a = [sum(x) % M for x in zip(a, b[j:] + b[:j])]
    elif c > '0':
        j = -p * int(c) % 13
        a = a[j:] + a[:j]
    p = p * 10 % 13
print(a[5])

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

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

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




print(dp[-1][5])

Solution (Python):
s = input()
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
s= '0'+s
dp[0][0] =1
mod = 1000000007
def factory (i,j):
    for premod in range(13):
        curMod = (premod*10+j)%13
        dp[i][curMod]+=dp[i-1][premod]
        dp[i][curMod]%=mod
for i in range(1,len(s)):
    if s[i]!='?':
        factory(i,int(s[i]))
    else:
        for num in range(10):
            factory(i,num)
print(dp[len(s)-1][5]%mod)

Solution (Python):

def solve():
  s = input()
  n  = len(s)
  mod = 10**9+7
  reverses = s[::-1]
  if reverses[0] != "?":
    tmp = int(reverses[0])
    query = [0 for i in range(13)]
    query[tmp] += 1
  else:
    query = [0 for i in range(13)]
    for i in range(10):
      query[i] += 1
      
  digit = 1
  tmp = [0 for i in range(13)]
  for i in range(1,n):
    digit *= 10
    digit %= 13
    tmp = [0 for i in range(13)]
    
    if reverses[i] =="?":
      for k in range(10):
        for j in range(13):
          tmp[(k*digit + j)%13] += query[j]
      
    else:
      for j in range(13):
        tmp[(digit*int(reverses[i])+j)%13] += query[j]

    for i in range(13):
      tmp[i] %= mod
    query = tmp 
      
  print(query[5])
if __name__ == '__main__':
  solve()

Solution (Python):
def solve():
  s = input()
  n  = len(s)
  mod = 10**9+7
  reverses = s[::-1]
  
  query = [0 for i in range(13)]
  if reverses[0] != "?":
    tmp = int(reverses[0])
    query = [0 for i in range(13)]
    query[tmp] += 1
  else:
    for i in range(10):
      query[i] += 1
  digit = 1
  
  for i in range(1,n):
    digit *= 10
    digit %= 13
    tmp = [0 for _ in range(13)]
    
    if reverses[i] =="?":
      for k in range(10):
        for j in range(13):
          num = k*digit
          num += j
          num %= 13
          tmp[num] += query[j]
      
    else:
      for j in range(13):
        num = digit*int(reverses[i])
        num += j
        num %= 13
        tmp[num] += query[j]

    for i in range(13):
      tmp[i] %= mod
    query = tmp 
      
  print(query[5])
solve()

Solution (Python):
s = input()

mod = 1000000007
n = 13

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

mul = 1
for i in reversed(range(len(s))):
    nextDp = [0] * 13
    if s[i] == '?':
        for k in range(10):
            for j in range(n):
                nextDp[(k * mul + j) % n] += dp[j]
        for j in range(n):
            nextDp[j] %= mod
    else:
        k = int(s[i])
        for j in range(n):
            nextDp[(k * mul + j) % n] = dp[j]

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5])

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

def main():
	mod = 10**9 + 7
	N = 13
	dp = [0] * N
	dp[0] = 1
	s = input().strip()
	mul = 1
	for i in reversed(range(len(s))):
		
		nextdp = [0] * N
		if s[i] == '?':
			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(s[i])
			
			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])

if __name__ == '__main__':
	main()

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in input()[::-1]:
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for k, c in enumerate(reversed(input())):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
b = 1, 10, 9, 12, 3, 4
for k, c in enumerate(reversed(input())):
    p = b[k % 6]
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c > '0':
        r = range(0, p * 10, p) if c == '?' else (p * int(c),)
        a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

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

n = len(s)
dp = [0] * 13
dp[0] = 1

for i in range(n):
    prev = dp[:]
    dp = [0]*13

    if s[i] == '?':
        for z in range(10):
            for j in range(13):
                dp[(j*10+z)%13] += prev[j]
                dp[(j*10+z)%13] %= 10**9+7

    else:
       _s = int(s[i])
       for j in range(13):
            dp[(j*10+_s)%13] += prev[j]
            dp[(j*10+_s)%13] %= 10**9+7

print(dp[5])

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c == '?':
        a = [sum(x) % M for x in zip(*(a[j % 13:] + a[:j % 13]
                              for j in range(0, -p * 10, -p)))]
    elif c > '0':
        j = -p * int(c) % 13
        a = a[j:] + a[:j]
    p = p * 10 % 13
print(a[5])

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

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)

Solution (Python):
S = input()
dp = []
for i in range(0, len(S)+1):
	lst = []
	for i in range(0, 13):
		lst.append(0)
	dp.append(lst)
dp[0][0] = 1
for i in range(0, len(S)):
	if S[i] == '?':
		for j in range(0, 10):
			for k in range(0, 13):
				dp[i+1][(10*k+j)%13] += dp[i][k]
				dp[i+1][(10*k+j)%13] %= 10**9 + 7
	else:
		for j in range(0, 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[len(S)][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(1,N+1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j*10+k)%13] += dp[i-1][j]
                dp[i][(j*10+k)%13] %= MOD
    else:
        t = int(S[i-1])
        for j in range(13):
            dp[i][(j*10+t)%13] += dp[i-1][j]
            dp[i][(j*10+t)%13] %= MOD

print(dp[N][5])

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

Solution (Python):
S = [int(x) if x != "?" else -1 for x in 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] == -1:
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+S[i])%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w += DP[0][j]
        DP[0][j] = w

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

Solution (Python):
S = input()

MOD = 10 ** 9 + 7

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

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

S = input()

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

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

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

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

cur = [0] * 13
cur[0] = 1
r = 1
base = 0
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        prev = cur
        cur = [sum(prev)] * 13
        for m in range(13):
            for d in range(10,13):
                cur[(m + r*d) % 13] -= prev[m]
        for m in range(13):
            cur[m] %= MOD
    else:
        base = (base + r*int(s)) % 13

    r = (10 * r) % 13

print(cur[(5-base) % 13])

Solution (Python):
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  rt = [i % 13 for i in range(100)]
  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
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      for j in range(10):
        r = multiplier * j % 13
        for k in list13:
          np[rt[k + r]] += p[k]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

Solution (Python):
S = input()

MOD=(10**9) + 7
N=13

dp=[[0 for i in range(N)] for j in range(100005)]
dp[0][0] = 1

dpi = 1
mul = 1

for c in S[::-1]:    
    for i in range(N):
        if c=='?':
            for j in range(10):
                ii = (i + (j*mul)) % N
                dp[dpi][ii] += dp[dpi-1][i] % MOD
                
        else:
            j = int(c)
            ii = (i + (j*mul)) % N
            dp[dpi][ii] += dp[dpi-1][i] % MOD
            
    mul *= 10
    mul %= N
    dpi += 1

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

Solution (Python):

"""解説
dp

dp[i][j] := 先頭i文字として考えられるもののうち、13で割ったあまりがjであるものの数

1?2?3 を分解すると、
10000 ≡ 3
 A000 ≡ A*(10**3) % MOD ≡ A*12
  200 ≡ 5
   B0 ≡ B*(10**1) % MOD
    3 ≡ 3
    -----
        11 + ? ≡ 11 + A*12 + B*10

"""


def solve():
    S = input()
    MOD = 10**9+7

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

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

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


if __name__ == "__main__":
    solve()