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

print(dp[N][5])

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


S = input()

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

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

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


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

for i,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):
MOD = 10 ** 9 + 7

s = input()
l = len(s)
dp = [[0 for _ in range(13)] for _ in range(l + 1)]
dp[0][0] = 1
for i in range(l):
    if s[i] == "?":
        for k in range(10):
            for j in range(13):
                pos = (j * 10) + k
                pos %= 13
                dp[i + 1][pos] += dp[i][j]
                dp[i + 1][pos] %= MOD
    else:
        for j in range(13):
            pos = (j * 10) + int(s[i])
            pos %= 13
            dp[i + 1][pos] = dp[i][j]
print(dp[-1][5])

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

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

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


N = len(S)
MOD = 10**9 + 7


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


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



for i in range(1, 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:
            dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + int(S[i])) % 13] %= MOD

print(dp[N][5] % MOD)

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

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

S = input()

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

dp[0][0] = 1

for i, num in enumerate(S):

    if num == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][((j * 10) + k) % 13] += dp[i][j]
                

    else:
        k = int(num)
        for j in range(13):
            dp[i+1][((j * 10) + k) % 13] += dp[i][j]
            

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

print(dp[l][5])

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

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            

    dp = [nextdp[i] % mod for i in range(13)]

    
    

print(dp[5])

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

Solution (Python):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    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):
        s=S[i]
        
        for j in range(13):
            temp=dp[i][j]
            if s!="?":
                a=int(s)
                nxt=(j*10+a)%13
                dp[i+1][nxt]+=temp
                
            else:
                for k in range(10):
                    nxt=(j*10+k)%13
                    dp[i+1][nxt]=(dp[i+1][nxt]+temp)%mod
                    
    print(dp[-1][5])
    
    
    

main()

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


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

Solution (Python):
import sys

mod = 10**9 + 7
S = sys.stdin.readline().strip()

S = S[::-1]
ls = len(S)
dp = [0] * 13
dp[0] = 1
for i in range(ls):
    ndp = [0] * 13
    
    for j in range(13):
        if dp[j] == 0:
            continue
        digit = pow(10, i, 13)
        if S[i] == "?":
            for k in range(10):
                r = k * digit + j
                r %= 13
                ndp[r] += dp[j]
                ndp[r] %= mod

        else:
            n = int(S[i])
            r = n * digit + j
            r %= 13
            ndp[r] += dp[j]
            ndp[r] %= mod

    
    dp = ndp

print(dp[5])

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

print(dp[n][5])

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


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

for i in range(len(S)):
    pow10 = pow(10,i,13)
    if S[i] != '?':
        d = int(S[i])
        for r in range(13):
            dp[i+1][(r + d*pow10) % 13] = dp[i][r]
    else:
        for d in range(10):
            for r in range(13):
                dp[i+1][(r + d*pow10) % 13] += dp[i][r]
                dp[i+1][(r + d*pow10) % 13] %= MOD

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

Solution (Python):
mod = 10**9 + 7
s = input()
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i, si in enumerate(s):
  if si == '?':
    for ss in range(10):
      for j in range(13):
        dp[i+1][(j*10+ss)%13] += dp[i][j]
        dp[i+1][(j*10+ss)%13] %= mod
  else:
    ss = int(si)
    for j in range(13):
      dp[i+1][(j*10+ss)%13] += dp[i][j]
      dp[i+1][(j*10+ss)%13] %= mod

print(dp[n][5])

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(input())[::-1]
leng = len(S)
mod = 10**9+7

old_dp = [0]*13
old_dp[0] = 1

for i in range(leng):
    dp = [0]*13
    if S[i]!='?':
        d = int(S[i])
        d = d*pow(10, i, 13)
        for j in range(13):
            dp[j] += old_dp[(j-d)%13]
            dp[j] %= mod
    else:
        for d in range(10):
            d = d*pow(10, i, 13)
            for j in range(13):
                dp[j] += old_dp[(j-d)%13]
                dp[j] %= mod
    old_dp = dp

print(dp[5])

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

Solution (Python):
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

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

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

print(dp[-1][5])

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

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

for i, x in enumerate(s):
    
    if i == 0:
        tmp = 1
    else:
        tmp = tmp * 10 % 13
    if x != "?":
        move = int(x) * tmp
        if i == 0:
            dp[i][move] = 1
        else:
            for j in range(13):
                dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                dp[i][j] %= MOD
    else:
        for coef in range(10):
            move = coef * tmp
            if i == 0:
                dp[i][move] = 1
            else:
                for j in range(13):
                    dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                    dp[i][j] %= MOD

print(dp[-1][5])

Solution (Python):
s=input()

mod=10**9+7

ans=[[0]*13 for _ in range(len(s))]

if s[-1]=="?":
    for i in range(10):
        ans[-1][i%13]+=1
else:
    ans[-1][int(s[-1])%13]+=1



ten=1
for ii in range(1,len(s)):
    ten=(ten*10)%13

    i=len(s)-ii-1
    
    if s[i]!="?":
        tmp=(int(s[i])*ten)%13
        for j in range(13):
            ans[i][(tmp+j)%13]+=(ans[i+1][j])%mod
    else:
        for k in range(10):
            tmp=(k*ten)%13
            for j in range(13):
                ans[i][(tmp+j)%13]+=(ans[i+1][j])%mod

print(ans[0][5]%mod)

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

n = len(S)

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

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

Solution (Python):
S = str(input()); N = len(S)
S = list(S); S.reverse() 
MOD = pow(10,9)+7
dp = [0 for _ in range(13)] 
dp[0] = 1
keta = 1
for i in range(N):
  p = [0 for _ in range(13)]
  dp,p = p,dp 
  if i != 0:
    keta = (keta*10)%13
  if S[i] == "?":
    for x in range(10):
      amari = x*keta%13
      for j in range(13):
        if j >= amari:
          mae = j-amari
        else:
          mae = j-amari+13
        dp[j] += p[mae]%MOD
  else:
    amari = int(S[i])*keta%13
    for j in range(13):
      if j >= amari:
        mae = j-amari
      else:
        mae = j-amari+13
      dp[j] += p[mae]%MOD

print(dp[5]%MOD)

Solution (Python):
S = input()
N = len(S)
m = 10**9 + 7

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

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

        else:
            k = int(digit)
            d = (j+k*p%13)%13
            dp[d][i+1] += dp[j][i]
            dp[d][i+1] %= m
print(dp[5][N])

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


print(dp[n][5])

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

Solution (Python):
def func(cnt, cn):
    tmp = [0] * 13
    for i in range(13):
        nn = (cn + i) % 13
        tmp[nn] = cnt[i]
    return tmp


MOD = 10**9+7

s = list(input())
s.reverse()

cnt = [0]*13
cnt[0] = 1
t = 1
for ci in range(len(s)):
    t %= 13 
    if s[ci] != '?':
        cn = int(s[ci]) * t % 13
        cnt = func(cnt, cn)
    else:
        tmp = [0]*13
        add = [0]*13
        for cj in range(10):
            cn = cj * t % 13
            add = func(cnt, cn)
            for _ in range(13):
                tmp[_] += add[_]
                tmp[_] %= MOD
        cnt = tmp
    t *= 10
print(cnt[5])

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

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

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

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

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


rests = [0] * 13
for i in range(len(rests)):
  rests[i] = i * 10 % 13
  
dp = [[0] * 13 for i in range(len(S))]

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

for i in range(1, len(dp)):
  x = S[i]
  if x != "?":
    x = int(x)
    
    for j in range(len(dp[i - 1])):
      dp[i][(rests[j] + x) % 13] += dp[i - 1][j]
      dp[i][(rests[j] + x) % 13] %= MOD
  else:
    
    for j in range(len(dp[i - 1])):
      for k in range(10):
        dp[i][(rests[j] + k) % 13] += dp[i - 1][j]
        dp[i][(rests[j] + k) % 13] %= MOD
  
print(dp[-1][5])

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


@nb.njit("i8(i8[:])", cache=True)
def solve(S):
    N = len(S)
    dp = np.zeros(shape=(N + 1, Q), dtype=np.int64)
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == -1:
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            for j in range(Q):
                dp[i + 1][(10 * j + D) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

    return dp[N][5]


def main():
    S = input().rstrip()

    S = np.array([int(s) if s != "?" else -1 for s in S], dtype=np.int64)
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


@nb.njit("i8(i8[:])", cache=True)
def solve(S):
    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == -1:
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            d = int(D)
            for j in range(Q):
                dp[i + 1][(10 * j + d) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

    return dp[N][5]


def main():
    S = input().rstrip()

    S = np.array([int(s) if s != "?" else -1 for s in S], dtype=np.int64)
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == "?":
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            d = int(D)
            for j in range(Q):
                dp[i + 1][(10 * j + d) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        base = pow(10, N - 1 - i, Q)
        D = S[i]
        if D == "?":
            for d in range(10):
                n = d * base
                for j in range(Q):
                    next_j = (j + n) % Q
                    dp[i + 1][next_j] += dp[i][j]
                    dp[i + 1][next_j] %= P
        else:
            n = int(D) * base
            for j in range(Q):
                next_j = (j + n) % Q
                dp[i + 1][(j + n) % Q] += dp[i][j]
                dp[i + 1][(j + n) % Q] %= P

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


if __name__ == "__main__":
    main()

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

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

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

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

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

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

MOD = pow(10, 9) + 7

n = len(s)

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




if s[-1] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[-1])
    dp[0][q] = 1

r = 1

for i in range(1, n):
    r = r * 10 % 13
    
    

    

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

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

Solution (Python):
S = input()
INF = 10 ** 9 + 7
length = len(S)
tmp = 1
mod = 0
cnt = 0
arr = []
for i in reversed(range(length)):
    if S[i] == "?":
        arr.append(tmp)
        cnt += 1
    else:
        mod += (tmp * int(S[i])) % 13
        mod %= 13
    tmp = (tmp * 10) % 13
tar = (5 - mod) % 13

dp = [[0 for _ in range(13)] for _ in range(cnt + 3)]
dp[0][0] = 1
for i in range(1, cnt + 1):
    for j in range(13):
        for k in range(10):
            dp[i][(j + arr[i - 1] * k) % 13] += dp[i - 1][j]
            dp[i][(j + arr[i - 1] * k) % 13] %= INF
ans = dp[cnt][tar]
print(ans)

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

print(dp[L][5])

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    s = list(input())

    s.reverse()

    devval = pow(10, 9) + 7

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

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

    
    for i in range(1, len(s)):
        for j in range(10):
            if s[i] != "?" and s[i] != str(j):
                continue

            
            aaa = j * pow(10, i, 13)

            
            for k in range(13):
                dp[i][(aaa + k) % 13] = (dp[i][(aaa + k) % 13] + dp[i - 1][k] % devval) % devval

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



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """??2??5"""
        output = """768"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """?44"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """7?4"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"""
        output = """153716888"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """?"""
        output = """1"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
from collections import Counter
from itertools import product
s = list(input())
MOD = 10**9+7
c = Counter([0])
ds = list(range(10))
mods = list(range(13))

ten_power = 1
while s:
    char = s.pop()
    if char == '?':
        cand = ds
    else:
        cand = [int(char)]
    nc = Counter()
    for key, d in product(mods, cand):
        new_key = (key + d * ten_power) % 13
        nc[new_key] += c[key]
        nc[new_key] %= MOD
    c = nc
    ten_power *= 10
    ten_power %= 13

print(nc[5])

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

numbers = list(range(10))
for i in range(n):
    next_nums = numbers if s[i] == '?' else [int(s[i])]
    for j in range(13):
        for k in next_nums:
            jj = (10 * j + k) % 13
            dp[i + 1][jj] = (dp[i + 1][jj] + dp[i][j]) % mod
print(dp[n][5])

Solution (Python):
mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                jj = (10 * j + k) % 13
                dp[i + 1][jj] = (dp[i + 1][jj] + dp[i][j]) % mod
    else:
        k = int(s[i])
        for j in range(13):
            jj = (10 * j + k) % 13
            dp[i + 1][jj] = (dp[i + 1][jj] + dp[i][j]) % 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):
    c = int(S[i]) if S[i] != "?" else -1
    for j in range(10):
        if c == -1 or c == j:
            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
ans = dp[N][5]
print(ans)

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


def main():
  S = input()[:-1]
  dp = [[0]*13 for _ in range(len(S)+1)]
  dp[0][0] = 1

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

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


if(__name__ == '__main__'):
  main()

Solution (Python):
import sys
import numpy as np
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


def convolve(x, y):
    MOD = 10**9+7
    z = np.convolve(x, y) % MOD
    z[:12] += z[13:25]
    return z[:13] % MOD


def main():
    mod = 10**9+7
    S = input()[::-1]
    dp = np.zeros((len(S), 13), dtype='int64')
    amari = 1
    if S[0] == '?':
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    for i in range(1, len(S)):
        arr = np.zeros(13, dtype='int64')
        amari = 10*amari % 13
        if S[i] == '?':
            for si in range(10):
                arr[amari*si % 13] += 1
        else:
            arr[amari*int(S[i]) % 13] = 1
        dp[i] = convolve(dp[i-1], arr)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    mod = 10**9+7
    S = input()[::-1]
    amari = 1
    dp = [[0]*13 for i in range(len(S))]
    if S[0] == '?':
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    for i in range(1, len(S)):
        amari = 10*amari % 13
        if S[i] == '?':
            for j in range(13):
                for si in range(10):
                    dp[i][(j+amari*si) % 13] += dp[i-1][j]
                    dp[i][(j+amari*si) % 13] %= mod

        else:
            for j in range(13):
                dp[i][(j+amari*int(S[i])) % 13] = dp[i-1][j]

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


if __name__ == '__main__':
    main()

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):
    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] %= MOD

print(dp[-1][5])

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    
    
    
    
    

    s=input()
    N=len(s)
    dp=[[0]*13 for i in range(N+1)]
    dp[0][0]=1
    cur=1
    for i in range(1,N+1):
        si=s[-i]
        if si.isnumeric():
            si=int(si)
            for j in range(13):
                nj=(j+cur*si)%13
                dp[i][nj]+=dp[i-1][j]
                
        else:
            tsum=0
            for j in range(13):
                for k in range(10):
                    nj=(j+k*cur)%13
                    dp[i][nj]+=dp[i-1][j]
                    dp[i][nj]%=mod

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






if __name__ == "__main__":
    main()

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