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

Solution (Python):
def inpl(): return list(map(int, input().split()))

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

DP = [0]*13
DP[0] = 1
for i in range(len(S)):
    DP2 = [0]*13
    if S[i] != "?":
        s = int(S[i])
        for i in range(13):
            DP2[(i + s*x)%13] = DP[i]%MOD
    else:
        for j in range(10):
            for i in range(13):
                DP2[(i + j*x)%13] = (DP2[(i + j*x)%13] + DP[i])%MOD
    x = x*10%13
    DP = DP2

print(DP[5]%MOD)

Solution (Python):
m = int(1e9+7)
s = list(input())

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1
r = 1
ans = 0
for i in range(len(s)):
    for j in range(13):
        dp[(i + 1) % 2][j] = 0
    c = s[len(s) - 1 - i]
    if c == '?':
        for j in range(13):
            for k in range(10):
                dp[(i + 1) % 2][(k * r + j) % 13] += dp[i % 2][j]
    else:
        for j in range(13):
            dp[(i + 1) % 2][(int(c) * r + j) % 13] += dp[i % 2][j]
    for j in range(13):
        dp[(i + 1) % 2][j] %= m
    ans = dp[(i + 1) % 2][5]
    r *= 10
    r %= 13
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


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


def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return


def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return


def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    D()

Solution (Python):
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)

def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*pow(10,d,13)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*pow(10,d,13)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    

print(dp[5]%mo)

Solution (Python):
S = input()
dp = [[0]*13 for i 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,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

print(dp[-1][5])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

S=input()

digit_mod13 = 1
pats = [0]*13
buf = [0]*13

pats[0] = 1
N = len(S)
for i in range(N):
    if S[N-1-i] == '?':
        for k in range(10):
            zurasu = (k*digit_mod13) % 13
            
            for j in range(13):
                buf[(j+zurasu)%13] += pats[j]
        for j in range(13):
            pats[j] = buf[j] % DVSR
        
        for j in range(13):
            buf[j] = 0
    else:
        zurasu = (int(S[N-1-i])*digit_mod13) % 13
        for j in range(13):
            buf[(j+zurasu)%13] += pats[j]
        for j in range(13):
            pats[j] = buf[j]
        
        for j in range(13):
            buf[j] = 0

    digit_mod13 = (digit_mod13*10) % 13




print(pats[5])

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

dp = [1] + [0] * 12
new_dp = [0] * 13

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

mod = 10 ** 9 + 7

for idx, char in enumerate(s):
    new_dp = [0] * 13
    if char != "?":
        for i in range(13):
            new_i = (i + res[idx % 6][int(char)]) % 13
            new_dp[new_i] += dp[i]
        dp = new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i = (i + res[idx % 6][j]) % 13
                new_dp[new_i] += dp[i]
        dp = [x % mod for x in new_dp]

print(dp[5])

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

MOD = 10 ** 9 + 7

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

k = 1

dp[0][0] = 1

for i, x in enumerate(reversed(s)):
    
    if x == '?':
        temp = 0
        for _ in range(10):
            for j in range(13):
                m = (j+temp) % 13
                dp[i+1][m] = (dp[i+1][m] + dp[i][j]) % MOD
            temp = (temp + k) % 13
    else:
        y = int(x)
        temp = (y * k) % 13
        
        for j in range(13):
            m = (j + temp) % 13
            dp[i + 1][m] = (dp[i + 1][m] + dp[i][j]) % MOD
    k = (k * 10) % 13
    
    

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

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

S = input()
N = len(S)
amari = [0 for _ in range(13)]


for i, s in enumerate(S):
    if i == 0:
        next_amari = [0 for _ in range(13)]
        if s != "?":
            number = int(s)
            now_amari = number * pow(10, N-1-i, 13) % 13
            next_amari[now_amari] = 1
        else:
            for number in range(10):
                now_amari = number * pow(10, N-1-i, 13) % 13
                next_amari[now_amari] += 1
        amari = next_amari
        continue

    next_amari = [0 for _ in range(13)]
    if s != "?":
        number = int(s)
        now_amari = number * pow(10, N-1-i, 13) % 13
        for j, n in enumerate(amari):
            next_amari[(j+now_amari) % 13] = n
    else:
        for number in range(10):
            now_amari = number * pow(10, N-1-i, 13) % 13
            for j, n in enumerate(amari):
                next_amari[(j+now_amari) % 13] = (n+next_amari[(j+now_amari) % 13])%MOD

    amari = next_amari
print(amari[5])

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()

mods = [0] * 13
if S[-1] == '?':
    for i in range(10):
        mods[i] = 1
else:
    mods[int(S[-1])] = 1
base = 10

for i in range(1, len(S)):
    c = S[~i]
    if c == '?':
        aa = list(range(10))
    else:
        aa = [int(c)]
    nm = [0] * 13
    for a in aa:
        for i in range(13):
            nm[(base * a + i) % 13] += mods[i] % MOD
    mods = nm
    base *= 10
    base %= 13

print(mods[5] % MOD)

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

dp[0][0]=1
MOD=10**9+7
L=[]
for i in range(13):
    L.append((i*10)%13)
N=len(S)
for i in range(N):
    if S[i]!="?":
        j=ord(S[i])-ord('0')
        for k in range(13):
            dp[i+1][(L[k]+j)%13]+=dp[i][k]
            dp[i+1][(L[k]+j)%13]%=MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i+1][(L[k]+j)%13]+=dp[i][k]
                dp[i+1][(L[k]+j)%13]%=MOD
print(dp[N][5])

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

DP = [[0] * 13 for _ in range(len(S))]

if S[-1] == "?":
  for i in range(10):
    DP[0][i] = 1
else:
  t = int(S[-1])
  DP[0][t] = 1

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

print(DP[-1][5])

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

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    
    dp = [[0]*13 for _ in range(10**5+2)] 
    dp[0][0] = 1
    for i,s in enumerate(S):
        if s == "?":
            for hatena in range(10):
                for n in range(13):
                    amari = (10*n + hatena)%13
                    dp[i+1][amari] += dp[i][n]
                    dp[i+1][amari]%=mod
        else:
            for n in range(13):
                amari = (10 * n+int(s))%13

                dp[i+1][amari] += dp[i][n]
                dp[i+1][amari]%=mod
    print(dp[len(S)][5])
if __name__ == '__main__':
    main()

Solution (Python):
S = input()[::-1]
P = 10**9+7
c = 1
X = [1]+[0]*12
for s in S:
    Y = [0] * 13
    if s == "?":
        for i in range(10):
            for j in range(13):
                Y[(c*i+j)%13] += X[j]
                Y[(c*i+j)%13] %= P
    else:
        for j in range(13):
            Y[(c*int(s)+j)%13] = X[j]
            
    X = Y
    c = c*10%13

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

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

Solution (Python):
s=input()
n=len(s)
S=[]
mod = 10**9+7
M = [[0 for i in range(10)] for j in range(n)]

for i in range(10):
    M[0][i] = i
for i in range(1, n):
    for j in range(10):
        M[i][j] = (M[i-1][j] * 10) % 13



for i in range(n):
    if s[-i-1]=="?":
        S.append("?")
    else:
        S.append(int(s[-i-1]))



DP = [[0 for i in range(13)] for j in range(n)]

if S[0]=="?":
    for i in range(10):
        DP[0][i] += 1
else :
    DP[0][S[0]] += 1



for i in range(1, n):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                DP[i][(k+M[i][j])%13] += DP[i-1][k]%mod
    else:
        j=S[i]
        for k in range(13):
            DP[i][(k+M[i][j])%13] += DP[i-1][k]%mod

    

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

Solution (Python):
S = list(input())
S = [int(s) if s != "?" else -1 for s in S]
mod = [1]
for i in range(10**5 + 1):
	mod.append((mod[i] * 10) % 13)
MOD = 10**9 + 7
N = len(S)
dp = [[0 for j in range(13)] for i in range(N)]
for i in range(N):
	d = S[N-1 - i]
	for x in range(10):
		if d == x or d == -1:
			plus = (mod[i] * x) % 13
			if i == 0:
				dp[i][x] = 1
			else:
				for j in range(13):
					J = (j+plus) % 13
					dp[i][J] = (dp[i][J] + dp[i-1][j]) % MOD
print(dp[N-1][5])

Solution (Python):
S=input()
N=len(S)
X=[1,10,9,12,3,4]
Y=[0,0,0,0,0,0]
nowmod=0
modprime=10**9+7
for i in range(N):
    if S[-i-1]=="?":
        Y[i%6]+=1
    else:
        nowmod+=X[i%6]*int(S[-i-1])
        nowmod%=13


M=max(Y)
dp=[[0 for j in range(13)]for i in range(M+1)]

dp[0][0]=1
for i in range(M):
    for k in range(10):
        for j in range(13):
            dp[i+1][(k+j)%13]+=dp[i][j]
            dp[i+1][(k+j)%13]%=modprime
table=[[dp[Y[i]][j] for j in range(13)]for i in range(6)]
ans=[[0 for j in range(13)] for i in range(7)]
ans[0][0]=1
for i in range(6):
    for j in range(13):
        for k in range(13):
            ans[i+1][(j+(X[i]*k))%13]+=ans[i][j]*table[i][k]
            ans[i+1][(j+(X[i]*k))%13]%=modprime
print(ans[6][(5-nowmod)%13])

Solution (Python):

import sys

MOD = 1000000007  

def solve(S: str):
    N = len(S)
    r_d = [1] * (N+1)
    r_d[0] = 0
    for i in range(2, N+1):
        r_d[i] = (r_d[i-1] * 10) % 13
    
    dp = [[0 for j in range(N+1)] for i in range(13)] 
    dp[0][0] = 1

    for j in range(1, N+1):
        d = S[-j]
        if d != "?":
            d = (int(d) * r_d[j]) % 13
            for i in range(13):
                dp[i][j] += dp[(i - d) % 13][j-1]
            continue
        for k in range(10):
            d = (k * r_d[j]) % 13
            for i in range(13):
                dp[i][j] += dp[(i - d) % 13][j-1]
                dp[i][j] %= MOD
    print(dp[5][N])
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
def NextAmari(prev,d):
    return((prev*10+d)%13)

S = input()
mod = 10**9 + 7
DP = [[0]*13 for i in range(len(S)+1)]

DP[0][0] = 1
for n,s in enumerate(S):
    i = n
    if s != "?":
        d = int(s)
        for j,num in enumerate(DP[i]):
            DP[i+1][NextAmari(j,d)] += num
    else:
        for d in range(10):
            for j,num in enumerate(DP[i]):
                DP[i+1][NextAmari(j,d)] += num
    for a in range(13):
        DP[i+1][a] %= mod
print(DP[-1][5])

Solution (Python):
s = input()
n = len(s)
s = s[::-1]
MOD = 10**9 + 7

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

for i in range(n):
    if s[i] == "?":
        tmp = keta[i]
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j*tmp + k) % 13] += dp[i][k]
                dp[i + 1][(j*tmp + k) % 13] %= MOD
    else:
        num = int(s[i])
        tmp = keta[i]
        for k in range(13):
            dp[i + 1][(num*tmp + k) % 13] += dp[i][k]
            dp[i + 1][(num*tmp + k) % 13] %= MOD        
print(dp[n][5])

Solution (Python):
S = input()
N = len(S)
su = 0
L = [0]*13
L[0] = 1
M = [1, 10, 9, 12, 3, 4]
mod = 10**9+7
for i, c in enumerate(S[::-1]):
    m = M[i % 6]
    if c=="?":
        Lc = L[:]
        for j in range(m, m*10, m):
            for k in range(13):
                idx = (k+j)%13
                L[idx] = (L[idx] + Lc[k]) % mod
    else:
        su += int(c) * m
print(L[(-su+5)%13])

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

print(dp[N][5])

Solution (Python):
S = input()

S = S[::-1]

mod_list = [pow(10,i,13) for i in range(12)]
mod = 10**9 + 7
DP = [[0]*13 for i in range(len(S)+1)]
DP[0][0] = 1

for i in range(len(S)):
    if S[i]=='?':
        for j in range(10):
            for k in range(13):
                DP[i+1][(k+j*mod_list[i%12])%13] = (DP[i+1][(k+j*mod_list[i%12])%13] + DP[i][k])%mod
    else:
        s=int(S[i])
        for k in range(13):
            DP[i+1][(k+s*mod_list[i%12])%13] =(DP[i+1][(k+s*mod_list[i%12])%13] + DP[i][k])%mod

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

Solution (Python):
s = input()[::-1]
MOD = 10**9 + 7
n = len(s)

data = [0 for i in range(n+2)] 
data[0] = 1
for i in range(1,n+2):
    data[i] = (data[i-1]*10)%13


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

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


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

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

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

s = input()
l = len(s)
MOD = 10**9+7

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


print(dp[5]%MOD)

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

dp = [[0 for i in range(13)] for j in range(2)]
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 j in range(13):
        dp[i%2][j] = 0

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

    
    
    


print(dp[(len(s)-1)%2][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 i in range(n):
    c = s[i]
    if c == '?':
        V = [0,1,2,3,4,5,6,7,8,9]
    else:
        V = [int(c)]
    for v in V:
        d = v*pow(10, n-i-1, 13)%13
        for j in range(13):
            dp[i+1][(j+d)%13] += dp[i][j]

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

print(dp[n][5])

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

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

Ss = input()

N = len(Ss)

dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
for d, Sd in enumerate(Ss):

    for mod13 in range(13):
        if Sd != '?':
            x = int(Sd)
            mod13n = (10*mod13 + x) % 13
            dp[d+1][mod13n] += dp[d][mod13]
            dp[d+1][mod13n] %= MOD
        else:
            for x in range(10):
                mod13n = (10*mod13 + x) % 13
                dp[d+1][mod13n] += dp[d][mod13]
                dp[d+1][mod13n] %= MOD

print(dp[-1][5])

Solution (Python):
def find(S):
    MOD=10**9+7
    S=S[::-1]
    dp=[[0]*13 for i in range(len(S))]
    power=1
    if S[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        dp[0][int(S[0])]=1
    
    for i in range(1,len(S)):
        power*=10
        power%=13
        if S[i]=="?":
            for j in range(13):
                for k in range(10):
                    dp[i][j]+=dp[i-1][(j-power*k)%13]
                    dp[i][j]%=MOD
        else:
            for j in range(13):
                k=int(S[i])
                dp[i][j]+=dp[i-1][(j-power*k)%13]
                dp[i][j]%=MOD              
    return dp[-1][5]

S=input()
print(find(S))

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



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

Solution (Python):
s = input()
MOD = 10**9 + 7
memo = [0]*13
memo[0] = 1

c = 1
for d in reversed(s):
    if d == '?':
        nmemo = [0]*13
        for i in range(10):
            r = (i*c)%13
            for j in range(13):
                nmemo[(j+r)%13] += memo[j]
        for i in range(13):
            nmemo[i] %= MOD
        memo = nmemo
    else:
        d = (-int(d)*c)%13
        memo = memo[d:] + memo[:d]

    c *= 10
    c %= 13
print(memo[5])

Solution (Python):

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def solve(S: str):
    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):
                    nex = (j * 10 + k) % 13
                    dp[i + 1][nex] += dp[i][j]
                    dp[i + 1][nex] %= MOD
            else:
                k = int(S[i])
                nex = (j * 10 + k) % 13
                dp[i + 1][nex] += dp[i][j]
                dp[i + 1][nex] %= MOD
    ret = dp[N][5]
    print(ret)
    return


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

if __name__ == '__main__':
    main()

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

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

Solution (Python):
X = input()
MOD = 10**9 + 7
M = 13
S = [0]*M
S[0] = 1
T = [0]*M

def calc(S, T, x):
    for i in range(M):
        T[(i*10 + x) % M] += S[i]
    for i in range(M):
        T[i] %= MOD

zeros = [0]*M
for c in X:
    T[:] = zeros
    if c == "?":
        for x in range(10):
            calc(S, T, x)
    else:
        x = int(c)
        calc(S, T, x)
    S, T = T, S
print(S[5])