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

Solution (Python):
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    s = S[index]
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])

Solution (Python):
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    if S[index] == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(S[index])
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])

Solution (Python):
MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for j in range(13)] for i in range(n + 1)]
dp[0][0] = 1
dpi = dp[0]
for i, si in enumerate(s):
    dpi1 = dp[i + 1]
    if si == '?':
        k_list = range(10)
    else:
        k_list = [int(si)]
    for j in range(13):
        xij = dpi[j]
        for k in k_list:
            dpi1[(j * 10 + k) % 13] += xij
    for j in range(13):
        dpi1[j] %= MOD
    dpi = dpi1
print(dp[-1][5])

Solution (Python):
MOD=1000000007
S=input()[::-1]
N=len(S)
pows=list(range(10))
dp=[[0]*13 for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for src in range(13):
        for j,p in enumerate(pows):
            if S[i]=='?' or int(S[i])==j:
                dst = (src+p)%13
                dp[i+1][dst] = (dp[i+1][dst]+dp[i][src])%MOD
    for i in range(10):
        pows[i]=(pows[i]*10)%13
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,d in enumerate(s):
	if d=="?":
		for x in range(10):
			for y in range(13):
				dp[i+1][(y*10+x)%13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i+1][(y*10+d)%13] += dp[i][y]
	for j in range(13):
		dp[i+1][j] %= mod
print(dp[n][5])

Solution (Python):
S = input()

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1
mul = 1
INF = 10 ** 9 + 7

for i in range(length):
    
    x = S[- (i + 1)]
    
    if x == "?":
        
        for j in range(13):
            
            for k in range(10):
            
                dp[i + 1][(k * mul + j) % 13] += dp[i][j]
                dp[i + 1][(k * mul + j) % 13] %= INF
                
    else:
        
        c = int(x)
        
        for j in range(13):
            
            dp[i + 1][(c * mul + j) % 13] += dp[i][j]
            dp[i + 1][(c * mul + j) % 13] %= INF
            
    mul = (mul * 10) % 13
    
print(dp[length][5])

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

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

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

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

Solution (Python):
s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])

Solution (Python):
def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      j10 = 0
      for j in list13:
        dpij = dpi[j]
        for k in list10:
          dpi1[lut[j10 + k]] += dpij
        j10 += 10
    else:
      t = int(s[i])
      for j in list13:
        dpi1[t] += dpi[j]
        t = lut[t + 10]
    for k in list13:
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Solution (Python):
def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  list10 = list(range(10))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      j10 = 0
      for j in range(13):
        dpij = dpi[j]
        for k in list10:
          dpi1[lut[j10 + k]] += dpij
        j10 += 10
    else:
      t = int(s[i])
      for j in range(13):
        dpi1[lut[t]] += dpi[j]
        t += 10
    for k in range(13):
      dp[i + 1][k] %= divisor
  print(dp[len(s)][5])
main()

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

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

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

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

Solution (Python):

import sys


MOD = 1000000007  


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

Solution (Python):

import sys


MOD = 1000000007  


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

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

S = input()
L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

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

print(dp[L][5])

Solution (Python):





from sys import stdin,setrecursionlimit


setrecursionlimit(10**6)
input=stdin.readline

s=input().rstrip()
dp=[[0]*13 for _ in range(10**5+5)]
n=len(s)
dp[0][0]=1
mod=10**9+7
for i in range(n):
    c=-1 if s[i]=="?" else int(s[i])
    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):
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] == '?':
        c = -1
    else:
        c = int(s[i])
        
    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

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

Solution (Python):
import numpy as np
MOD = 10 ** 9 + 7

S = [int(x) if x != "?" else -1 for x in input()]
N = len(S)


r = [0]*13


s = S[0]
if s != -1:
  r[s] = 1
else:
  for i in range(10):
    r[i] = 1


for i in range(1, N):
    
    
    dp = [0]*26
    
    for j in range(13):
      dp[j*10%13] += r[j] % MOD
    
    dp[13:26] = dp[0:13]
    r = [0]*13
    s = S[i]
    if s == -1:
      w = sum(dp[4:14])
      for j in range(13):
        r[j] += w
        w += dp[j+1] -dp[j+4]
    else:
      for j in range(13):
        r[j] += dp[13-s+j]
print(r[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):
from sys import exit, stderr, stdin
input = stdin.readline


def main():
    MOD = 10**9 + 7
    S = input()[:-1]
    L = len(S)
    
    memo = [0 for _ in range(13)]
    memo[0] = 1

    for i in range(L):
        memo_prev = [x for x in memo]
        memo = [0 for _ in range(13)]
        
        if S[i].isnumeric():
            n = int(S[i])
            for m in range(13):
                cur = (10*m+n)%13
                memo[cur] += memo_prev[m]
        
        else:
            for n in range(10):
                for m in range(13):
                    cur = (10*m+n)%13
                    memo[cur] += memo_prev[m]
            for m in range(13):
                memo[m] %= MOD
    print(memo[5])


if __name__ == "__main__":
    main()

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

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

for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

Solution (Python):
s=input()
l=len(s)

mod=10**9+7

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

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

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

Solution (Python):
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() 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)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    s = S().strip()
    dp = [0] * 13
    dp[0] = 1
    trans_list = [i * 10 % 13 for i in range(13)]
    for i in s:
        nxt_dp = [0] * 13
        for j in range(13):
            if i == '?':
                for k in range(10):
                    nxt_dp[(trans_list[j] + k) % 13] += dp[j]
                    nxt_dp[(trans_list[j] + k) % 13] %= mod
            else:
                nxt_dp[(trans_list[j] + int(i)) % 13] += dp[j]
                nxt_dp[(trans_list[j] + int(i)) % 13] %= mod
        dp = nxt_dp

    return dp[5]


print(main())

Solution (Python):
def main():
  s = input()[::-1]
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0] * 13
  np = [0] * 13
  rt = [i % 13 for i in range(121)]
  p[0] = 1
  for i in range(len(s)):
    if s[i] != '?':
      r = rt[int(s[i]) * multiplier]
      for j in list13:
        np[rt[j + r]] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[rt[k + r]] += p[k]
        r = rt[r + multiplier]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
    multiplier = rt[10 * multiplier]
  print(p[5])
main()

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

S = input()

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

Solution (Python):

s = input()
n = len(s)
dp1 =[0 for _ in range(13)]
dp1[0]=1


move = [[] for _ in range(13)]

for i in range(10):
    for j in range(13):
        move[(10*j+i)%13].append(j)



for i in range(n):
    dp2 =[0 for _ in range(13)]
    if s[i]=="?":
        si = range(10)
        for mod,ex in enumerate(move):
            dp2[mod] += sum([dp1[x] for x in ex])
    else:
        si = int(s[i])
        for j in range(13):
            dp2[(10*j+si)%13]+=dp1[j]
    dp1 = [x%(10**9+7) for x in dp2] 


print(dp1[5])

Solution (Python):
S = input()

P = 10**9+7
LENGTH = len(S)

"""dp[i][j] -> あり得る全ての上からi+1桁目までの数を13で割った余りが j となる状態数"""
dp = [[0 for i in range(13)] for j in range(LENGTH)]

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

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

print(dp[LENGTH-1][5]%P)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

class mod:
    def __init__(self, v=0):
        self.v = v
        self.v %= MOD
    def __add__(self, v):
        self.v += v.v
        self.v %= MOD
        return self
    def __str__(self):
        return str(self.v)


def main():
    S = input(str)
    dp = [[mod(0) for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0].v = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                
    print(dp[-1][5])

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

class mod:
    def __init__(self, v=0):
        self.v = v
        self.v %= MOD
    def __add__(self, v):
        self.v += int(v)
        self.v %= MOD
        return self
    def __sub__(self, v):
        self.v -= int(v)
        return self
    def __mul__(self, v):
        self.v *= int(v)
        self.v %= MOD
        return self
    def __int__(self):
        return int(self.v)
    def __str__(self):
        return str(self.v)


def main():
    S = input(str)
    dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0] = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                dp[i][(n * 10 + m) % 13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

class mod:
    def __init__(self, v=0):
        self.v = v
        self.v %= MOD
    def __add__(self, v):
        self.v += int(v)
        self.v %= MOD
        return self
    def __sub__(self, v):
        self.v -= int(v)
        return self
    def __mul__(self, v):
        self.v *= int(v)
        self.v %= MOD
        return self
    def __int__(self):
        return int(self.v)
    def __str__(self):
        return str(self.v)


def main():
    S = input(str)
    dp = [[mod(0) for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0].v = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
    print(dp[-1][5])

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):

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

mod = 1e9+7
mul = 1
for i in range(len(S)-1, -1, -1):
  nextDP = [0 for _ in range(N)]
  c = S[i]
  if c=="?":
    for k in range(10):
      for j in range(N):
        nextDP[(k*mul + j)%N] += dp[j]
        nextDP[(k*mul + j)%N] %= mod  
  else:
    k = int(c)
    for j in range(N):
      nextDP[(k*mul + j)%N] += dp[j]
      nextDP[(k*mul + j)%N] %= mod  
    
  mul *= 10
  mul %= N
  dp = nextDP
print(int(dp[5]))

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

Solution (Python):
import math
from collections import defaultdict

mod = pow(10, 9)+7

def digits_parade(strr, n):
	dp = [[0]*13 for i in range(n)]
	if strr[0]=="?":
		for k in range(10):
			dp[0][k] = 1
	else:
		dp[0][int(strr[0])] = 1

	for i in range(1, n):
		if strr[i]=="?":
			for j in range(10):
				temp = j
				for k in range(13):
					dp[i][(10*k + temp)%13] += dp[i-1][k]
					dp[i][(10*k + temp)%13] %= mod
		else:
			temp = int(strr[i])
			for k in range(13):
				dp[i][(10*k + temp)%13] += dp[i-1][k]
				dp[i][(10*k + temp)%13] %= mod
	return dp[n-1][5]

strr = input()
n = len(strr)

ans =digits_parade(strr, n)
print(ans)

Solution (Python):
import numpy as np
s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10**9+7

amari = np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
arrays = [np.eye(13, k=i, dtype=np.int64)+np.eye(13, k=i-13, dtype=np.int64) for i in range(13)]
brrays = [sum(arrays[c*effects[i]%13] for c in range(10)) for i in range(6)]
for i, c in enumerate(reversed(s)) :
    if c != "?" :
        c = int(c)
        array = arrays[c*effects[i%6]%13]
        amari = np.dot(amari, array)
    else :
        array = brrays[i%6]
        amari = np.dot(amari, array)%mod

print(amari[5])

Solution (Python):
s=input()[::-1]
p=[1]+[0]*12
q=1
t=[[(i*k)%13 for i in range(10)]for k in range(13)]
for i in s:
    if i!="?":
        i=int(i)
        g=t[q][i]
        p=p[-g:]+p[:-g]
    else:
        d=[0]*13
        for j in t[q]:
            r=p[-j:]+p[:-j]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Solution (Python):
s=input()[::-1]
p=[1]+[0]*12
q=1
t=[[(i*k)%13 for i in range(10)]for k in range(13)]
for i in s:
    if i!="?":
        i=int(i)
        g=t[q][i]
        p=p[-g:]+p[:-g]
    else:
        d=[0]*13
        for j in t[q]:
            r=p[-j:]+p[:-j]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Solution (Python):
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i] % div
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i] % div
        rem = temp
    return rem[5] % div

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

Solution (Python):
s=input()
n=len(s)
dp=[[0]*13 for _ in range(100010)]
dp[0][0]=1
for i in range(n):
    for j in range(10):
        if s[i]==str(j) or s[i]=="?":
            for h in range(13):
                dp[i+1][(h*10+j)%13]+=dp[i][h]
    for h in range(13):
        dp[i+1][h]%=1000000007
print(dp[n][5])

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



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


dp[0][0] = 1

for i in range(len(S)):
    
    
    for remain in range(13):  
        
        if S[i] == '?':  
            for target in range(10):  
                next_remain = (remain*10 + target) % 13
                dp[i+1][next_remain] += dp[i][remain]
                dp[i+1][next_remain] %= 1000000007
        else:
            next_remain = (remain*10 + int(S[i])) % 13
            dp[i+1][next_remain] += dp[i][remain]
            dp[i+1][next_remain] %= 1000000007



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

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

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

dp[0][0] = 1

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

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

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

Solution (Python):
MOD = 10 ** 9 + 7
 
s = str(input())
 
s = list(s)
 
cur = [0] * 13
 
if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1
 
for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD
 
print(cur[5] % MOD)

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

s = str(input())

s = list(s)

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD

print(cur[5] % MOD)

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

Solution (Python):

mod = 1000000007
S = str(input())
N = len(S)


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

    for k in range(13):
        dp[i+1][k]%=mod
            
print(dp[N][5]%mod)

Solution (Python):
MOD = 10**9 + 7
S = input()
 
cur = [0] * 13
cur[0] = 1
r = 1
base = 0
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        prev = cur
        cur = [sum(prev)] * 13
        for m in range(13):
            for d in range(10,13):
                cur[(m + r*d) % 13] -= prev[m]
        for m in range(13):
            cur[m] %= MOD
    else:
        base = (base + r*int(s)) % 13
 
    r = (10 * r) % 13
 
print(cur[(5-base) % 13])

Solution (Python):
mod = 10**9+7
s=[x for x in input()]
n=len(s)
dp=[[0 for i in range(13)] for j in range(n+1)]
dp[0][0]=1
for i in range(n):
  for j in range(10):
    if s[i]!='?' and s[i]!=str(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]=dp[i+1][j]%mod
print(dp[n][5])

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

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

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

Solution (Python):
S = list(input())
N = len(S)
dp = [[0] * 13 for _ in range(N+1)]
MOD = 10**9 + 7
s = S[0]
if s=='?':
    for k in range(10):
        dp[0][k] = 1
else:
    dp[0][int(s)] = 1
 

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

Solution (Python):
s = list(input())
n = len(s)
s.reverse()
m = 10**9 + 7
p = 10
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        k = (s1*p)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        for x in range(10):
            k = (x*p)%13
            for j in range(13):
                dp[i][(j+k)%13] += dp[i-1][j]
                dp[i][(j+k)%13] %= m
    p = (p * 10) % 13
print(dp[n-1][5])

Solution (Python):
import copy
MOD = 10**9+7
s = list(input())
n = len(s)
s.reverse()
dp = []
tem = []
for i in range(13):
    tem.append(0)
for i in range(n+1):
  dp.append(copy.copy(tem))
dp[0][0]=1
beki = 1
for i in range(1,n+1):
    if s[i-1] != "?":
        s1 = int(s[i-1])
        k = (s1*beki)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
            
            dp[i][(j+k)%13]%=MOD
    else:
        for j in range(10):
            k = (j*beki)%13
            for x in range(13):
                dp[i][(x+k)%13] += dp[i-1][x]
                dp[i][(x+k)%13]%=MOD
    beki=beki*10
    beki%=13
    
print(dp[n][5])