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

mul = 1

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

  mul = (mul * 10) % 13

print(dp[N][5])

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

Solution (Python):
S = input()
memo_ls = [[0 for j in range(13)] for i in range(len(S) + 1)]
memo_ls[0][0] = 1
for i in range(len(S)):
    for _ in range(10):
        if S[i] != "?" and int(S[i]) != _:
            continue
        for j in range(13):
            memo_ls[i + 1][(j * 10 + _) % 13] += memo_ls[i][j]
    for j in range(13):
        memo_ls[i + 1][j] %= 10**9+7

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

Solution (Python):
S=input()
A=[1,0,0,0,0,0,0,0,0,0,0,0,0]
a=10**9+7
for i in range(len(S)):
  B=A[:]
  if S[i]=="?":
    A[0]=(B[0]+B[9]+B[5]+B[1]+B[10]+B[6]+B[2]+B[11]+B[7]+B[3])%a
    A[1]=(B[4]+B[0]+B[9]+B[5]+B[1]+B[10]+B[6]+B[2]+B[11]+B[7])%a
    A[2]=(B[8]+B[4]+B[0]+B[9]+B[5]+B[1]+B[10]+B[6]+B[2]+B[11])%a
    A[3]=(B[12]+B[8]+B[4]+B[0]+B[9]+B[5]+B[1]+B[10]+B[6]+B[2])%a
    A[4]=(B[3]+B[12]+B[8]+B[4]+B[0]+B[9]+B[5]+B[1]+B[10]+B[6])%a
    A[5]=(B[7]+B[3]+B[12]+B[8]+B[4]+B[0]+B[9]+B[5]+B[1]+B[10])%a
    A[6]=(B[11]+B[7]+B[3]+B[12]+B[8]+B[4]+B[0]+B[9]+B[5]+B[1])%a
    A[7]=(B[2]+B[11]+B[7]+B[3]+B[12]+B[8]+B[4]+B[0]+B[9]+B[5])%a
    A[8]=(B[6]+B[2]+B[11]+B[7]+B[3]+B[12]+B[8]+B[4]+B[0]+B[9])%a
    A[9]=(B[10]+B[6]+B[2]+B[11]+B[7]+B[3]+B[12]+B[8]+B[4]+B[0])%a
    A[10]=(B[1]+B[10]+B[6]+B[2]+B[11]+B[7]+B[3]+B[12]+B[8]+B[4])%a
    A[11]=(B[5]+B[1]+B[10]+B[6]+B[2]+B[11]+B[7]+B[3]+B[12]+B[8])%a
    A[12]=(B[9]+B[5]+B[1]+B[10]+B[6]+B[2]+B[11]+B[7]+B[3]+B[12])%a
  else:
    s=int(S[i])
    for i in range(13):
      A[i]=B[(i*4+9*s)%13]
print(A[5])

Solution (Python):
S=input()
a=[0]*13
a[0]= 1

for c in S:
  dp=[0]*13
  for i in range(13):
    dp[(i*10)%13]=a[i]%(10**9+7)
  dp+=dp

  if c=='?':
    for i in range(13):
      a[i]=sum(dp[i+4:i+14])
  else:
    for i in range(13):
      a[i]=dp[i+13-int(c)]

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

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines




MOD=10**9+7






















def main():
	s=input().rstrip().decode('utf-8')
	n=len(s)
	
	dp=[[0]*13 for _ in range(n+1)]
	dp[0][0]=1
	
	for i in range(1,n+1):
		now=s[i-1]
		if now=="?":
			for j in range(13):
				for k in range(10):
					dp[i][(10*j+k)%13]+=dp[i-1][j]
		else:
			k=int(now)
			for j in range(13):
				dp[i][(10*j+k)%13]+=dp[i-1][j]
		
		for j in range(13):
			dp[i][j]%=MOD
	
	print(dp[n][5])
	
	
	
	
if __name__ == '__main__':
	main()

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    dp = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        ts = s[-i-1]
        if i == 0:
            if ts == "?":
                for j in range(10):
                    dp[i][j] += 1
            else:
                dp[i][int(ts)] += 1
        else:
            mult = pow(10, i, 13)
            if ts == "?":
                for j in range(13):
                    for k in range(10):
                        dp[i][(k * mult + j) % 13] += dp[i-1][j]
            else:
                num = int(ts)
                for j in range(13):
                    dp[i][(num * mult + j) % 13] += dp[i-1][j]
            for j in range(13):
                dp[i][j] %= mod
    print(dp[-1][5] % mod)


if __name__ == '__main__':
    solve()

Solution (Python):
s = input()

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

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

for i in reversed(range(len(s))):
    keta = len(s) - i - 1
    if s[i] == '?':
        for k in range(10):
            for j in range(13):
                amari = (j+k*(mul)) % 13
                
                dp[keta+1][amari] += dp[keta][j]
                dp[keta+1][amari] %= mod
    else:
        num = int(s[i])
        for j in range(13):
            amari = (j+(num*(mul))) % 13
            
            dp[keta+1][amari] += dp[keta][j]
            dp[keta+1][amari] %= mod
    mul = mul * 10 % 13
            
print(dp[len(s)][5])

Solution (Python):
s = input()
now = 1
dp0 = [[1] + [0] * 12]
dp = dp0 + [[0] * 13 for i in range(len(s))]
mod = 10 ** 9 + 7
for key,i in enumerate(s[::-1]):
  if i == "?":
    rem = 0
    rems = []
    for j in range(10):
      rems.append(rem)
      rem += now
      rem %= 13
    for index,j in enumerate(dp[key]):
      for rm in rems:
        dp[key+1][(index+rm)%13] += j % mod
  else:
    i = int(i)
    rm = now * i
    for index,j in enumerate(dp[key]):
      dp[key+1][(index+rm)%13] += j % mod
  now *= 10
  now %= 13
ans = dp[-1][5] % mod
print(ans)

Solution (Python):
from itertools import product

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for d in range(N):
    if S[d] == '?':
        for i, j in product(range(13), range(10)): 
            rem = ((10 * i) % 13 + j) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
    else:
        for i in range(13):
            rem = ((10 * i) % 13 + int(S[d])) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
print(dp[N][5])

Solution (Python):
S = list(reversed(input().strip()))

MOD = int(pow(10, 9) + 7)

powers = [1 for i in range(len(S))]
for i in range(1, len(S)):
    powers[i] = (10 * powers[i - 1]) % 13

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

for i, char in enumerate(S):
    def compute(num):
        if i == 0:
            
            dp[0][num] += 1
        else:
            for o in range(13):
                dp[i][(o + num * powers[i]) % 13] += dp[i - 1][o]
                dp[i][(o + num * powers[i]) % 13] %= MOD
                
    if char == "?":
        for j in range(10):
            compute(j)
    else:
        compute(int(char))

print(dp[-1][5])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
n = len(s)
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    
print(now[5])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    
print(now[5])

Solution (Python):
n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
modlist=[1,10,9,12,3,4]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=modlist[i%6]
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



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


print(dp[d][5])

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

DP[0] = 1
digit = 1
 

for i in range(len(S) - 1, -1, -1):
    nextDP = [0] * N
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP[:]
 
print(DP[5])
 
"""
??2??5

"""

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

Solution (Python):
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

MOD=10**9+7

S=read().rstrip().decode("utf-8")


R=[0]*13
R_buffer=[0]*13

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


for i in range(1,len(S)):
  
  if S[i]=="?":
    for j in range(13):
      for k in range(10):
        R_buffer[(j*10+k)%13]+=R[j]
  else:
    for j in range(13):
      R_buffer[(j*10+int(S[i]))%13]+=R[j]
  
  for j in range(13):
    R[j]=R_buffer[j]%MOD
    R_buffer[j]=0
  
  
print(R[5])

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

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
        for j in range(13):
            dp[i][j] %= MOD
print(dp[n - 1][5] % MOD)

Solution (Python):
S = input()
dp = [[0] * 13 for _ in range(2)]

mod = 10**9 + 7
dp[0][0] = 1
pow10 = 1
for i, s in enumerate(S[::-1]):
    now_idx, next_idx = i & 1, (i + 1) & 1
    dp[next_idx] = [0] * 13
    if s == '?':
        for j in range(13):
            for k in range(10):
                next_mod = (j + k * pow10) % 13
                dp[next_idx][next_mod] += dp[now_idx][j]
                dp[next_idx][next_mod] %= mod
    else:
        k = int(s)
        for j in range(13):
            next_mod = (j + k * pow10) % 13
            dp[next_idx][next_mod] += dp[now_idx][j]
            dp[next_idx][next_mod] %= mod
    pow10 = (pow10 * 10) % 13
print(dp[len(S) & 1][5])

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

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


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


if __name__ == '__main__':
    main()

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


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


if __name__ == '__main__':
    main()

Solution (Python):



sl = list(input())

dp = [[0 for i in range(13)] for i in range(len(sl)+1)]
dp[0][0] = 1
for idx, s in enumerate(sl):
    if s == "?":
        n = -1
    else:
        n = int(s)
    for j in range(13):
        for i in range(10):
            if n == -1 or n == i: 
                dp[idx+1][(10*j+i) % 13] += dp[idx][j]
                dp[idx+1][(10*j+i) % 13] %= 10**9 + 7

print(dp[-1][5] % (10**9 + 7))

Solution (Python):
s=input()
n=len(s)
dp=[list(0 for i in range(13)) for j in range(n)]
MOD=10**9+7
if s[0]=="?":
    for k in range(0,10):
        dp[0][k]+=1
else:
    dp[0][int(s[0])]+=1
for i in range(0,n-1):
    for k in range(13):
        if s[i+1]=="?":
            for j in range(10):
                ct=(k*10+j)%13
                dp[i+1][ct]+=dp[i][k]
                dp[i+1][ct]%=MOD
        elif s[i+1]!="?":
            tmp=(int(s[i+1])+k*10)%13
            dp[i+1][tmp]+=dp[i][k]
            dp[i+1][tmp]%=MOD
print(dp[n-1][5])

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

s = ''.join(list(reversed(s)))

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

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

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

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

Solution (Python):
s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]%mod
    else:
        for j in range(10):
            y.append((x*j)%mod)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]%mod
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)

Solution (Python):
s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]%mod
    else:
        for j in range(10):
            y.append(x*j)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]%mod
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)

Solution (Python):
import sys
input = sys.stdin.readline
S = list(input())[: -1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(len(S)):
  for j in range(13):
    for k in range(10):
      if S[i] == "?":
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
        dp[i + 1][(j * 10 + k) % 13] %= mod
    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
print(dp[-1][5])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    M=13
    S=input()
    n=len(S)
    dp=[0]*M
    dp[0]=1
    for i in range(n):
        ndp=[0]*M
        s=S[i]
        if(s=='?'):
            for j in range(10):
                for m in range(M):
                    ndp[(m*10+j)%M]+=dp[m]
                    ndp[(m*10+j)%M]%=MOD
        else:
            s=int(s)
            for m in range(M):
                ndp[(m*10+s)%M]+=dp[m]
        dp=ndp
    print(dp[5])
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    M=13
    S=input()[::-1]
    n=len(S)
    dp=[0]*M
    dp[0]=1
    for i in range(n):
        ndp=[0]*M
        s=S[i]
        d=pow(10,i,M) 
        if(s=='?'):
            for j in range(10):
                for m in range(M):
                    ndp[(m+j*d)%M]+=dp[m]
                    ndp[(m+j*d)%M]%=MOD
        else:
            s=int(s)
            for m in range(M):
                ndp[(m+s*d)%M]+=dp[m]
        dp=ndp
    print(dp[5])
resolve()

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):

import sys

MOD = 1000000007  

def solve(S: str):
    
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    list10 = range(0,10)
    list13 = range(0,13)
    keta =1
    for i in range(1,N+1):
        if S[N-i]=="?":
            for j in list10:
                addmod = j*keta%13
                for k in list13:
                    modmod = (k+addmod)%13
                    dp[i][modmod] += dp[i-1][k]%MOD
        else:
            addmod = (int(S[N-i])*keta)%13
            for k in list13:
                modmod = (k+addmod)%13
                dp[i][modmod] = dp[i-1][k]%MOD
        keta*=10
        keta%=13
    print(dp[N][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 copy
s = str(input())
N = len(s)
num = [0,0,0,0,0,0]
all = [76923 for i in range(13)]
all[0] = 76924

num1 = [1,1,1,1,1,1,1,1,1,1,0,0,0] 
num2 = [1,1,1,0,1,1,0,1,1,0,1,1,1] 
num3 = [1,1,1,1,0,1,1,1,0,1,1,1,0] 
num4 = [1,0,0,0,1,1,1,1,1,1,1,1,1] 
num5 = [1,1,1,1,0,1,1,0,1,1,0,1,1] 
num6 = [1,0,1,1,1,0,1,1,1,0,1,1,1] 

tgt = copy.deepcopy(all)

md = 0
for i in range(N):
    t = s[N-i-1]
    if t == '?':
        num[i%6] += 1
    else:
        md += ((10**(i%6)) * int(t))%13
allnum = min(num)
for i in range(6):
    num[i] -= allnum


if allnum == 0:
    tgt = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    tgt[md%13] = 1
else:
    for i in range(allnum-1):
        tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        for j in range(13):
            for k in range(13):
                tgt2[(j+k)%13] += all[j]*tgt[k]
        for j in range(13):
            tgt2[j] = tgt2[j]%(10**9+7)
        tgt = copy.deepcopy(tgt2)

for i in range(num[0]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num1[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[1]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num2[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[2]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num3[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[3]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num4[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[4]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num5[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[5]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num6[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)

if allnum == 0:
    print(tgt[5])
else:
    print(tgt[(5-md)%13])

Solution (Python):


def main():
    S = input().rstrip()
    ans, MOD = [0] * 13, 10 ** 9 + 7
    ans[0] = 1
    for c in S:
        dp = [0] * 13
        for i in range(13):
            dp[(i * 10) % 13] = ans[i] % MOD
        dp += dp
        if c == "?":
            for i in range(13):
                ans[i] = sum(dp[i + 4 : i + 14])
        else:
            x = int(c)
            for i in range(13):
                ans[i] = dp[i + 13 - x]
    print(ans[5] % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13







"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1


dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]


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

dp = [[0]*M for _ in range(N)]
for i in range(N):
    if i == 0:
        if S[-i - 1] == "?":
            for j in range(10):
                dp[i][j] += 1
        else:
            dp[i][int(S[-i - 1])] += 1
    else:
        mult = pow(10, i, 13)
        if S[-i - 1] == "?":
            for j in range(13):
                for k in range(10):
                    dp[i][(k * mult + j) % 13] += dp[i - 1][j]
        else:
            st = int(S[-i - 1])
            for j in range(13):
                dp[i][(st * mult + j) % 13] += dp[i - 1][j]
    for j in range(13):
        dp[i][j] = dp[i][j] % mod


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

Solution (Python):
import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()

Solution (Python):
S = input()
dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1
bit = 0
for c in S:
    if c == '?':
        for k in range(13):
            for s in range(10):
                dp[bit^1][(10*k+s) % 13] += dp[bit][k]
    else:
        for k in range(13):
            dp[bit^1][(10*k+int(c)) % 13] += dp[bit][k]
    
    for k in range(13):
        dp[bit^1][k] %= (10 ** 9 + 7)
        dp[bit][k] = 0
    bit ^= 1
print(dp[bit][5])

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])


if __name__ == '__main__':
    solve()

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

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

DIV = 10**9+7
s = input()
n = len(s)-1
ary = [ (int(s[i]) if s[i] != '?' else -1) for i in range(n) ]
dp = [ [0 for _ in range(13)] for _ in range(n+1) ]
dp[0][0] = 1
for i in range(n):
    for j in range(10):
        if ary[i] != -1 and ary[i] != 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] %= DIV
print(dp[n][5])

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