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

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

Solution (Python):



MAX = 10**9 + 7

def main():
  s = input().strip()
  p = 13
  dp = [[0]*p for _ in range(len(s))]
  remains = [[0]*p for _ in range(6)]
  for i in range(6):
    for j in range(p):
      remains[i][j] = ((10 ** i) * j) % p
    
  if s[-1] == '?':
    dp[0][:10] = [1] * 10
  else:
    dp[0][int(s[-1])] = 1
    
  for i, c in enumerate(s[::-1][1:], 1):
    if c == '?':
      for c in range(10):
        for j in range(p):
          dp[i][(remains[i%6][c] + j) % p] += (dp[i-1][j] % MAX) 
    else:
      c = int(c)
      for j in range(p):
        dp[i][(remains[i%6][c] + j) % p] += (dp[i-1][j] % MAX) 
        
  print(dp[-1][5] % MAX)
  
if __name__=='__main__':
  main()

Solution (Python):
s = input()
n = len(s)
dp = [[0]*13 for i in range(n+5)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
	    for j in range(13):
	    	    if s[i] != '?':
	    	    	    x = int(s[i])
	    	    	    ni = i+1
	    	    	    nj = (j*10+x)%13
	    	    	    dp[ni][nj] += dp[i][j]
	    	    	    dp[ni][nj]%= mod
	    	    	    continue
	    	    for d in range(10):
	    	    	    ni = i+1
	    	    	    nj = (j*10+d)%13
	    	    	    dp[ni][nj] += dp[i][j]
	    	    	    dp[ni][nj]%= mod
print(dp[n][5])

Solution (Python):
S=list(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):
    if S[i]=="?":
        temp=10**((N-i-1)%6)
        for j in range(10):
            for k in range(13):
                dp[i+1][(k+j*temp)%13]+=dp[i][k]
                dp[i+1][(k+j*temp)%13]%=10**9+7
                    
    else:
        temp=int(S[i])*10**((N-i-1)%6)
        for k in range(13):
            dp[i+1][(k+temp)%13]+=dp[i][k]
            dp[i+1][(k+temp)%13]%=10**9+7

print(dp[-1][5])

Solution (Python):
S = input()[::-1]
l = len(S)
MOD = 10**9+7
dp = [[0]*13 for i in range(l+1)]
dp[0][0] = 1
m = 1
for i in range(1,l+1):
  c = S[i-1]
  if c=='?':
    for j in range(10):
      n = m*j
      for h in range(13):
        dp[i][(h+n)%13] += dp[i-1][h]
        dp[i][(h+n)%13] %= MOD
  else:
    c = int(c)*m
    for j in range(13):
      dp[i][(j+c)%13] += dp[i-1][j]
      dp[i][(j+c)%13] %= MOD
  m *= 10
  m %= 13
print(dp[-1][5])

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q

    def length(self):
        return len(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    
    S = Scanner.string()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        c = S[i]
        if c == "?":
            for k in range(10):
                for j in range(13):
                    dp[i+1][(j * 10 + k) % 13] += dp[i][j]
                    dp[i+1][(j * 10 + k) % 13] %= MOD
        else:
            k = int(S[i])
            for j in range(13):
                dp[i+1][(j * 10 + k) % 13] += dp[i][j]
                dp[i+1][(j * 10 + k) % 13] %= MOD
    print(dp[N][5])
    return


if __name__ == "__main__":
    main()

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

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

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

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

Solution (Python):
S=input()
N=len(S)
count=0
hatenadata=[]
Sinfo=[]
for i in range(0,N):
    if S[i]=='?':
        Sinfo.append('0')
        count+=1
        hatenadata.append(i)
    else:
        Sinfo.append(S[i])
X=''.join(Sinfo)
first=int(X)%13

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-k*10**((digit-1)%6))%13] for k in range(0,10))%(10**9+7)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

def main():
    s = SI()
    n = len(s)
    dp = [[0] * 13 for _ in range(n + 1)]
    
    dp[0][0] = mint(1)
    e10 = 1
    for i, c in enumerate(s[::-1]):
        for m in range(13):
            pre = dp[i][m]
            if pre == 0: continue
            if c == "?":
                for d in range(10):
                    nm = (m + d * e10) % 13
                    dp[i + 1][nm] += pre
            else:
                nm = (m + int(c) * e10) % 13
                dp[i + 1][nm] += pre
        e10 = e10 * 10 % 13
    print(dp[n][5])

main()

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

S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    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[l][5]%MOD)

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

S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    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[l][5]%MOD)

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

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

for i in range(l):
    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[l][5]%MOD)

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

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

for i in range(l):
    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]%MOD)

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

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

for i in range(l):
    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]%MOD)

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

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

for i in range(l):
    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):
MOD = 10**9+7

S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1
l = len(S)
for i in range(l):
    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):
MOD = 10**9+7

S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1
l = len(S)
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):
MOD = 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] %= 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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

mod = 10**9+7
s = readline().rstrip().decode('utf-8')

dp = [0]*13 
dp[0] = 1
dig = 1 
for i in range(len(s)-1,-1,-1): 
    c = s[i]
    next_dp = [0]*13 
    if c == "?": 
        for d in range(10):
            for j in range(13):
                next_dp[(d*dig + j)%13] += dp[j]
                next_dp[(d*dig + j)%13] %= mod

    
    else:
        d = int(c)
        for j in range(13):
            next_dp[(d*dig + j)%13] += dp[j]
            next_dp[(d*dig + j)%13] %= mod


    dig *= 10
    dig %= 13
    dp = next_dp

print(dp[5]%mod)

Solution (Python):
S=input()
n=len(S)
l=[0]*13
l[0]=1
pr=10**9+7
for i in range(n):
    a=[0]*13
    p=pow(10,i,13)
    s=S[-i-1]
    if s=="?":
        for j in range(10):
            for k in range(13):
                a[(k+p*j)%13]+=l[k]%pr
    else:
        for k in range(13):
            a[(k+p*int(s))%13]+=l[k]%pr
    l=a
print(l[5]%pr)

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

Solution (Python):
import numpy as np
s = input()

A = []
for i in range(6):
    m = [-(j*10**i%13)%13 for j in range(10)]
    tmp = []
    for j in m:
        tmp.append([[1 if (k-l)%13==j else 0 for k in range(13)] for l in range(13)])
    tmp.append([[1 if (k-l)%13 in m else 0 for k in range(13)] for l in range(13)])
    A.append(tmp)
A = np.array(A)

dp = np.zeros(13, dtype=int)
dp[0] = 1
m = 1
for ind, i in enumerate(reversed(s)):
    i = int(i) if i!='?' else 10
    tmp = np.dot(A[ind%6, i, :, :], dp)
    dp = tmp%(10**9+7)
print(dp[5])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


S = sr()
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 x in range(13):
        for a in add:
            dp[(10*x + a) % 13] += prev[x]
    dp = [y%MOD for y in dp]

print(dp[5])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


S = sr()
MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1
for i, s in enumerate(S):
    if s != '?':
        x = int(s)
        for j in range(13):
            dp[i+1][(10*j+x)%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]
        for t in range(13):
            dp[i+1][t] %= MOD

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

Solution (Python):
import sys

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[use][(j*10+num)%13] += dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
        for j in range(13):
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5])

if __name__ == "__main__":
    main()

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

for i, s in enumerate(S[::-1], start=1):
    m = pow(10, i-1, 13)
    if s=="?":
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
    else:
        j = int(s)
        for k in range(13):
            dp[i][(j*m+k)%13] += dp[i-1][k]
    
    for j in range(13):
        dp[i][j] %= mod

print(dp[-1][5])

Solution (Python):
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 != '?':
        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
    else:
        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
    mul *= 10
    mul %= 13
print(dp[-1][5])

Solution (Python):
import sys


def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
from copy import deepcopy

def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans

S = input().strip()
N = len(S)
MOD = 10**9+7
dp = make_multi_list(0, [N+1, 13])
dp[0][0] = 1

for i in range(N):
    c = S[i]
    ni = i + 1
    for j in range(13):
        if c == '?':
            for k in range(10):
                nj = (j * 10 + k) % 13
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= MOD
        else:
            n = int(c)
            nj = (j * 10 + n) % 13
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= MOD

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

Solution (Python):















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

for i in range(0, l):
    if s[i] != '?':
        for k in range(13):
            dp[i+1][(k*10+int(s[i])) % 13] = dp[i][k]
    else:
        
        for k in range(13):
            temp[(k*10) % 13] = dp[i][k]
        
        excluded = temp[1] + temp[2] + temp[3]
        for k in range(13):
            dp[i+1][k] = (summ - excluded) % mod
            excluded -= temp[(k+1)%13]
            excluded += temp[(k+4)%13]

        summ *= 10
        summ %= mod

print(dp[l][5])

Solution (Python):















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

for i in range(0, l):
    if s[i] != '?':
        for k in range(13):
            dp[i+1][(k*10+int(s[i])) % 13] = dp[i][k]
    else:
        
        for k in range(13):
            temp[(k*10) % 13] = dp[i][k]
        
        excluded = temp[1] + temp[2] + temp[3]
        for k in range(13):
            dp[i+1][k] = (summ - excluded) % mod
            excluded -= temp[(k+1)%13]
            excluded += temp[(k+4)%13]

        summ *= 10
        summ %= mod

print(dp[l][5])

Solution (Python):
S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3

for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  
print(l[5])

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

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

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

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

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


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

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

ss = ins()
s = ss[::-1]
n = len(s)
a = [ [0]*13 for i in range(n) ]
r = 10
if s[0]=='?':
    for i in range(10):
        a[0][i] = 1
else:
    a[0][int(s[0])] = 1

for i in range(1,n):
    if s[i]=='?':
        ds = list(range(10))
    else:
        ds = [int(s[i])]
    for d in ds:
        for j in range(13):
            k = (j+d*r)%13
            
            a[i][k] = (a[i][k]+a[i-1][j])%R
    r = (r*10)%13

if DBG:
    for i in range(6):
        printn(i)
        print(a[i])
print(a[n-1][5])

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

Solution (Python):
s = list(input())
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    flag = 1 if s[i]=='?' else 0
    for a in range(10):
        if flag==1 or s[i]==str(a):
            for j in range(13): 
                dp[i+1][(j*10+a)%13] += dp[i][j] 
    for j in range(13):
        dp[i+1][j]%=10**9+7
print(dp[n][5])

Solution (Python):
s = list(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):
    flag = 1 if s[i]=='?' else 0 
    if flag==1:
        for a in range(10):
            for j in range(13): 
                dp[i+1][(j*10+a)%13] += dp[i][j] 
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=10**9+7
        
print(dp[n][5])

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

for i, s in enumerate(S[::-1], start=1):
    m = pow(10, i-1, 13)
    if s=="?":
        for j in range(10):
            for k in range(13):
                dp[i][(j*m+k)%13] += dp[i-1][k]
    else:
        j = int(s)
        for k in range(13):
            dp[i][(j*m+k)%13] += dp[i-1][k]
    
    for j in range(13):
        dp[i][j] %= mod

print(dp[-1][5])

Solution (Python):











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

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

for i, s in enumerate(S):
    mul = pow(10, i, 13)
    if s != '?':
        shift = (int(s) * mul) % 13
        for j in range(13):
            dp[i + 1][(j + shift) % 13] = dp[i][j]
    else:
        for candi in range(10):
            shift = (candi * mul) % 13
            for j in range(13):
                dp[i + 1][(j + shift) % 13] += dp[i][j] % MOD
print(dp[-1][5] % MOD)

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(1,N+1):
    c=S[i-1]
    if c=='?':
        for k in range(10):
            for n in range(13):
                nn=(n*10+k)%13
                dp[i][nn]+=dp[i-1][n]
                dp[i][nn]%=MOD
    else:
        for n in range(13):
            nn=(n*10+int(c))%13
            dp[i][nn]+=dp[i-1][n]
            dp[i][nn]%=MOD
print(dp[N][5])

Solution (Python):
def main():
    S = 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):
        if S[i] != '?':
            for j in range(13):
                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):
                for j in range(13):
                    dp[i+1][(j * 10 + k)%13] += dp[i][j]
                    dp[i+1][(j * 10 + k)%13] %= MOD

    print(dp[N][5])

    

if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
S=input()
dp=[[0 for _ in range(13)] for _ in range(len(S))]
MOD=10**9+7
if S[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[0])]+=1
for i in range(1, len(S)):
  cur_nums=[i for i in range(10)] if S[i]=='?' else [int(S[i])]
  for cur in cur_nums:
    for rem in range(13):
      dp[i][(10*rem+cur)%13]=(dp[i][(10*rem+cur)%13]+dp[i-1][rem])%MOD
print(dp[-1][5])

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    S = input()
    u = [1] + [0] * 12
    v = [0] * 13
    m = 1
    shift = 0
    for s in reversed(S):
        if s == '?':
            for j in range(13):
                v[j] = sum(u[(j - (m * i) % 13) % 13] for i in range(10)) % MOD
            u, v = v, u
        else:
            shift = (shift + m * int(s)) % 13
        m = m * 10 % 13
    return u[(5 - shift) % 13]

print(main())

Solution (Python):
def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    i = 0
    for v in reversed(S):
        if v == '?':
            k = 0
            for j in range(13):
                for k in range(13):
                    if l[i][j]:
                        kk = (j+k) % 13
                        n[kk] += c[k]
                        n[kk] %= mod
            c = n
            n = [0] * 13
        else:
            r += (l2[i][int(v)])
            r %= 13
        i += 1
        i %= 6
    r = (5 - r) % 13
    print(c[r] % mod)
main()

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



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

m = 1
for i in range(2, N + 1):
    m = m * 10 % 13
    for j in range(13):
        num = '?' if S[-i] == '?' else int(S[-i])
        for k in range(10):
            if num == '?' or k == num:
                d = k * m % 13
                dp[i][j] = (dp[i][j] + dp[i - 1][(13 + j - d) % 13]) % MOD

print(dp[N][5])

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