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):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    MOD = 10 ** 9 + 7
    S = rl().rstrip()
    
    N = len(S)
    dp = [[0 for _ in range(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:
            num = int(S[i])
            for j in range(13):
                dp[i + 1][(j * 10 + num) % 13] += dp[i][j] % MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    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] != '?':
                dp[i+1][(10 * j + int(S[i])) % 13] += dp[i][j] % MOD
            else:
                for k in range(0,10):
                    dp[i+1][(10 * j + k) % 13] += dp[i][j] % MOD
    
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

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

if __name__ == "__main__":
    main()

Solution (Python):
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

DP = [[0]*13 for i in range(N)]
K = 1
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            if i==0:
                DP[0][(j*K)%13] = 1
            else:
                for k in range(13):
                    DP[i][(j*K+k)%13] += DP[i-1][k]
    else:
        j = int(S[i])*K
        if i==0:
            DP[0][(j*K)%13] = 1
        else:
            for k in range(13):
                DP[i][(j+k)%13] += DP[i-1][k]
    K = (K*10)%13
    for j in range(13):
        DP[i][j] = DP[i][j]%MOD
print(DP[N-1][5]%MOD)

Solution (Python):
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    S = readline().rstrip()
    N = 13
    dp = [0] * 13  
    dp[0] = 1
    
    mul = 1
    for s in S[::-1]:
        next_dp = [0] * N
        if s == '?':
            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)
            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])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict as dd
s = input()

dp = dd(lambda: dd(lambda: 0))
nums = list(range(0, 10))

for keta in range(1, len(s)+1):
    digit = s[keta-1]
    if digit != "?":
        digit = int(digit)
        if keta == 1:
            dp[keta][digit] = 1
        else:
            for amari, val in dp[keta-1].items():
                dp[keta][(amari * 10 + digit) % 13] += val
                dp[keta][(amari * 10 + digit) % 13] %= 10**9 + 7

    else:
        if keta == 1:
            for digit in nums:
                dp[keta][digit] = 1
        else:
            for digit in nums:
                for amari, val in dp[keta-1].items():
                    dp[keta][(amari * 10 + digit) % 13] += val
                    dp[keta][(amari * 10 + digit) % 13] %= 10**9 + 7

print(dp[len(s)][5] % (10**9 + 7))

Solution (Python):
S = input()
N = len(S)
mod = 10**9+7
P = 13
 
dp = [[0 for _ in range(P)] for _ in range(N+1)]
dp[0][0] = 1
 
for i in range(N):
    x = S[-1-i]
    if x == '?':
        base = pow(10, i, P)
        for j in range(10):
            r = base*j % P
            for m in range(P):
                dp[i+1][(m+r)%P] = (dp[i+1][(m+r)%P] + dp[i][m]) % mod
    else:
        r = pow(10, i, P) * int(x) % P
        for j in range(P):
            dp[i+1][(j+r)%P] = max(dp[i+1][(j+r)%P], dp[i][j])
 
print(dp[-1][5])

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

if S[N-1] == '?':
    tmp = [0 for _ in range(P)]
    for i in range(10):
        tmp[i % P] = 1
    dp[0] = tmp
else:
    dp[0][int(S[N-1]) % P] = 1
 
for i in range(1, N):
    k = N-i-1
    if S[k] == '?':
        base = pow(10, i, P)
        for j in range(10):
            r = base*j % P
            for m in range(P):
                dp[i][(m+r)%P] = (dp[i][(m+r)%P] + dp[i-1][m]) % mod
    else:
        r = pow(10, i, P) * int(S[k]) % P
        for j in range(P):
            dp[i][(j+r)%P] = max(dp[i][(j+r)%P], dp[i-1][j])
 
print(dp[-1][5])

Solution (Python):
m = [[0, 4, 8, 12, 3, 7, 11, 2, 6, 10],[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],[0, 10, 7, 4, 1, 11, 8, 5, 2, 12],[0, 9, 5, 1, 10, 6, 2, 11, 7, 3],[0, 12, 11, 10, 9, 8, 7, 6, 5, 4],[0, 3, 6, 9, 12, 2, 5, 8, 11, 1]]
S = list(input())
d = len(S)
dp = [[0] * 13 for _ in range(d)]
if S[0] == '?':
    for x in m[d%6]:
        dp[0][x] = 1
else:
    dp[0][m[d%6][int(S[0])]] = 1
for i in range(1,d):
    if S[i] == '?':
        for j in range(13):
            dp[i][j] = sum(dp[i-1][(13+j-x) % 13] for x in m[(d-i)%6]) % 1000000007
    else:
        for j in range(13):
            dp[i][j] = dp[i-1][(13+j-m[(d-i)%6][int(S[i])])%13]
print(dp[d-1][5])

Solution (Python):




S = input()
N = len(S)
MOD = 10**9 + 7
"""
dp[i+1][j] : Sのi文字目まで見たときに、13で割って余りがjになるものの個数

遷移
i-1まで見たときの余りがjの個数がdp[i][j]
iまで見るとi-1までの部分を13でわった余りも10倍されるから、10*j
数字の後ろにS[i]が追加されるので 10*j + S[i]になり、これを13で割った余ると
S[i][j] -> S[i+1][(10*j + S[i]) % 13] みたいな遷移になる

"""
dp = [[0 for _ in range(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]
                dp[i+1][(10*j + k) % 13] %= MOD

        else:
            dp[i+1][(10*j + int(S[i])) % 13] += dp[i][j]
            dp[i+1][(10*j + int(S[i])) % 13] %= MOD



print(dp[-1][5])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()[::-1]
n = len(s)
now = [0] * 13
now[0] = 1
for i,x in enumerate(s):
    new = [0] * 13
    c = pow(10,i,13)
    if x == '?':
        for k in range(10):
            for j in range(13):
                new[(j+c*k)%13] += now[j]
                new[(j+c*k)%13] %= mod
    else:
        for j in range(13):
            new[(j+c*int(x))%13] += now[j]
            new[(j+c*int(x))%13] %= mod
    now = new[::]
print(now[5])

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

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

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

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

Solution (Python):
S = input()
 
INF = 10 ** 9 + 7
 
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):
m=10**9+7
s=list(input())
n=len(s)
s.reverse()
dp=[[0]*13 for _ in range(n)]
if s[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(s[0])]=1
x=1
for i in range(1,n):
    x=(x*10)%13
    for j in range(13):
        if s[i]=="?":
            if dp[i-1][j]!=0:
                for k in range(10):
                    dp[i][(j+k*x)%13]+=dp[i-1][j]
                    dp[i][j]%=m
        else:
            if dp[i-1][j]!=0:
                dp[i][(j+int(s[i])*x)%13]+=dp[i-1][j]
                dp[i][j]%=m
print(dp[n-1][5]%m)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from copy import copy 
def main():
    S = readline().decode().rstrip()    
    P = int(1e9)+7
    dp = [0 for _ in range(13)]
    dp[0] = 1
    mul = 1
    for s in reversed(S):
        nxDP = [0 for _ in range(13)]
        if s == '?':
            for i in range(10):
                for j in range(13):
                    nxr = (i*mul+j)%13
                    nxDP[nxr] += dp[j]
                    nxDP[nxr] %= P
        else:
            for j in range(13):
                nxr = ((ord(s)-ord('0'))*mul+j)%13
                nxDP[nxr] += dp[j]
                nxDP[nxr] %= P
        dp = copy(nxDP)
        mul *= 10
        mul %= 13

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

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

    s = input()
    r = [0] * 13
    r[0] = 1
    p = 1
    for c in reversed(s):
        if c == '?':
            tank = []
            for x in range(10):
                x = x * p % 13
                tank.append(r[13 - x:] + r[:13 - x])
            r = map(sum, zip(*tank))
            *r, = map(lambda x: x % MOD, r)


        else:
            x = int(c)
            x = x * p % 13
            r = r[13 - x:] + r[:13 - x]
        p = p * 10 % 13

    print(r[5])


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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


def resolve():
    s = input()
    L = len(s)
    dp = [[0] * 13 for _ in range(L + 1)]
    dp[0][0] = 1

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

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


if __name__ == '__main__':
    resolve()

Solution (Python):
p = 10**9+7
S = input().strip()
A = [[0 for k in range(13)] for j in range(13)]
for j in range(13):
    for k in range(13):
        for m in range(10):
            if (10*k+m)%13==j:
                A[j][k] = 1
                break
B = [[0 for _ in range(10)] for _ in range(13)]
for j in range(13):
    for m in range(10):
        for k in range(13):
            if (10*k+m)%13==j:
                B[j][m] = k
                break
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N+1)]
for j in range(13):
    if S[0]!="?":
        dp[1][j] = int(int(S[0])==j)
    else:
        if j<10:
            dp[1][j] = 1
for i in range(2,N+1):
    for j in range(13):
        if S[i-1]!="?":
            dp[i][j] = (dp[i][j]+dp[i-1][B[j][int(S[i-1])]])%p
        else:
            for k in range(13):
                dp[i][j] = (dp[i][j]+dp[i-1][k]*A[j][k])%p
print(dp[N][5])

Solution (Python):
S = input()
N = len(S)
dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for n in range(N):
    s = S[n]
    if s!='?':
        s = int(s)*pow(10, (N-n-1), 13)%13
        for i in range(13):
            idx = (s+i)%13
            dp[n+1][idx] = dp[n][i]%mod
    else:
        for i in range(10):
            s = i*pow(10, (N-n-1), 13)%13
            for j in range(13):
                idx = (s+j)%13
                dp[n+1][idx] += dp[n][j]%mod

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

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  




'''
dp[i][j] ... [0,i)桁の数字で、余りがjに成る通りの総数
更新則
?じゃないとき
dp[i+1][(j+S[i]*pow(10,i,13))%13] = dp[i][j]
?のとき
dp[i+1][j] += dp[i][k] 
'''
mod = 13
S = list(reversed(read()[:-1]))

dp = [[0] * mod for _ in range(len(S) + 1)]
dp[0][0] = 1
pow10imod = 1
for i in range(len(S)):
    for j in range(mod):
        if S[i] != '?':
            dp[i + 1][(j + int(S[i]) * pow10imod) % mod] += \
                dp[i][j] % MOD
            
            
        else:
            for k in range(10):
                dp[i + 1][(j + k * pow10imod) % mod] += \
                    dp[i][j] % MOD
                
                
    pow10imod = pow10imod * 10 % mod

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7


s=input().rstrip()
n=len(s)
beki=[0 for i in range(n+1)]
beki[0]=1
for i in range(n):
    beki[i+1]=(beki[i]*10)%13

u=[[0 for i in range(13)] for j in range(n+1)]
u[0][0]=1
s=list(reversed(s))
for i in range(n):
    
    for j in range(13):
        if s[i]!="?":
            u[i+1][(j+beki[i]*int(s[i]))%13]+=u[i][j]%mod
        else:
            for k in range(10):
                u[i+1][(j+beki[i]*k)%13]+=u[i][j]%mod

print(u[n][5]%mod)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = read().rstrip().decode()
dp = [[0] * 13 for _ in range(len(s))]
mod = 10 ** 9 + 7
if s[0] == '?':
    dp[0] = 10 * [1] + [0] * 3
else:
    dp[0][int(s[0])] += 1
for i, ss in enumerate(s[1:]):
    if ss == '?':
        for j in range(13):
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    else:
        for j in range(13):
            dp[i + 1][(int(ss) + j * 10) % 13] += dp[i][j]
    for j in range(13):
        dp[i + 1][j] %= mod
print(dp[-1][5])

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

DP=[[0]*C for _ in range(N+1)]
DP[0][0]=1

for i,s in enumerate(S,1):
    if s=="?":
        for k in range(C):
            for j in range(10):
                new_mod=k*10+j
                DP[i][new_mod%13]+=DP[i-1][k]
    else:
        for k in range(C):
            new_mod=k*10+int(s)
            DP[i][new_mod%13]+=DP[i-1][k]
    for k in range(C):
        DP[i][k]%=MOD

print(DP[-1][5])

Solution (Python):
def main():
    S = input()
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]

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


main()

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


def main():
    S = input()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    from itertools import product
    for i, mod13 in product(range(N), range(13)):
        if S[i] == "?":
            lim = 9
            for d in range(lim+1):
                dp[i+1][(mod13*10 + d) % 13] \
                    += dp[i][mod13]
                dp[i+1][(mod13*10 + d) % 13] \
                    %= MOD
        else:
            d = int(S[i])
            dp[i+1][(mod13*10 + d) % 13] \
                += dp[i][mod13]
            dp[i+1][(mod13*10 + d) % 13] \
                %= MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()

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

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

for s in S:
    newDp = [0] * M
    if s == '?':
        for s in range(10):
            for m in range(M):
                newDp[(m * 10 + s) % M] += dp[m]
    else:
        s = int(s)
        for m in range(M):
            newDp[(m * 10 + s) % M] += dp[m]
    dp = newDp
    for m in range(M):
        dp[m] %= MOD

print(newDp[5] % MOD)

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

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

for s in S:
    newDp = [0] * M
    if s == '?':
        for m in range(M):
            for s in range(10):
                newDp[(m * 10 + s) % M] += dp[m]
    else:
        s = int(s)
        for m in range(M):
            newDp[(m * 10 + s) % M] += dp[m]
    dp = newDp
    for m in range(M):
        dp[m] %= MOD

print(newDp[5] % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
S = list(input())[: -1]
mod = 10 ** 9 + 7
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] != "?":
      x = int(S[i])
      dp[i + 1][(j * 10 + x) % 13] += dp[i][j]
      dp[i + 1][(j * 10 + x) % 13] %= mod
    else:
      for x in range(10):
        dp[i + 1][(j * 10 + x) % 13] += dp[i][j]
        dp[i + 1][(j * 10 + x) % 13] %= mod
print(dp[-1][5])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from copy import copy 
def main():
    S = readline().decode().rstrip()
    P = int(1e9)+7
    DP = [0 for _ in range(13)]
    DP[0] = 1
    mul = 0
    for k in reversed(S):
        nxDP = [0 for _ in range(13)]
        if k == '?':
            for j in range(10):
                r = (j*pow(10, mul, 13))%13
                for i in range(13):
                    nxDP[(r+i)%13] += DP[i] 
                    nxDP[(r+i)%13] %= P  
        else:
            r = ((ord(k)-ord('0'))*pow(10, mul, 13))%13
            for i in range(13):
                nxDP[(r+i)%13] += DP[i] 
                nxDP[(r+i)%13] %= P
        mul += 1
        DP = copy(nxDP)
    print(DP[5])
if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	S = inputStr()
	S_len = len(S)

	DP = [[0 for j in range(13)] for i in range(S_len)]
	S = S[::-1]

	mut = 10
	for i,val in enumerate(S):
		if i == 0:
			if val == "?":
				for j in range(0,10):
					DP[i][j] += 1
			else:
				DP[i][int(val)] += 1
		else:
			if val == "?":
				for j in range(0,10):
					tmp = (mut * j) % 13
					for v,vol in enumerate(DP[i-1]):
						if vol == 0:
							continue
						tmptmp = (v + tmp) % 13
						DP[i][tmptmp] = (DP[i][tmptmp] + vol) % mod
			else:
				tmp = (mut * int(val)) % 13
				for j,vol in enumerate(DP[i-1]):
					if vol == 0:
						continue
					tmptmp = (j + tmp) % 13
					DP[i][tmptmp] = (DP[i][tmptmp] + vol) % mod
			mut = (mut * 10) % 13

	
	print(DP[S_len-1][5] % mod)




def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

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

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

def POWt(N):
    arr=[1]
    for i in range(1,N+1):
        arr.append(arr[-1]*10%13)
    return arr

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

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

Solution (Python):
MOD = 10 ** 9 + 7
S = input()
N = len(S)
mod13 = [0] * 13
mod13[0] = 1
exponent = 1
for i in range(1, N + 1):
    mod13_new = [0] * 13
    c = S[-i]
    if c == "?":
        for n in range(10):
            m = n * exponent % 13
            for r in range(13):
                mod13_new[(r + m) % 13] += mod13[r]
    else:
        for r in range(13):
            mod13_new[(r + int(c) * exponent) % 13] = mod13[r]
    exponent = exponent * 10 % 13
    for r in range(13):
        mod13_new[r] %= MOD
    mod13 = mod13_new
print(mod13[5])

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    S = input()
    N = len(S)
    mod13 = [0] * 13
    mod13[0] = 1
    exponent = 1
    for i in range(1, N + 1):
        mod13_new = [0] * 13
        c = S[-i]
        if c == "?":
            for n in range(10):
                m = n * exponent % 13
                for r in range(13):
                    mod13_new[(r + m) % 13] += mod13[r]
        else:
            for r in range(13):
                mod13_new[(r + int(c) * exponent) % 13] = mod13[r]
        exponent = exponent * 10 % 13
        for r in range(13):
            mod13_new[r] %= MOD
        mod13 = mod13_new
    print(mod13[5])

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    S = input()
    N = len(S)
    mod13 = [[0] * 13 for _ in range(N + 1)]
    mod13[0][0] = 1
    exponent = 1
    for i in range(1, N + 1):
        c = S[-i]
        if c == "?":
            for n in range(10):
                m = n * exponent % 13
                for r in range(13):
                    mod13[i][(r + m) % 13] += mod13[i - 1][r]
        else:
            m = int(c) * exponent % 13
            for r in range(13):
                mod13[i][(r + m) % 13] = mod13[i - 1][r]
        exponent = exponent * 10 % 13
        for r in range(13):
            mod13[i][r] %= MOD
    print(mod13[N][5])

if __name__ == "__main__":
    main()

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

for i in range(n):
    for j in range(10):
        if s[i] != "?" and int(s[i]) != j: continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod
        

print(dp[n][5])

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

def main():
    S = input()
    N = len(S)
    MOD = 10**9+7

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

    s = S[0]
    if s == -1:
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][s%13] += 1
    for i in range(1,N):
        s = S[i]
        X = [s]
        if s == -1:
            X = range(10)

        for j in range(0,13):
            ten_j = j*10
            for x in X:
                k = (ten_j+x)%13
                dp[i][k] += dp[i-1][j]
                dp[i][k] %= MOD

    
    print(dp[N-1][5])



if __name__ == "__main__":
  main()

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

def main():
    S = input()
    N = len(S)
    MOD = 10**9+7

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

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


    print(dp[N-1][5])


if __name__ == "__main__":
  main()

Solution (Python):

import sys



MOD = 1000000007  



def solve(S: str):
    S = S[::-1]
    dp = [[0] * 13 for _ in range(len(S))]
    

    s = S[0]
    if s == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s)] = 1
    for l in range(1, len(S)):
        s = S[l]
        pow_l = pow(10, l, 13)
        if s == "?":
            for m in range(13):
                for i in range(10):
                    dp[l][(m + pow_l * i) % 13] += dp[l-1][m]% MOD
        else:
            i = int(s)
            for m in range(13):
                dp[l][(m + pow_l * i) % 13] += dp[l-1][m] % MOD

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

    return



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

if __name__ == '__main__':
    main()