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

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[0 for _ in range(13)]

DP[0]=1
m = 10**9+7
mul = 1
for i in range(len(s)):
    dig = s[i]
    nextDP = [0 for _ in range(13)]
    if dig == '?':
        for j in range(10):
            for k in range(13):
                nextDP[(k+mul*j)%13] += DP[k]
                nextDP[(k+mul*j)%13]%=m
    else:
        j = int(dig)
        for k in range(13):
            nextDP[(k+mul*j)%13] += DP[k]
            nextDP[(k+mul*j)%13]%=m

    mul *= 10
    mul%=13
    DP = nextDP

print(DP[5]%m)

Solution (Python):
s = input()

mod = 10 ** 9 + 7

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

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

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

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

Solution (Python):


import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
S = readline().decode().rstrip()
N = len(S)

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










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

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

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

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

Solution (Python):
S = ''.join(list(reversed(input())))
N = len(S)
p = 13
mod = 10**9 + 7

dp = [[0]*p for _ in range(N)]

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

b = 10
for i in range(N - 1):
    r = []
    if S[i + 1] == '?':
        for j in range(10):
            r.append(b * j % p)
    else:
        r.append(b * int(S[i + 1]) % p)

    for j in range(len(r)):
        for k in range(p):
            if dp[i][k] > 0:
                dp[i + 1][(k + r[j]) % p] += dp[i][k]
                dp[i + 1][(k + r[j]) % p] %= mod

    b *= 10
    b %= p

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

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

for i in range(len(S)):
    cdp = [0] * 13
    tmpS = 0
    if S[i] == '?':
        tmpS = -1
    else:
        tmpS = int(S[i])
    for j in range(10):
        if tmpS != -1 and tmpS != j: continue
        for k in range(13):
            cdp[(k * 10 + j) % 13] += dp[k]
            cdp[(k * 10 + j) % 13] %= MOD

    dp = cdp[:]
print(dp[5])

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

for i in range(len(S)):
    tmpS = 0
    if S[i] == '?':
        tmpS = -1
    else:
        tmpS = int(S[i])
    for j in range(10):
        if tmpS != -1 and tmpS != j: continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
            dp[i + 1][(k * 10 + j) % 13] %= MOD

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 





S = input()[::-1]

arr = []
for i, x in enumerate(S):
	if x in digits:
		n = pow(10, i, 13)*int(x)%13
		arr.append(n)
	else:
		arr.append(pow(10, i, 13))

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

dp[0][0] = 1

for i, x in enumerate(arr, 1):
	if S[i-1] == "?":
		for k in range(10):
			for j in range(13):
				dp[i][j] += dp[i-1][(j-k*x)%13]
				dp[i][j] %= mod

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


print(dp[-1][5])

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

dp[0][0] = 1

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

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

Solution (Python):
def f(i,k):
  for j in range(13):
    dp[i+1][(k*mul+j)%13]+=dp[i][j]
    dp[i+1][(k*mul+j)%13]%=mod
  
mod=10**9+7
s=input()[::-1]
n=len(s)
dp=[[0]*13 for i in range(10**5+1)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  mul*=10
  mul%=13
  
print(dp[n][5]%mod)

Solution (Python):
def f(i,k):
  for j in range(13):
    dp[i+1][(j*10+k)%13]+=dp[i][j]
    dp[i+1][(j*10+k)%13]%=mod
  
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*13 for i in range(10**5+1)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  
print(dp[n][5]%mod)

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

def main(s):
    mod = 10**9 + 7
    
    rem = [1]
    for i in range(11):
        rem.append((rem[-1]*10)%13)
    
    arr = []
    
    init = 0
    for i in range(len(s)):
        if s[i]=="?":
            arr.append(len(s)-i-1)
        else:
            init += (int(s[i]) * rem[(len(s)-i-1)%12])%13
            init %= 13

    
    dp = [[0 for i in range(13)]]
    dp[0][0] = 1
    for i in arr:
        temp = [0 for i in range(13)]
        prev = dp[-1]
        for j in range(13):
            for k in range(10):
                update = prev[j]
                temp[(j+k*rem[i%12])%13] += update
                temp[(j+k*rem[i%12])%13] %= mod
        dp.append(temp)

    print(dp[-1][(18-init)%13])
    
                
if __name__=="__main__":
    s = getval()
    main(s)

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):
    for j in range(13):
        for k in range(10):
            if S[i] == str(k) or 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 math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

  return dp[n][5]%mod


print(main())

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

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

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

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

print(dp[-1][5])

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

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

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

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

print(dp[-1][5])

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

conv = {}
for i in range(13):
  conv[i] = (i * 10) % 13

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

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

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

print(dp[-1][5])

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

def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

p=10**9+7
for n in range(len(S)):
    x=pow_k(10,n,13)
    if S[n]=='?':
        for i in range(10):
            for m in range(13):
                dp[(n+1)][(m+i*x)%13]=(dp[(n+1)][(m+i*x)%13]+dp[n][m])%p
    else:
        s=int(S[n])
        for m in range(13):
            dp[(n+1)][(m+s*x)%13]=dp[n][m]%p

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

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1

    for i,s in enumerate(s[::-1],start = 1):
        p10 = pow(10,i-1,13)
        if s!= "?":
            for k in range(13):
                dp[i][(int(s)*p10 + k)%13] += dp[i-1][k]
                dp[i][(int(s)*p10 + k)%13] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    dp[i][(j*p10 + k)%13] += dp[i-1][k]
                    dp[i][(j*p10 + k)%13] %= MOD
    print(dp[n][5] % MOD)


if __name__=="__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit, i8

S = input()
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype=int)
dp[0] = 1


@njit(cache=True)
def q_mark(dp):
    new_dp = np.zeros(13, dtype=i8)
    for i in range(13):
        new_dp[np.arange(i, i + 10) % 13] += dp[i]
        new_dp %= MOD
    return new_dp


for s in S:
    
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        dp = q_mark(dp)
    else:
        dp = np.roll(dp, int(s))
print(dp[5])

Solution (Python):
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7
    dp = [[0 for _ in range(13)] for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        if s[i - 1] == "?":
            for now in range(10):
                for before in range(13):
                    ind = (now + 10 * before) % 13
                    dp[i][ind] += dp[i - 1][before]
                    dp[i][ind] %= mod
        else:
            for before in range(13):
                ind = (int(s[i - 1]) + 10 * before) % 13
                dp[i][ind] += dp[i - 1][before]
                dp[i][ind] %= mod
    print(dp[n][5])


if __name__ == '__main__':
    main()

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


if __name__ == "__main__":
    main()

Solution (Python):
S = input()[::-1]
P = 13
qs = [0]*13
tmp = 1
rest = 0
for i, s in enumerate(S):
    if s == '?':
        qs[tmp] += 1
    else:
        rest = (rest + int(s) * tmp) % P
    tmp = (tmp * 10) % P

dp = [0] * 13
dp[rest] = 1
for i, cnt in enumerate(qs):
    for _ in range(cnt):
        dp_new = [0]*13
        for j in range(10):
            tmp = (i * j) % P
            for k in range(P):
                dp_new[(k + tmp) % P] = (dp_new[(k + tmp) % P] + dp[k])%int(1e9+7)
        dp = dp_new
print(dp[5]%int(1e9+7))

Solution (Python):
S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9 + 7
mul = 1


for i in range(N):
    for k in range(10):
        if S[-i-1] != '?' and S[-i-1] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j + mul * k) % 13] += dp[i][j]
    mul = (mul * 10) % 13
    for j in range(13):
        dp[i+1][j] %= MOD

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

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

    else:
        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] %= mod


print(dp[n][5])

Solution (Python):
S = input()
dp = 13*[0]
dp[0] = 1
mod = 10**9+7

for s in S:
  if s=="?":
    dp = [sum(dp[4*(j-i)%13] for i in range(10))%mod for j in range(13)]
  else:
    dp = [dp[4*(j-int(s))%13] for j in range(13)]
    
print(dp[5])

Solution (Python):
s = input()

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

Solution (Python):
S = list(input())
N = len(S)
dp=[]
MOD = (10 ** 9) + 7
f = S.pop(0)
if f == '?':
  dp_low = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  dp_low = [0] * 13
  dp_low[int(f)] = 1
  
dp.append(dp_low)
for i in range(N-1):
  dp_low = [0] * 13
  if S[i] == '?':
    for j, val in enumerate(dp[i]):
      for k in range(10):
        temp = ((j * 10) + k) % 13
        dp_low[temp] += val
  else:
    for j, val in enumerate(dp[i]):
      temp = ((j * 10) + int(S[i])) % 13
      dp_low[temp] += val
  for i in range(13):
    dp_low[i] %= MOD
  dp.append(dp_low)
print(dp[-1][5])

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

p = 1

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

for i in range(1,N+1):
  if S[-i] == '?':
    for k in range(10):
      a = (k * p) % 13
      for j in range(13):
        dp[i][j] += dp[i-1][j-a] % mod
        dp[i][j] %= mod
  else:
    a = (int(S[-i]) * p) % 13
    for j in range(13):
      dp[i][j] += dp[i-1][j-a] % mod
  p = (p * 10) % 13

print(dp[N][5])

Solution (Python):
from collections import defaultdict
s = input()
s = s[::-1]

app = [0 for _ in range(13)]

for i in range(len(s)):
    tmp_dic = [0 for _ in range(13)]
    if i == 0:
        if s[i] != '?':
            tmp_dic[int(s[i])]+= 1
        else:
            for j in range(10):
                tmp_dic[j] += 1

    else:
        if s[i] != '?':
            tmp = int(s[i]) * pow(10, i, 13)
            for j in range(13):
                tmp_dic[(tmp+j)%13] += app[j] % (10**9+7)

        else:
            for j in range(10):
                tmp = int(j) * pow(10, i, 13)
                for k in range(13):
                    tmp_dic[(tmp+k)%13] += app[k] % (10**9+7)

    app = tmp_dic
    

print(app[5] % (10**9+7))

Solution (Python):

import sys

s=input()

n=[0]*6
q=[0]*6
j=[1,10,9,12,3,4,1]
lens=len(s)
for i in range(lens):
    i6=i%6
    if s[lens-1-i]=="?":
        q[i6]+=1
    else:
        n[i6]+=int(s[lens-1-i])

mod=10**9+7
    
nsum=0
for i in range(6):
    nsum+=(n[i]*j[i])%13
nsum=(5-nsum)%13

if q==[0]*6:
    if nsum==0:
        print(1)
    else:
        print(0)
    sys.exit()
        
cc2=[[-1]*13 for i in range(6)]

for i6 in range(6):
    for i in range(10):
        iii=(i*10**i6)%13
        cc2[i6][i]=iii


dpm=[0]*13
dpn=[0]*13
icnt=-1
for i6 in range(6):
    for i in range(q[i6]):
        dpn=[0]*13
        icnt+=1
        if icnt==0:
            for j in range(10):
                jj=(j*10**i6)%13


                dpm[jj]=1
            continue
        for mi in range(13):
            for j in range(10):

                ccir=(mi-cc2[i6][j])%13

                dpn[mi]=(dpn[mi]+dpm[ccir])%mod
        dpm=dpn.copy()  



print(dpm[nsum]%mod)

Solution (Python):
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
by = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*by%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*by%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
    by = by*10%13
print(dp[-1][5])

Solution (Python):
s = input()
n = len(s)
mod = 10 ** 9 + 7
amari = [1]
for i in range(n - 1):
    amari.append(amari[-1] * 10 % 13)
amari.reverse()
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(13):
        if s[i] == "?":
            temp = 0
            for k in range(10):
                temp += dp[i][(j - amari[i] * k) % 13]
                temp %= mod
            dp[i + 1][j] = temp
        else:
            num = int(s[i])
            dp[i + 1][j] = dp[i][(j - amari[i] * num) % 13]
print(dp[n][5])

Solution (Python):





import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string


BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def main():
    
    
    
    
    
    
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    dp[i][(t+j)%13]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        
        p=(p%13*10%13)%13
    
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

Solution (Python):





import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string


BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def main():
    
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    dp[i][(t+j)%13]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        p=(p%13*10%13)%13
    
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

Solution (Python):





import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string


BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def main():
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    temp=(t+j)%13
                    dp[i][temp]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        p=(p%13*10%13)%13
    
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
from bisect import bisect_left
S = input()

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

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] %= mod
  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] %= mod
  mul = mul*10 % 13  
print(dp[len(S)][5])

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):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

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

    for i in range(len_S):
        S_i = S[i]
        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[-1][5])

if __name__ == '__main__':
    resolve()

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    S = input()
    N = len(S)
    base = 1
    remainders = [0]*13
    remainders[0] = 1
    number = 0
    modulo = 10**9+7
    for i in range(N-1, -1, -1):
        new_remainders = [0]*13
        if S[i] == '?':
            for digit in range(10):
                for r in range(len(remainders)):
                    new_remainders[(base*digit+r)%13] += remainders[r]
        else:
            digit = int(S[i])
            for r in range(13):
                new_remainders[(base*digit+r)%13] = remainders[r]
        base = (base*10)%13
        remainders = [r%modulo for r in new_remainders]
    return remainders[5]


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