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):
from sys import stdin
s = stdin.readline()[:-1]

length = len(s)

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

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

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

s = str(input())

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



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

print(dp[-1][5])

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

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

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

s = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(s)):
    dp2 = [0] * 13
    for j in range(10):
        if (s[i] == '?') | (s[i] == str(j)):
            for k in range(13):
                dp2[(10 * k + j) % 13] += dp[k]
                dp2[(10 * k + j) % 13] %= mod
    dp = dp2
print(dp[5])

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 in range(n):
    if s[i] == '?':
        for r in range(13):
            for d in range(10):
                r1 = (r * 10 + d) % 13
                dp[i + 1][r1] += dp[i][r]
                dp[i + 1][r1] %= MOD
    else:
        for r in range(13):
            r1 = (r * 10 + int(s[i])) % 13
            dp[i + 1][r1] += dp[i][r]
            dp[i + 1][r1] %= MOD

ans = dp[n][5]

print(ans)

Solution (Python):
S = input()
MOD = 10**9+7
N = 13
mul = 1


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



for i in range(len(S)-1, -1, -1):
    
    next_dp = [0] * N
    c = S[i]

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

    else:
        k = int(S[i])
        for j in range(N):
            next_dp[(k * mul + j) % N] += dp[j]
            next_dp[(k * mul + j) % N] %= MOD

    mul *= 10
    mul %= N
    dp = next_dp

print(dp[5])

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    S = S[::-1]

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

    for c in S:
        dp, dp_prev = [0] * 13, dp
        for k in range(13):
            if c == '?':
                for j in range(10):
                    dp[(p * j + k) % 13] = (dp[(p * j + k) % 13] + dp_prev[k]) % MOD
            else:
                dp[(p * int(c) + k) % 13] = (dp[(p * int(c) + k) % 13] + dp_prev[k]) % MOD

        p = p * 10 % 13

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    S = S[::-1]

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

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

        p = p * 10 % 13

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)
    power = [0] * N
    power[0] = 1
    for i in range(N - 1):
        power[i + 1] = 10 * power[i] % 13

    S = S[::-1]

    Q = []
    const = 0
    for i, c in enumerate(S):
        if c == '?':
            Q.append(i)
        else:
            const = (const + power[i] * int(c)) % 13

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

    for i in range(len(Q)):
        dp, dp_prev = [0] * 13, dp
        p = power[Q[i]]
        for j in range(10):
            for k in range(13):
                idx = (p * j + k) % 13
                dp[idx] = (dp[idx] + dp_prev[k]) % MOD

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)
    power = [0] * N
    power[0] = 1
    for i in range(N - 1):
        power[i + 1] = 10 * power[i] % 13

    S = S[::-1]

    Q = [i for i, c in enumerate(S) if c == '?']
    M = len(Q)

    const = 0
    for i, c in enumerate(S):
        if c != '?':
            const = (const + power[i] * int(c)) % 13

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

    for i in range(M):
        dp, dp_prev = [0] * 13, dp
        p = power[Q[i]]
        for j in range(10):
            for k in range(13):
                idx = (p * j + k) % 13
                dp[idx] = (dp[idx] + dp_prev[k]) % MOD

    print(dp[5])
    return


if __name__ == '__main__':
    main()

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

s = input()
n = len(s)

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

for i in range(n):
  dp2 = [0]*13  
  for j in range(10):
    if s[i] == '?' or s[i] == str(j):
      for k in range(13):
        dp2[(k*10 + j)%13] += dp[k]
        dp2[(k*10 + j)%13] %= mod
        
  dp = dp2

print(dp[5])

Solution (Python):
s = input()
 
mod = 10**9+7
n = len(s)
res = [1] + [0] * 12
for ss in s:
    dp = [0] * 13
    for i in range(13):
        dp[(10*i)%13] = res[i]
    dp += dp
 
    if ss == '?':
        for i in range(13):
            res[i] = sum(dp[i+4:i+14])
    else:
        for i in range(13):
            res[i] = dp[i+13-int(ss)]
    res = [v%mod for v in res]
print(res[5])

Solution (Python):
s = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(s))]
t = [1]
for i in range(len(s)-1):
    t.append(t[-1]*10%13)
t.reverse()

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

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

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    MOD=10**9+7
    S=input().strip("\n")
    q=[]
    g=0
    S=S[::-1]
    m13=(1,10,9,12,3,4)
    for i in range(len(S)):
        if S[i] == "?":
            q.append(m13[i%6])
        else:
            x=int(S[i])
            g+=x*m13[i%6]
            g%=13
    if len(q)==0:
        if g==5:
            print(1)
        else:
            print(0)
        exit()
    N=len(q)
    q=[0]+q
    dp=[[0]*13 for i in range(N+1)]
    for j in range(10):
        dp[1][(j*q[1])%13]=1
    for i in range(2,N+1):
        for j in range(13):
            for k in range(10):
                x=(j-k*q[i])%13
                dp[i][j]+=dp[i-1][x]
                dp[i][j]%=MOD
    print(dp[N][(5-g)%13])
    
if __name__=="__main__":
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().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)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(S):
    memo = [0] * 13
    memo[0] = 1
    mod = 10**9 + 7
    for c in S:
        nm = [0] * 13
        if c == '?':
            r = range(10)
        else:
            r = [int(c)]
        for d in r:
            for i in range(13):
                nm[(i*10+d) % 13] += memo[i]
                nm[(i*10+d) % 13] %= mod
        memo = nm
    return memo[5]


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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
 
MOD = 1000000007  
 
 
def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = [0] * 13, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, pre
        for i in range(13): 
            cur[i] = 0
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        
    return cur[5]
 

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    print(solve(S))
 
def test():
    import doctest
    doctest.testmod()
 
if __name__ == '__main__':
    
    main()

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

Solution (Python):
s = input()

mod = 10**9+7
n = len(s)
res = [1] + [0] * 12
for ss in s:
    dp = [0] * 13
    for i in range(13):
        dp[(10*i)%13] = res[i]
    dp += dp

    if ss == '?':
        for i in range(13):
            res[i] = sum(dp[i+4:i+14])
    else:
        for i in range(13):
            res[i] = dp[i+13-int(ss)]
    res = [v%mod for v in res]
print(res[5])

Solution (Python):
s = input()

mod = 10**9+7
n = len(s)
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]
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13] += dp[i][k]
    for k in range(13):
        dp[i+1][k] %= mod
print(dp[n][5])

Solution (Python):







import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    s = str(input())
    ls = len(s)
    dp = [[0]*13 for _ in range(ls+1)]
    dp[0][0] = 1
    MOD = 10**9+7

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

    print(dp[ls][5])


resolve()

Solution (Python):


LI = lambda: list(map(int, input().split()))


S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
S = input()[::-1]
L = len(S)
MOD = 10**9+7
N = 13

dp = [ [0]*13 for i in range(L+1)]
dp[0][0] = 1
mul = 1

for i in range(L):
  if S[i] == "?":
    for prev in range(N):
      for j in range(10):
        dp[i+1][(j*mul+prev)%N] += dp[i][prev]
        dp[i+1][(j*mul+prev)%N] %= MOD
  else:
    j = int(S[i])
    for prev in range(N):
      dp[i+1][(j*mul+prev)%N] += dp[i][prev]
      dp[i+1][(j*mul+prev)%N] %= MOD
  
  mul *= 10
  mul %= N

print(dp[-1][5])

Solution (Python):
from sys import stdin
import numpy as np
def main():
    
    readline=stdin.readline
    mod=10**9+7
    s=readline().strip()
    n=len(s)

    convert=[[0]*13 for i in range(13)]
    for a in range(13):
        for b in range(10):
            convert[a][(10*a+b)%13]=1

    convert=np.array(convert,dtype=np.int64)
    dp=np.zeros(13,dtype=np.int64)
    dp[0]=1
    for i in range(n):
        if s[i]=="?":
            tmp=np.dot(dp,convert)
        else:
            x=int(s[i])
            tmp=np.zeros(13,dtype=np.int64)
            for j in range(13):
                tmp[(j*10+x)%13]=dp[j]
        tmp%=mod
        dp=tmp

    print(dp[5])
    
if __name__=="__main__":
    main()

Solution (Python):
a = list(range(13))
b = []
for i in a:
    num = int(str(i) + '0') % 13
    l = []
    for j in range(13):
        l.append((num+j)%13)
    b.append(l)

s = input()
MOD = 10**9+7
dp = [[0 for _ in range(13)] for _ 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):
            for k in range(10):
                dp[i][b[j][k]] += dp[i-1][j]
                dp[i][b[j][k]] %= MOD
    else:
        for j in range(13):
            n = b[j][int(s[i])]
            dp[i][n] += dp[i-1][j]
            dp[i][n] %= MOD
print(dp[-1][5]%MOD)

Solution (Python):
def main():
    s=input()
    n = len(s)
    dp = [[0]*(13) for _ in range(100005)]
    MOD = 10**9 + 7
    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
    res = dp[n][5]

    print(res)





if __name__ == '__main__':
    main()

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

mod = 10**9 + 7

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

for i in range(1, N+1):
    if S[i-1] == "?":
        for j in range(10):
            tmp_mod = (j * pow(10, i-1, 13)) % 13
            for k in range(13):
                dp[i][k] = (dp[i][k] + dp[i-1][k-tmp_mod%13]) % mod

    else:
        tmp_mod = (int(S[i-1]) * pow(10, i-1, 13)) % 13
        for k in range(13):
            dp[i][k] = (dp[i][k] + dp[i-1][k-tmp_mod%13]) % mod

print(dp[N][5])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
def SMI(): return input().split()
def SLI(): return list(input())
 
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
 






 
def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD
 
        mul = mul * 10 % 13
    
    print(dp[-1][5] % MOD)
 
if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')








def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        
        
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')








def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        
        s = S[i]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')








def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    R = S[::-1]
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')








def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')








def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

    S = input()
    S = S[::-1]
    MOD = 10 ** 9 + 7

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

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

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])


if __name__ == '__main__':
    solve()

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(l):
    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[-1][5] % mod)

Solution (Python):
mod = 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] %= mod
    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] %= mod
    mul = mul * 10 % 13

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

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 in range(n):
    digit = n-1-i
    x = s[digit]
    X = []
    if x != '?':
        X.append(int(x)*pow(10, i, 13) % 13)
    else:
        for num in range(10):
            X.append(num*pow(10, i, 13) % 13)
    for j in range(13):
        for x in X:
            dp[i+1][(j+x) % 13] += dp[i][j]
            dp[i+1][(j+x) % 13] %= MOD

print(dp[-1][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):
    for j in range(13):
        if S[i] == '?':
            for k in range(10):
                dp[i+1][ (10*j+k)%13 ] += dp[i][j]
        else:
            k = int(S[i])
            dp[i+1][ (10*j+k)%13 ] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD
print(dp[N][5])

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

s = input()
s = list(reversed(s))

mods = [0 for _ in range(13)]
mods[0] = 1

x = 1
MOD = 10 ** 9 + 7
for c in s:
    new_mods = [v for v in mods]
    val = 0
    if c == '?':
        for i in range(1, 10):
            val = i * x % 13
            for j in range(13):
                new_mods[j] += mods[j - val] % MOD
    else:
        val = int(c) * x % 13
        for i in range(13):
            new_mods[i] = mods[i - val] % MOD

    mods = new_mods
    
    x *= 10
    x %= 13
print(mods[5] % MOD)

Solution (Python):
class Mod13DPTable:
    MOD = 10**9 + 7
    def __init__(self, length):
        self.mod13 = [{j:0 for j in range(13)} for i in range(length)]
        self.MOD = 10**7 + 7
    def set_start(self, units_digit):
        if units_digit == '?':
            for i in range(10):
                self.mod13[0][i] = 1
        else:
            self.mod13[0][int(units_digit)] = 1
    def get_table(self, digit):
        return self.mod13[digit]
    def update(self, num, digit, multi):  
        for k, v in self.mod13[digit-1].items():
            remain = ((num * multi) + k) % 13
            self.mod13[digit][remain] = (self.mod13[digit][remain] + v) % Mod13DPTable.MOD
            
def main():
    MOD = 10**9 + 7
    S = input()
    mod13dp = Mod13DPTable(len(S))
    mod13dp.set_start(S[-1])
    multi = 10
    for i, m in enumerate(reversed(list(S[:-1]))):
        i += 1
        if m == '?':
            for j in range(10):
                mod13dp.update(j, i, multi)
        else:
            mod13dp.update(int(m), i, multi)
        multi = multi*10 % 13
    print(mod13dp.get_table(-1)[5])
main()

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):
    x = s[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(10 * j + k) % 13] += dp[i][j]
                dp[i + 1][(10 * j + k) % 13] %= MOD
        else:
            k = int(x)
            dp[i + 1][(10 * j + k) % 13] += dp[i][j]
            dp[i + 1][(10 * j + k) % 13] %= MOD

print(dp[n][5])

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

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):
                p=(k+10*j)%13
                dp[i+1][p]+=dp[i][j]
                dp[i+1][p]%=mod

    else:

        for j in range(13):
            p=(int(s[i])+10*j)%13
            dp[i+1][p]+=dp[i][j]
            dp[i+1][p]%=mod


print(dp[n][5])

Solution (Python):
def main():
    s = input()
    mod = 13
    p = 10 ** 9 + 7
    dp = [0] * mod
    dp[0] = 1

    for i, ss in enumerate(s):
        tmp = [0] * mod
        if ss == "?":
            for j in range(10):
                for k in range(mod):
                    d = (10 * k + j) % mod
                    tmp[d] += dp[k]
                    tmp[d] %= p
        else:
            for k in range(mod):
                d = (10 * k + int(ss)) % mod
                tmp[d] += dp[k]
        dp = tmp
    print(dp[5])
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    s = input()[::-1]
    mod = 13
    p = 10 ** 9 + 7
    dp = [0] * mod
    dp[0] = 1

    for i, ss in enumerate(s):
        tmp = [0] * mod
        if ss == "?":
            for j in range(10):
                d = j * pow(10, i, mod)
                for k in range(mod):
                    tmp[(k + d) % mod] += dp[k]
                    tmp[(k + d) % mod] %= p
        else:
            d = int(ss) * pow(10, i, mod)
            for k in range(mod):
                tmp[(k + d) % mod] += dp[k]
        dp = tmp
    print(dp[5])
if __name__ == '__main__':
    main()