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 = list(input())
dp = [[0]*13 for _ in range(100005)]
n = len(s)
res = 0
mod = 10**9+7
dp[0][0] = 1
for i in range(n):
    c = int(s[i]) if s[i] !='?' else -1
    for j in range(10):
        if c!=-1 and c!=j: continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[n][5])

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        base = pow(10, l - i - 1, 13)

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

    print(dp[l][5])


if __name__ == '__main__':
    main()

Solution (Python):
from copy import copy

MOD = 10**9 + 7
s = input()
count = [0 for _ in range(13)]
count[0] = 1
for i in range(len(s)):
    new = [0 for _ in range(13)]
    for m in range(13):
        new[(m * 10) % 13] = count[m]
    count = new
    if s[i] != "?":
        div = int(s[i])
        count = count[-div:] +  count[:-div]
    else:
        new = [0 for _ in range(13)]
        pre = sum(count[:3])
        SUM = sum(count) % MOD
        for j in range(13):
            pre += count[(j+3) % 13]
            pre -= count[j % 13]
            new[j] = (SUM - pre) % MOD
        count = new
print(count[5])

Solution (Python):
from copy import copy

MOD = 10**9 + 7
s = input()
count = [0 for _ in range(13)]
count[0] = 1
for i in range(len(s)):
    new = [0 for _ in range(13)]
    for m in range(13):
        new[(m * 10) % 13] = count[m]
    count = new
    if s[i] != "?":
        div = int(s[i])
        count = count[-div:] +  count[:-div]
    else:
        new = [0 for _ in range(13)]
        pre = sum(count[:3])
        SUM = sum(count) % MOD
        for j in range(13):
            pre += count[(j+3) % 13]
            pre -= count[j % 13]
            new[j] = (SUM - pre) % MOD
        count = new
print(count[5])

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

S=list(input().rstrip('\n'))

kake10 = [0,10,7,4,1,11,8,5,2,12,9,6,3]
now = {0:1,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
for i in S:
  now = {kake10[x]:now[x] for x in range(13)}
  if i=='?':
    now2 = {x:sum(now[(x+y)%13] for y in range(4,14))%1000000007 for x in range(13)}
    now = now2
  else:
    a = int(i)
    now = {(x+a)%13:now[x] for x in range(13)}
print(now[5])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





S = input()
N = len(S)

dp = [[0] * 13 for i in range(N)]
str_int = '0123456789'
if S[0] in str_int:
    dp[0][int(S[0])] += 1
else:
    for i in range(10):
        dp[0][i] += 1

for i in range(1, N):
    if S[i] in str_int:
        
        for j in range(13):
            dp[i][(10 * j + int(S[i])) % 13] += (dp[i - 1][j] % mod)
    else:
        
        for j in range(13):
            
            
            for l in range(10):
                dp[i][(10 * j + l) % 13] += (dp[i - 1][j] % mod)

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

Solution (Python):
m=10**9+7
s=input()
d=[1]+[0]*12
for i in range(len(s)):
 if s[i]== "?":d=[sum(d[(j-k)*4%13]for k in range(10))%m for j in range(13)]
 else:d=[d[(j-int(s[i]))*4%13]%m for j in range(13)]
print(d[5])

Solution (Python):


S = input()

MOD = 10 ** 9 + 7

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

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

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

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    s = S()

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

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
def readinput():
    s=input()
    return s

def printTbl(tbl):
    for l in tbl:
        print(l)

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

    Rtbl=[]
    for _ in range(10):
        Rtbl.append([0]*13)
    for i in range(1,10):
        for j in range(13):
            Rtbl[i][j]=(Rtbl[i-1][j]+j)%13
    

    n=len(s)
    p0=0
    q=[]
    for i in range(n):
        if s[i]!='?':
            p0=(p0*10+int(s[i]))%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
        else:
            p0=(p0*10)%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
            q.append(1)
    

    nq=len(q)
    if nq==0:
        if p0==5:
            return 1
        else:
            return 0

    Ptbl=[]
    for _ in range(13):
        Ptbl.append([0]*nq)
    q0=q[0]
    for i in range(10):
        Ptbl[(Rtbl[i][q0]+p0)%13][0]+=1
    for j in range(1,nq):
        qj=q[j]
        for n in range(10):
            for i in range(13):
                if Ptbl[i][j-1]>0:
                    ii=(i+Rtbl[n][qj])%13
                    Ptbl[ii][j]=(Ptbl[ii][j]+Ptbl[i][j-1])%MOD
    
    return Ptbl[5][nq-1]

def main2(s):
    MOD=10**9+7
    dp=[]
    n=len(s)
    for _ in range(13):
        dp.append([0]*(n+1))
    dp[0][0]=1
    for i in range(n):
        c=s[i]
        for j in range(13):
            for k in range(10):
                if c!='?' and c!=str(k):
                   continue
                jj=(j*10+k)%13
                dp[jj][i+1]=(dp[jj][i+1]+dp[j][i])%MOD
    return dp[5][n]

if __name__=='__main__':
    s=readinput()
    ans=main2(s)
    print(ans)

Solution (Python):
import sys
import math
import bisect
import heapq
from collections import Counter


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


def main():
    mod = 10 ** 9 + 7
    S = list(input())
    l = len(S)
    dp = [[0] * 13 for _ in range(l + 1)]

    dp[0][0] = 1
    for j in range(1, l + 1):
        jp = j - 1
        if S[jp] == "?":
            for k in range(13):
                kk = k * 10
                for q in range(10):
                    new_k = (kk + q) % 13
                    dp[j][new_k] += dp[jp][k]
            for k in range(13):
                dp[j][k] %= mod
        else:
            n = int(S[jp])
            for k in range(13):
                new_k = (k * 10 + n) % 13
                dp[j][new_k] += dp[jp][k]
                dp[j][new_k] %= mod
    print(dp[l][5])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import bisect
import heapq
from collections import Counter


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


def main():
    mod = 10 ** 9 + 7
    S = list(input())
    l = len(S)
    dp = [[0] * 13 for _ in range(l + 1)]

    dp[0][0] = 1
    for j in range(1, l + 1):
        if S[j - 1] == "?":
            for k in range(13):
                for q in range(10):
                    new_k = (k * 10 + q) %13
                    dp[j][new_k] += dp[j - 1][k]
            for k in range(13):
                dp[j][k] %= mod
        else:
            n = int(S[j - 1])
            for k in range(13):
                new_k = (k * 10 + n)%13
                dp[j][new_k] += dp[j - 1][k]
                dp[j][new_k] %= mod
    print(dp[l][5])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import bisect
import heapq
from collections import Counter


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


def main():
    mod = 10 ** 9 + 7
    S = list(input())
    l = len(S)
    dp = [[0] * 13 for _ in range(l + 1)]

    dp[0][0] = 1
    for j in range(1, l + 1):
        if S[j - 1] == "?":
            for k in range(13):
                for q in range(10):
                    new_k = (k * 10 + q) %13
                    dp[j][new_k] += dp[j - 1][k]
                    dp[j][new_k] %= mod
        else:
            n = int(S[j - 1])
            for k in range(13):
                new_k = (k * 10 + n)%13
                dp[j][new_k] += dp[j - 1][k]
                dp[j][new_k] %= mod
    print(dp[l][5])

if __name__ == "__main__":
    main()

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

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, 13)) % 13
            for k in range(13):  
                Y = dp[i-1][k]
                Z = (X + k) % 13  
                dp[i][Z] += Y % p

    else:
        X = int(X)
        X = (X * pow(10, i-1, 13)) % 13
        for k in range(13):  
            Y = dp[i-1][k]
            Z = (X + k) % 13  
            dp[i][Z] += Y % p

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

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

for i in range(1,N+1):
    X = S[N-i]
    if X=="?":
        for X in range(10):
            Y = (X*pow(10,i-1,13))%13
            for j in range(13):
                if 0<=Y+j<=12:
                    Z = Y+j
                else:
                    Z = Y+j-13
                dp[i][Z] = (dp[i][Z]+dp[i-1][j])%p
    else:
        X = int(X)
        Y = (X*pow(10,i-1,13))%13
        for j in range(13):
            if 0<=Y+j<13:
                Z = Y+j
            else:
                Z = Y+j-13
            dp[i][Z] = dp[i-1][j]

print(dp[-1][5])

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

t = [[0 for j in range(13)] for i in range(n)]
for i,x in enumerate(s):
    A = pow(10, i ,13)
    if i == 0:
        if x == "?":
            for j in range(0,10):
                t[i][j] += 1
        else:
            t[i][int(x)] += 1
    else:
        if x == "?":
            for k in range(13):
                for j in range(10):
                    b = (k + j*A)%13
                    t[i][b] += t[i-1][k]
                    t[i][b] %= mod
        else:
            for k in range(0,13):
                b = (k + int(x)*A)%13
                t[i][b] += t[i-1][k]
                t[i][b] %= mod
print(t[-1][5]%mod)

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):
from collections import defaultdict

S = input()
N = len(S)

MOD = 10**9 + 7
mod = 13

A = [1, 10, 9, 12, 3, 4]
D = defaultdict(int)
a = 0

for i in range(N):
  if S[-1-i] == "?":
    D[A[i%6]] += 1
  else:
    a += A[i%6] * int(S[-1-i]) % mod
    a %= mod

ans = [0]*mod
ans[0] = 1

for i, x in D.items():
  for _ in range(x):
    prev = [a for a in ans]
    ans = [0]*mod
    for j in range(mod):
      for y in range(10):
        ans[(j+i*y)%mod] += prev[j]
      ans = [a%MOD for a in ans]

print(ans[(5-a)%mod])

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

if __name__ == '__main__':
  main()

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

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

Solution (Python):
def main():
    mod = 1000000007
    S = input()
    n = len(S)

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

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

    for i in range(1,n):
        s = S[i]
        if s == "?":
            for rem in range(10):
                for pre in range(13):
                    dp[i][(10*pre + rem) % 13] += dp[i-1][pre]
                    dp[i][(10*pre + rem) % 13] %= mod

        else:
            rem = int(s)
            for pre in range(13):
                    dp[i][(10*pre + rem) % 13] += dp[i-1][pre]
                    dp[i][(10*pre + rem) % 13] %= mod

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

S = rs()

L = len(S)

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

R = [0]*L
d = 1
for i in range(L):
	d %= 13
	R[i] = d
	d *= 10
R.reverse()

dp[0][0] = 1

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

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

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

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

Solution (Python):
S=input()
N=len(S)
mod=10**9+7
DP=[[0]*13 for i in range(N+1)]
DP[0][0]=1
for i in range(N):
  if S[i]=='?':
    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
  else:
    for j in range(13):
      DP[i+1][(j*10+int(S[i]))%13]=DP[i][j]
print(DP[N][5])

Solution (Python):
def resolve():
    S = list(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(len(S)):
        for j in range(13):
            if S[i] == "?":
                for k in range(10):
                    dp[i+1][(j*10+k)%13] += dp[i][j]
                    if dp[i+1][(j*10+k)%13] > MOD:
                        dp[i+1][(j*10+k)%13] -= MOD
            else:
                k = int(S[i])
                dp[i+1][(j*10+k)%13] += dp[i][j]
                if dp[i+1][(j*10+k)%13] > MOD:
                    dp[i+1][(j*10+k)%13] -= MOD
    print(dp[len(S)][5])

if '__main__' == __name__:
    resolve()

Solution (Python):
mod1,mod2=10**9+7,998244353
mod=mod1
dp=[0]*13
dp[0]=1
for i in input():
    if i=="?":
        dp=[sum(dp[4*(j-k)%13]for k in range(10))%mod for j in range(13)]
    else:
        x=int(i)
        dp=[dp[4*(j-x)%13]for j in range(13)]
    
    
print(dp[5])

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

for i in range(N):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
        
    for j in range(10):
        if c != -1 and c != j:
            continue
        else:
            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):
MOD = 10**9 + 7
s = input()
 
old_dp = [0] * 13
new_dp = [0] * 13
old_dp[0] = 1
 
for c in s:
    for i in range(13):
        if c == '?':
            for d in range(10):
                new_dp[(i*10 + d) % 13] += old_dp[i]
        else:
            new_dp[(i*10+int(c)) % 13] += old_dp[i]
    old_dp = [x % MOD for x in new_dp]
    new_dp = [0] * 13
    
print(old_dp[5])

Solution (Python):
import sys
s = input()[::-1]
mod = 10**9 + 7
dp = [0 for i in range(13)]

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

if len(s) == 1:
    print(dp[5])
    sys.exit()

for i, x in enumerate(s[1:], start=1):
    nextdp = [0 for j in range(13)]
    if x != '?':
        a = int(x) * pow(10, i, 13)
        for k in range(13):
            nextdp[(k + a)%13] += dp[k]%mod
            nextdp[(k + a)%13] %= mod
    else:
        for y in range(10):
            a = y * pow(10, i, 13)
            for k in range(13):
                nextdp[(k + a)%13] += dp[k]%mod
                nextdp[(k + a)%13] %= mod
    dp = nextdp
print(dp[5])

Solution (Python):
s = list(input())
MOD = 10**9 + 7
cnt = [[] for _ in range(len(s))]
i = len(s) - 1
de = 1

while i >= 0:
    if s[i] == '?':
        for j in range(10):
            cnt[i].append((j * de) % 13)
    else: cnt[i].append((int(s[i]) * de) % 13)
    i -= 1
    de *= 10
    de %= 13

dp = [[0]*13 for _ in range(len(s))]
for i in cnt[0]:
    dp[0][i] = 1
for i in range(1, len(s)):
    for j in cnt[i]:
        for k in range(13):
            if dp[i-1][k] != 0:
                dp[i][(j + k)%13] += dp[i - 1][k]
                dp[i][(j + k)%13] %= MOD
print(dp[-1][5])

Solution (Python):
import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13


print(dp[5])

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = input()
    n = len(s)
    m13 = [0,10,7,4,1,11,8,5,2,12,9,6,3]
    dp = [0]*13
    mod = 10**9+7
    dp[0] = 1
    for i in s:
        dpp = dp*1
        if i == "?":
            dp = [0]*13
            for j in range(13):
                for k in range(10):
                    nj = m13[j]+k
                    dp[(m13[j]+k)%13] = (dp[(m13[j]+k)%13]+dpp[j])%mod
        else:
            ii = int(i)
            for j in range(13):
                dp[(m13[j]+ii)%13] = dpp[j]
    print(dp[5])
    return

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

print(dp[n][5])

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    S = input()
    N = len(S)
    p = 10**9 + 7
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1

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

if __name__ == "__main__":
    main()

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

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

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

Solution (Python):
S = input()

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

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

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

mod = 1000000007

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

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

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

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

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

Solution (Python):
s = list(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][(j*10+k)%13] += dp[i][j] 
                dp[i+1][(j*10+k)%13] %= mod
        else:
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[n][5])

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

INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1
pow10 = 4
for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = (pow10*10)%13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])

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

INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow(10,i,13)
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])