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

Solution (Python):
S=input()
import numpy as np
M=13
MOD=10**9+7
dp=np.zeros(M, dtype=np.int64)
dp[0]=1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
  idx[i * 10 % M] = i
for s in S:
  if s=='?':
    tdp=dp[idx]
    ndp = np.concatenate([tdp[4:], tdp])
    dp = np.convolve(ndp, window, mode='valid') % MOD
  else:
    dp=np.roll(dp[idx],int(s))
print(dp[5]%MOD)

Solution (Python):

s=raw_input()
mod=10**9+7
res=[0]*13
res[0]=1
for i in s:
 dp=[0]*13
 for j in range(13):
  dp[(j*10)%13]=res[j]%mod
 dp+=dp
 if i=='?':
  for k in range(13):
   res[k]=sum(dp[k+4:k+14])
 else:
  for k in range(13):
   res[k]=dp[k+13-int(i)]
print res[5]%mod

Solution (Python):
S = input().strip()
mod = 10**9 + 7
d = [i*10%13 for i in range(13)]
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
for i, c in enumerate(S, 1):
    if c != '?':
        c = int(c)
        for j in range(13):
            dp[i][(d[j] + c) % 13] = dp[i-1][j]
    else:
        for c in range(10):
            for j in range(13):
                k = (d[j] + c) % 13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] %= mod
print(dp[-1][5])

Solution (Python):
S = input().strip()
mod = 10**9 + 7
d = {i:i*10%13 for i in range(13)}
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
for i, c in enumerate(S, 1):
    if c != '?':
        c = int(c)
        for j in range(13):
            dp[i][(d[j] + c) % 13] = dp[i-1][j] % mod
    else:
        for c in range(10):
            for j in range(13):
                k = (d[j] + c) % 13
                dp[i][k] = (dp[i][k] + dp[i-1][j]) % mod
print(dp[-1][5])

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

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
        mul %= 13
    print(dp[5])
main()

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

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

S = input()
S = S[::-1]
LS = len(S)

MOD = 10 ** 9 + 7


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

for i in range(LS):
    if S[i] != '?':
        d = int(S[i])
        md = (d * pow(10, i, 13)) % 13

        if md == 0:
            dp[i + 1] = dp[i]
        else:
            dp[i + 1][md:] = dp[i][:-md]
            dp[i + 1][:md] = dp[i][-md:]
    else:
        t = pow(10, i, 13)
        for k in range(10):
            md = (k * t) % 13

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

print(dp[LS][5])

Solution (Python):
s = input()
dp = [1] + [0] * 12
for c in s:
    newdp = [0] * 13
    for d in range(10) if c == '?' else [int(c)]:
        for m in range(13):
            m2 = (m * 10 + d) % 13
            newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
    dp = newdp
print(dp[5])

Solution (Python):
import copy
s=input()
a=0
n=len(s)
x=[0]*13
if s[-1]=='?':
  x = [int(i<=9) for i in range(13)]
else:
  x[int(s[-1])%13]=1
p=1
for i in range(1,n):
  p=10*p%13
  y=[0]*13
  if s[n-1-i]=='?':
    for j in range(13):
      for k in range(10):
        y[(k*p+j)%13]+=x[j]
  else:
    t=int(s[n-1-i])
    for j in range(13):
      y[(t*p+j)%13]+=x[j]
  x=copy.deepcopy(y)
  x = [z%(10**9+7) for z in x]
print(x[5])

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


dp = [[0]*13 for _ in range(len(s)+1)]
dp[0][0] = 1
mul = 1
s_rev = s[::-1]
for i in range(len(s)):
    x = s_rev[i]
    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] % mod)

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


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

Solution (Python):

s = input()
s = s[::-1]
MOD = 10**9+7
mod13_map = [[i for i in range(13)]]
ma = mod13_map.append
for i in range(1,10**5):
    next_digit = list(map(lambda x:x*10%13,mod13_map[i-1]))
    ma(next_digit)

ret = [1] + [0] * 12 
for i,v in enumerate(s):
    if v!="?":
        
        ret *= 2
        sft = mod13_map[i][int(v)]
        ret = ret[13-sft:26-sft]
    else:
        temp_ret = [0] * 13
        for j in range(10):
            
            for k,l in enumerate(ret):
                temp_ret[(k+mod13_map[i][j])%13]+=l
        temp_ret = list(map(lambda x:x%MOD,temp_ret))
        ret = temp_ret
print(ret[5]%MOD)

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


s = input()

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

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

print(DP[n][5])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()

dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        loop = range(10)
    else:
        loop = [int(s)]
    for j in range(13):
        for lo in loop:
            dp[(10*j+lo)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()

dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    num = s
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()

dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s != '?':
        s = int(s)
        for j in range(13):
            dp[(10*j+s)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)

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

dp = [0]*13
dp[0] = 1
r = 1
for c in S[::-1]:
    dp2 = [0]*13
    for p in range(13):
        if c =='?':
            for d in range(10):
                k = (d*r+p)%13
                dp2[k] += dp[p]
        else:
            d = int(c)
            k = (d*r+p)%13
            dp2[k] += dp[p]
    for k in range(13):
        dp2[k] %= MOD
    r *= 10
    r %= 13
    dp = dp2
print(dp[5])

Solution (Python):
S = input()
dp = [[0] * 13 for _ in range(10 ** 5 + 5)]
MOD = 10 ** 9 + 7
dp[0][0] = 1
n = len(S)
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 ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]

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

print(dp[n][5])

Solution (Python):
import sys
from heapq import heappush, heappop


def main():
    s=list(input())
    n=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ in range(n)]
    if s[0]=='?':
        dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[0][int(s[0])]=1
    for i in range(1,n):
        for j in range(13):
            if s[i]=='?':
                for k in range(10):
                    x=(j*10+k)%13
                    dp[i][x]+=dp[i-1][j]
                    dp[i][x]%=mod
            else:
                x=(j*10+int(s[i]))%13
                dp[i][x]+=dp[i-1][j]
                dp[i][x]%=mod
    print(dp[n-1][5])

if __name__ == '__main__':
    main()

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

for i in range(1,N+1):
    R = [0]*13
    if S[i-1] == "?":
        for j in range(10):
            r = j * pow(10,N-i,13) %13 
            R[r] += 1 

    else:
        r = int(S[i-1]) * pow(10,N-i,13) %13
        R[r] += 1

    for k in range(13):
                for l in range(13):
                    dp[i][k] += dp[i-1][l] * R[(k-l)%13]
                    dp[i][k] %= MOD

print(dp[N][5])

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

for i in range(1,N+1):
    R = [0]*13
    if S[i-1] == "?":
        for j in range(10):
            r = j * pow(10,N-i,13) %13 
            R[r] += 1 
        for k in range(13):
            for l in range(13):
                    dp[i][k] += dp[i-1][l] * R[(k-l)%13]
                    dp[i][k] %= MOD

    else:
        r = int(S[i-1]) * pow(10,N-i,13) %13
        R[r] += 1
        for k in range(13):
                for l in range(13):
                    dp[i][k] += dp[i-1][l] * R[(k-l)%13]
                    dp[i][k] %= MOD

print(dp[N][5])

Solution (Python):

S = input()[::-1]

MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)


def mod13_of_10pow(i):
    return [1, 10, 9, 12, 3, 4][i % 6]




ans = [modint(0)] * 13

for i, c in enumerate(S):
    if i == 0:
        if c != '?':
            ans[int(c)] += 1
        else:
            for q in range(10):
                ans[q] += 1
        continue

    tmp = [modint(0)] * 13

    m = mod13_of_10pow(i)
    ds = [int(c)] if c != '?' else [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for d in ds:
        for k in range(13):
            tmp[(k + d * m) % 13] += ans[k]

    ans = tmp

print(ans[5])

Solution (Python):
s = input()
n = len(s)
MOD = 13
MOD2 = 10 ** 9 + 7

dp = [[0] * 13 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n, ):
    keta = pow(10, n - i - 1, MOD)
    if s[i] == "?":
        for si in range(10):
            for j in range(MOD):
                dp[i + 1][(j + si * keta) % MOD] += dp[i][j]
                dp[i + 1][(j + si * keta) % MOD] %= MOD2
    else:
        for j in range(MOD):
            dp[i + 1][(j + int(s[i]) * keta) % MOD] += dp[i][j]
            dp[i + 1][(j + int(s[i]) * keta) % MOD] %= MOD2
print(dp[-1][5])

Solution (Python):
S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(N + 1)]
dp[0][0] = 1
mod = 10**9+7
pow10 = 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 + k*pow10) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*pow10) % 13] = dp[i-1][j]
    pow10 = (pow10 * 10) % 13
    for j in range(13):
        dp[i][j] %= mod

print(dp[N][5])

Solution (Python):

"""
D - Digits Parade
https://atcoder.jp/contests/abc135/tasks/abc135_d

"""
import sys


def solve(S):
    dp = [[0] * 13 for _ in range(len(S)+1)]
    dp[0][0] = 1
    for i, ch in enumerate(S):
        for j in range(10):
            if ch == '?' or j == int(ch):
                for ki in range(13):
                    dp[i+1][(ki*10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i+1][j] %= (10**9 + 7)
    return dp[len(S)][5]


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

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

S = list(input())
N = len(S)


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

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]
    else:
        x = ord(S[i - 1]) - ord('0')
        for j in range(13):
            dp[i][(j * 10 + x) % 13] += dp[i - 1][j]
    for j in range(13):
        dp[i][j] %= 1000000007
print(dp[-1][5])

Solution (Python):

"""
D - Digits Parade
https://atcoder.jp/contests/abc135/tasks/abc135_d

"""
import sys


def solve(S):
    dp = [[0] * 13 for _ in range(len(S)+1)]
    dp[0][0] = 1
    for i, ch in enumerate(S):
        c = -1 if ch == '?' else int(ch)
        for j in range(10):
            if (c != -1 and c != j):
                continue
            for ki in range(13):
                dp[i+1][(ki*10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i+1][j] %= (10**9 + 7)
    return dp[len(S)][5]


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

MOD = 10 ** 9 + 7

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

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

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

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys


import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m in range(len(S))]
mod=10**9+7
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)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
    for m in range(13):
        dp[i][m]%=mod

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

Solution (Python):
def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


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

        ten = (ten*10)%13

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

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

Solution (Python):
mod = 10**9+7
s = input()[::-1]
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
dp[0][0] = 1
ten = 1
for i in range(len(s)):
    if s[i]=="?":
        for j in range(10):
            q = (ten*j)%13
            for jj in range(13):
                dp[i+1][(jj+q)%13] = (dp[i][jj]+dp[i+1][(jj+q)%13])%mod
    else:
        q = (ten*int(s[i]))%13
        for jj in range(13):
            dp[i+1][(jj+q)%13] = (dp[i][jj]+dp[i+1][(jj+q)%13])%mod
    ten = (ten*10)%13
print(dp[-1][5])

Solution (Python):
s = str(input())
n = len(s)
MOD = 10**9 + 7

res_dic = {}
for i in range(13):
    if (i*10)%13 in res_dic:
        res_dic[(i*10)%13].append(i)
    else:
        res_dic[(i*10)%13] = [i]
        
caseq_list = [[0 for j in range(13)] for i in range(10)]
for num in range(10):
    for j in range(13):
        k = (j - num)%13
        if k in res_dic:
            for m in res_dic[k]:
                caseq_list[num][j] = m
        
dp = [[0 for j in range(13)] for i in range(n+1)]    
if s[0] == '?':
    for i in range(10):
        dp[1][i] =  1
else:
    num = ord(s[0]) - ord('0')
    dp[1][num] = 1

for i in range(1,n):
    c = s[i]
    if c == '?':
        for num in range(10):
            for j in range(13):
                dp[i+1][j] = (dp[i+1][j] + dp[i][caseq_list[num][j]]) % MOD
    else:
        num = ord(c) - ord('0')
        for j in range(13):
            dp[i+1][j] = (dp[i+1][j] + dp[i][caseq_list[num][j]]) % MOD
print(dp[n][5])

Solution (Python):
MOD = 1000000007

S = input()
N = len(S)

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

rem = [[0 for k in range(10)] for j in range(13)]

for j in range(13):
    for k in range(10):
        rem[j][k] = (10 * j + k) % 13

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

print(dp[N][5])

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

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

for i, s in enumerate(S):
    if s == "?":
        val = tuple(range(10))
    else:
        val = (int(s),)

    digit = pow(10, i, 13)
    for j in range(13):
        for k in val:
            ni = i + 1
            nj = (j + digit * k) % 13
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod

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

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

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

Solution (Python):
def STR(): return input()

mod = 1000000007

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


for i in range(l + 1): 
    if s[i-1] == '?':
        for j in range(13): 
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): 
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): 
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod

print(dp[l][5])

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

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

mul = 1
for n in range(N):
    s = S[-(n+1)] 
    if s == "?":
        for i in range(10):
            for mo in range(13):
                ind = (i * mul + mo) % 13
                dp[n+1][ind] += dp[n][mo]
                dp[n+1][ind] %= MOD
    else:
        i = int(S[-(n+1)])
        for mo in range(13):
            ind = (i * mul + mo) % 13
            dp[n+1][ind] += dp[n][mo]
            dp[n+1][ind] %= MOD
    mul *= 10
    mul %= 13

print(dp[N][5])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

S = inpS()
N = len(S)
dp = [0]*13

dp[0] = 1
mul = 1
for i in range(N-1, -1, -1):
  nextDP = [0]*13
  s = S[i]
  if s == "?":
    for dgt in range(10):
      for mo in range(13):
        ind = (dgt*mul+mo)%13
        nextDP[ind] += dp[mo]
        nextDP[ind] %= MOD        
  else:
    dgt = int(S[i])
    for mo in range(13):
      ind = (dgt*mul+mo)%13
      nextDP[ind] += dp[mo]
      nextDP[ind] %= MOD    
  mul *= 10
  mul %= 13
  dp = nextDP
print(dp[5])

Solution (Python):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()

Solution (Python):

s=input()
mod=10**9+7


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

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

Solution (Python):
from math import pow
S = input()
S = list(S)
S.reverse()
l = len(S)
dp =[ [0] * 13 for _ in range(l + 1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
keta = 1
for k,c in enumerate(S):
    if c == "?":
        for i in range(0,10): 
            for amari in range(0, 13):
                next_amari = (amari + i * keta ) % 13
                dp[k + 1][next_amari] += (dp[k][amari] )
                dp[k + 1][next_amari] %= MOD
    else:
        i = int(c)
        for amari in range(0,13):
            next_amari = (amari + i * keta ) % 13
            dp[k + 1][ next_amari] += (dp[k][amari])
            dp[k + 1][next_amari] %= MOD

    keta *= 10
    keta %= 13

print(dp[l][5])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()

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

dp[0][0] = 1

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

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

l = len(s)
s = [int(e) if e != "?" else -1 for e in s]
dp = [[0] * 13 for _ in range(l + 1)]
dp[0][0] = 1

for i in range(l):
	for k in range(10):
		if s[i] == -1 or s[i] == k:
			for j in range(13):
				nj = (j * 10 + k) % 13
				dp[i+1][nj] += dp[i][j]
				dp[i+1][nj] %= mod

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

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

    mod13=[1]*(10**5+1)
    for i in range(10**5):
        mod13[i+1]=mod13[i]*10%13
    
    s=list(input())[::-1]
    l=len(s)
    
    dp=[[0]*13 for _ in range(1+l)]

    if s[0]=='?':
        for num in range(10):
            t=num%13
            dp[1][t]+=1
    else:
        num=int(s[0])
        t=num%13
        dp[1][t]=1

    for i in range(1,l):
        if s[i]=='?':
            for j in range(13):
                for num in range(10):
                    t=(j+mod13[i]*num)%13
                    dp[i+1][t]+=dp[i][j]
                    dp[i+1][t]%=MOD
        
        else:
            num=int(s[i])
            for j in range(13):
                t=(j+mod13[i]*num)%13
                dp[i+1][t]+=dp[i][j]
                dp[i+1][t]%=MOD
    
    print(dp[-1][5])
 
if __name__=='__main__':
    main()

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

dp = [[0] * 13 for _ in range(len(s)+1)]
for i in range(10):
    if s[0] == "?":
        dp[1][i] += 1
    else:
        dp[1][int(s[0])] = 1
        break

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

print(dp[-1][5])

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

Solution (Python):

def main():
    S=input()
    
    dp=[[0]*13 for _ in range(len(S)+1)]
    dp[0][0]=1
    mod=10**9+7
    """
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                if a*10%13<(a*10+10)%13:
                    dp[i][a*10%13:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][a*10%13:(a*10+10)%13]%=mod
                else:
                    dp[i][a*10%13:]+=dp[i-1][a]
                    dp[i][a*10%13:]%=mod
                    dp[i][:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][:(a*10+10)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
"""
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                for n in range(10):
                    dp[i][(a*10+n)%13]+=dp[i-1][a]
                    dp[i][(a*10+n)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
if __name__=="__main__":
    main()

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

dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
cur = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                
                tmp = (k * cur) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = (x * cur) % 13
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
    cur = (cur * 10) % 13
print(dp[n][5])

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

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

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

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