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



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MAX_C = 10**9 + 7


s = input()
s = s[:len(s)-1]
n = len(s)
s = [-1 if s[i] == '?' else int(s[i]) for i in range(n)]

mat = [[0]*13 for _ in range(n)]
list10 = list(range(10))
list13 = list(range(13))
mods = [i % 13 for i in range(130)]
mul = [[0]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        mul[i][j] = 10*i + j

if s[0] == -1:
    for i in list10:
        mat[0][i] = 1
else:
    mat[0][s[0]] = 1

for col_i in range(1, n):
    n_w = s[col_i]
    if n_w == -1:
        for n_v in list10:
            for p_row_i in list13:
                #v = 10*p_row_i + n_v
                v = mul[p_row_i][n_v]
                mat[col_i][mods[v]] += mat[col_i-1][p_row_i]

    else:
        for p_row_i in list13:
            #v = 10*p_row_i + s[col_i]
            v = mul[p_row_i][n_w]
            mat[col_i][mods[v]] += mat[col_i-1][p_row_i]

    for i in list13:
        mat[col_i][i] %= MAX_C

print(mat[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MAX_C = 10**9 + 7


s = input()
s = s[:len(s)-1]
n = len(s)
s = [-1 if s[i] == '?' else int(s[i]) for i in range(n)]

mat = [[0]*13 for _ in range(n)]
list10 = list(range(10))
list13 = list(range(13))
mods = [i % 13 for i in range(130)]

if s[0] == -1:
    for i in list10:
        mat[0][i] = 1
else:
    mat[0][s[0]] = 1

for col_i in range(1, n):
    if s[col_i] == -1:
        for n_v in list10:
            for p_row_i in list13:
                v = 10*p_row_i + n_v
                mat[col_i][mods[v]] += mat[col_i-1][p_row_i]

    else:
        for p_row_i in list13:
            v = 10*p_row_i + s[col_i]
            mat[col_i][mods[v]] += mat[col_i-1][p_row_i]

    for i in list13:
        mat[col_i][i] %= MAX_C

print(mat[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
MAX_C = 10**9 + 7


s = input()
s = s[:len(s)-1]
n = len(s)
s = [-1 if s[i] == '?' else int(s[i]) for i in range(n)]

mat = [[0]*13 for _ in range(n)]
list10 = list(range(10))
list13 = list(range(13))
mods = [i % 13 for i in range(130)]

if s[0] == -1:
    for i in list10:
        mat[0][i] = 1
else:
    mat[0][s[0]] = 1

for col_i in range(1, n):
    for p_row_i in list13:
        if mat[col_i-1][p_row_i] != 0:
            p_v = 10 * p_row_i

            if s[col_i] == -1:
                for n_v in list10:
                    v = p_v + n_v
                    mat[col_i][mods[v]] += mat[col_i-1][p_row_i]

            else:
                v = p_v + s[col_i]
                mat[col_i][mods[v]] += mat[col_i-1][p_row_i]

    for i in list13:
        mat[col_i][i] %= MAX_C

print(mat[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
MAX_C = 10**9 + 7


s = input()
s = s[:len(s)-1]
n = len(s)
s = [-1 if s[i] == '?' else int(s[i]) for i in range(n)]

mat = [[0]*13 for _ in range(n)]
list10 = list(range(10))
list13 = list(range(13))

if s[0] == -1:
    for i in list10:
        mat[0][i] = 1
else:
    mat[0][s[0]] = 1

for col_i in range(1, n):
    for p_row_i in list13:
        if mat[col_i-1][p_row_i] != 0:
            p_v = p_row_i

            if s[col_i] == -1:
                for n_v in list10:
                    v = 10 * p_v + n_v
                    mat[col_i][v % 13] += mat[col_i-1][p_row_i]

            else:
                v = 10 * p_v + s[col_i]
                mat[col_i][v % 13] += mat[col_i-1][p_row_i]

    for i in list13:
        mat[col_i][i] %= MAX_C

print(mat[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
MAX_C = 10**9 + 7

mat = [[0]*13 for _ in range(100000)]
list10 = list(range(10))
list13 = list(range(13))

s = input()
s = s[:len(s)-1]
s = [-1 if s[i] == '?' else int(s[i]) for i in range(len(s))]

if s[0] == -1:
    for i in list10:
        mat[0][i] = 1
else:
    mat[0][s[0]] = 1

for col_i in range(1, len(s)):
    for p_row_i in list13:
        if mat[col_i-1][p_row_i] != 0:
            p_v = p_row_i

            if s[col_i] == -1:
                for n_v in list10:
                    v = 10 * p_v + n_v
                    mat[col_i][v % 13] += mat[col_i-1][p_row_i]

            else:
                v = 10 * p_v + s[col_i]
                mat[col_i][v % 13] += mat[col_i-1][p_row_i]

    for i in list13:
        mat[col_i][i] %= MAX_C

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
ns = len(s)
base = 1000000000 + 7
dp = [[0 for i in range(13)] for j in range(ns + 1)]
dp[0][0] = 1
for i in range(ns):
    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and j != c:
            continue
        for k in range(13):
            dp[i + 1][(10 * k + j) % 13] += dp[i][k]
    for j in range(10):
        dp[i + 1][j] %= base
print(dp[ns][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
ns = len(s)
base = 1000000000 + 7
dp = [[0 for i in range(13)] for j in range(ns + 1)]
dp[0][0] = 1
for i in range(ns):
    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and j != c:
            continue
        for k in range(13):
            dp[i + 1][(10 * k + j) % 13] += dp[i][k]
    for j in range(10):
        dp[i + 1][j] = dp[i + 1][j] % base
print(dp[ns][5])

Submission status: Time Limit Exceeded

Solution code:

MOD = 10**9 + 7

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

dp[0][0] = 1

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

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

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

print(dp[L][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
MAX_C = 10**9 + 7

mat = [[0]*13 for _ in range(100000)]

s = input()
s = s[:len(s)-1]
s = [-1 if s[i] == '?' else int(s[i]) for i in range(len(s))]

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

for col_i in range(1, len(s)):
    for p_row_i in range(13):
        if mat[col_i-1][p_row_i] != 0:
            p_v = p_row_i

            if s[col_i] == -1:
                for n_v in range(10):
                    v = 10 * p_v + n_v
                    mat[col_i][v % 13] += mat[col_i-1][p_row_i]

            else:
                v = 10 * p_v + s[col_i]
                mat[col_i][v % 13] += mat[col_i-1][p_row_i]

    for i in range(13):
        mat[col_i][i] %= MAX_C

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
MAX_C = 10**9 + 7

mat = [[0]*13 for _ in range(100000)]

s = input()
s = s[:len(s)-1]
s = [-1 if s[i] == '?' else int(s[i]) for i in range(len(s))]

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

for col_i in range(1, len(s)):
    for p_row_i in range(13):
        if mat[col_i-1][p_row_i] != 0:
            if mat[col_i-1][p_row_i] != 0:
                p_v = p_row_i
            else:
                p_v = 0

            if s[col_i] == -1:
                for n_v in range(10):
                    v = 10 * p_v + n_v
                    mat[col_i][v % 13] += mat[col_i-1][p_row_i]

            else:
                v = 10 * p_v + s[col_i]
                mat[col_i][v % 13] += mat[col_i-1][p_row_i]

    for i in range(13):
        mat[col_i][i] %= MAX_C

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math

mat = [[0]*13 for _ in range(100000)]

s = input()
s = s[:len(s)-1]

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

for col_i in range(1, len(s)):
    for p_row_i in range(13):
        if mat[col_i-1][p_row_i] != 0:
            if mat[col_i-1][p_row_i] != 0:
                p_v = p_row_i
            else:
                p_v = 0

            if s[col_i] == '?':
                for n_v in range(10):
                    v = 10 * p_v + n_v
                    mat[col_i][v % 13] += mat[col_i-1][p_row_i]

            else:
                v = 10 * p_v + int(s[col_i])
                mat[col_i][v % 13] += mat[col_i-1][p_row_i]

    for i in range(13):
        mat[col_i][i] %= (10**9 + 7)

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

Submission status: Time Limit Exceeded

Solution code:

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

if len(S) % 3 == 1:
    S = '00' + S
elif len(S) % 3 == 2:
    S = '0' + S

L = (len(S) // 3)
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        s = S[k*3:k*3+3]
        d1 = [i for i in range(10)] if s[0] == '?' else [int(s[0])]
        d2 = [i for i in range(10)] if s[1] == '?' else [int(s[1])]
        d3 = [i for i in range(10)] if s[2] == '?' else [int(s[2])]

        for i1 in d1:
            for i2 in d2:
                for i3 in d3:
                    num = 100 * i1 + 10 * i2 + i3
                    dp[k + 1][(13 + num - m) % 13] += dp[k][m]

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

print(dp[L][5])

Submission status: Time Limit Exceeded

Solution code:

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

if len(S) % 3 == 1:
    S = '00' + S
elif len(S) % 3 == 2:
    S = '0' + S

L = (len(S) // 3)
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        s = S[k*3:k*3+3]
        d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
        d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
        d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]

        for i1 in d1:
            for i2 in d2:
                for i3 in d3:
                    num = int(i1 + i2 + i3)
                    dp[k + 1][(13 + num - m) % 13] += dp[k][m]

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

print(dp[L][5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
memo = None


def rec(S, k, total):
    if k == len(S)//3:
        # print(total)
        fixed_total = total + 5 if k % 2 == 0 else total - 5
        # fixed_total = abs(total) + 5
        memo[k][total % 13] = int((fixed_total) % 13 == 0)
        return int((fixed_total) % 13 == 0)

    if memo[k][total % 13] is not None:
        return memo[k][total % 13]

    s = S[k*3:k*3+3]
    d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
    d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
    d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]
    ret = 0

    for i1 in d1:
        for i2 in d2:
            for i3 in d3:
                num = int(i1 + i2 + i3)
                if k % 2 == 0:
                    ret += rec(S, k+1, total + num)
                else:
                    ret += rec(S, k+1, total - num)

    memo[k][total % 13] = ret
    return ret

S = input()

# if len(S) % 3 == 1:
#     S = '00' + S
# elif len(S) % 3 == 2:
#     S = '0' + S

# L = (len(S) // 3)
# dp = [[0 for i in range(14)] for j in range(L + 1)]
# # print(rec(S, 0, 0) % MOD)
# # print(memo)

# dp[0][0] = 1

# for k in range(L):
#     for m in range(13):
#         s = S[k*3:k*3+3]
#         d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
#         d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
#         d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]

#         for i1 in d1:
#             for i2 in d2:
#                 for i3 in d3:
#                     num = int(i1 + i2 + i3)
#                     dp[k + 1][(13 + num - m) % 13] += dp[k][m]

#         for i in range(13):
#             dp[k][m] %= MOD

# print(dp[L][5] % MOD)

L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
memo = None


def rec(S, k, total):
    if k == len(S)//3:
        # print(total)
        fixed_total = total + 5 if k % 2 == 0 else total - 5
        # fixed_total = abs(total) + 5
        memo[k][total % 13] = int((fixed_total) % 13 == 0)
        return int((fixed_total) % 13 == 0)

    if memo[k][total % 13] is not None:
        return memo[k][total % 13]

    s = S[k*3:k*3+3]
    d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
    d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
    d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]
    ret = 0

    for i1 in d1:
        for i2 in d2:
            for i3 in d3:
                num = int(i1 + i2 + i3)
                if k % 2 == 0:
                    ret += rec(S, k+1, total + num)
                else:
                    ret += rec(S, k+1, total - num)

    memo[k][total % 13] = ret
    return ret

S = input()

if len(S) % 3 == 1:
    S = '00' + S
elif len(S) % 3 == 2:
    S = '0' + S

L = (len(S) // 3)
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        s = S[k*3:k*3+3]
        d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
        d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
        d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]

        for i1 in d1:
            for i2 in d2:
                for i3 in d3:
                    num = int(i1 + i2 + i3)
                    dp[k + 1][(13 + num - m) % 13] += dp[k][m]

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

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

# L = len(S)
# memo = [[0 for i in range(14)] for j in range(L + 1)]
# dp = [[0 for i in range(14)] for j in range(L + 1)]
# # print(rec(S, 0, 0) % MOD)
# # print(memo)

# dp[0][0] = 1

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

# print(dp[L][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ns = len(s)
base = 1000000000 + 7
dp = [[0 for i in range(13)] for j in range(ns + 1)]
if s[0] != '?':
	dp[1] = [(1 if i == int(s[0]) else 0) for i in range(13)]
else:
	dp[1] = [(1 if i < 10 else 0) for i in range(13)]
for i in range(1, ns):
	for j in range(13):
		if s[i] != '?':
			for k in range(13):
				dp[i + 1][j] += dp[i][k] if (k * 10 + int(s[i])) % 13 == j else 0
		else:
			for k in range(13):
				for m in range(10):
					dp[i + 1][j] += dp[i][k] if (k * 10 + m) % 13 == j else 0
		dp[i + 1][j] = dp[i + 1][j] % base
print(dp[ns][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement
from sys import stdin,setrecursionlimit
#from copy import deepcopy

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = list(input())[::-1]

dp = np.array([1] + [0]*12)

nd = len(S)
for i in range(nd):
  if S[i] != '?':
    slide = (int(S[i])*(10**i)) % 13
    dp = np.r_[dp[-slide:], dp[:-slide]]
  
  else:
    new_dp = dp.copy()
    for j in range(1, 10):
      slide = int(j*(10**i)) % 13
      new_dp += np.r_[dp[-slide:], dp[:-slide]]
    
    dp = new_dp % (10**9 + 7)

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
mod = 0
for i in range(n):
    dp_old = dp.copy()
    #print(dp_old)
    dp = [0 for _ in range(13)]
    weight = 10**i % 13
    if s[n - i - 1] == '?':
        for j in range(13):
            for k in range(10):
                dp[(j + k * weight) % 13] += dp_old[j] % 1000000007
                
    else:
        for j in range(13):
            dp[(j + int(s[n - i - 1]) * weight) % 13] += dp_old[j] % 1000000007
print(dp[5] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)


# def debug(var, name="hoge"):
#     print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
#     return


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

    for i in range(L):
        memo = [0 for _ in range(13)]
        # 数字なら以前までの余りにたす
        if S[i].isnumeric():
            for m in range(13):
                cur = (10*m+int(S[i]))%13
                memo[cur] += memo_prev[m]
        # ?なら1~10の余りのケース全てをためす
        else:
            for n in range(10):
                for m in range(13):
                    cur = (10*m+n)%13
                    memo[cur] += memo_prev[m]
                    memo[cur] %= MOD
        memo_prev = memo.copy()
    print(memo[5])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
MOD = 10**9 + 7

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    S = list(input()[:-1])[::-1]
    # print(S)
    L = len(S)
    modsum = 0
    # はじめ長さ、つぎは余り
    memo = [[ 0 for __ in range(13)] for _ in range(L)]

    # 0だけ別に
    if S[0].isnumeric():
        memo[0][int(S[0])] = 1
    else:
        for n in range(10):
            memo[0][n] = 1
    p = 1
    for i in range(1, L):
        # 数字なら以前までの余りにたす
        p *= 10
        if S[i].isnumeric():
            mod = (int(S[i])*p)%13
            for m in range(13):
                # 0でない余りを次に持ち越し
                if memo[max(0,i-1)][m] > 0:
                    memo[i][(m+mod)%13] += memo[max(0,i-1)][m]
        # ?なら1~10の余りのケース全てをためす
        else:
            for n in range(10):
                mod = (n*p)%13
                for m in range(13):
                    # その前の数があるなら足す
                    if memo[max(0,i-1)][m] > 0:
                        cur = (m+mod)%13
                        memo[i][cur] += memo[max(0,i-1)][m]
                        memo[i][cur] %= MOD
    print(memo[L-1][5])
    # print(memo)








if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
MOD = 10**9 + 7

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    S = list(input()[:-1])[::-1]
    # print(S)
    L = len(S)
    modsum = 0
    # はじめ長さ、つぎは余り
    memo = [[ 0 for __ in range(13)] for _ in range(L)]

    # 0だけ別に
    if S[0].isnumeric():
        memo[0][int(S[0])%13] = 1
    else:
        for n in range(10):
            memo[0][n] = 1

    for i in range(1, L):
        # 数字なら以前までの余りにたす
        if S[i].isnumeric():
            mod = (int(S[i])*pow(10,i))%13
            for m in range(13):
                # 0でない余りを次に持ち越し
                if memo[max(0,i-1)][m] > 0:
                    memo[i][(m+mod)%13] = memo[max(0,i-1)][m]
        # ?なら1~10の余りのケース全てをためす
        else:
            for n in range(10):
                mod = (n*pow(10,i))%13
                for m in range(13):
                    # その前の数があるなら足す
                    if memo[max(0,i-1)][m] > 0:
                        cur = (m+mod)%13
                        memo[i][cur] += memo[max(0,i-1)][m]
                        memo[i][cur] %= MOD
    print(memo[L-1][5])
    # print(memo)








if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
MOD = 10**9 + 7

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    S = list(input()[::-1][1:])
    L = len(S)
    modsum = 0
    # はじめ長さ、つぎは余り
    memo = [[ 0 for __ in range(13)] for _ in range(L)]

    # 0だけ別に
    if S[0].isnumeric():
        memo[0][int(S[0])%13] = 1
    else:
        for n in range(10):
            memo[0][n] = 1

    for i in range(1, L):
        # 数字なら以前までの余りにたす
        if S[i].isnumeric():
            mod = (int(S[i])*pow(10,i))%13
            for m in range(13):
                # 0でない余りを次に持ち越し
                if memo[max(0,i-1)][m] > 0:
                    memo[i][(m+mod)%13] = memo[max(0,i-1)][m]
        # ?なら1~10の余りのケース全てインクリメント
        else:
            for n in range(10):
                mod = (n*pow(10,i))%13
                for m in range(13):
                    # その前の数があるなら足す
                    if memo[max(0,i-1)][m] > 0:
                        cur = (m+mod)%13
                        memo[i][cur] += memo[max(0,i-1)][m]
                        memo[i][cur] %= MOD
    print(memo[L-1][5])
    # print(memo)








if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()[::-1]

dp = np.zeros((len(s),13), dtype="uint64")

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

L1 = range(1, len(s))

for i in L1:
    if s[i] == "?":
        mod = pow(10, i, 13)
        mod_list = ((mod*i)%13 for i in range(10))
        for j in mod_list:
            dp[i, :] += np.roll(dp[i - 1, :], j)
        dp[i, :] %= (10**9+7)
    else:
        mod = (pow(10, i, 13)*int(s[i]))%13
        dp[i, :] += np.roll(dp[i - 1, :], mod)

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

Submission status: Time Limit Exceeded

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

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

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

L1 = range(1, len(s))
L2 = range(13)

for i in L1:
    if s[i] == "?":
        mod = pow(10, i, 13)
        mod_list = ((mod*i)%13for i in range(10))
        for j in mod_list:
            for k in L2:
                l = (k+j)%13
                dp[i][l] += dp[i-1][k]
    else:
        mod = (pow(10, i, 13)*int(s[i]))%13
        for k in L2:
            l = (k+mod)%13
            dp[i][l] += dp[i-1][k]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp1 = [0] * 13
dp2 = [0] * 13
dp1[0] = 1
n = len(s)

for i in range(n):
    if s[n-i-1] != "?":
        a = (int(s[n-i-1]) * 10 ** i) % 13
        for j in range(13):
            dp2[j] = dp1[j-a]
    else:
        for k in range(10):
            a = (k * 10 ** i) % 13
            for j in range(13):
                dp2[j] += dp1[j-a]
    dp1 = dp2
    dp2 = [0] * 13

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

DIV = 13
MOD = 10**9+7
dp = [[0] * DIV for x in range(len(s))]

tmp = s[-1]
if tmp == '?':
    for j in range(10):
        dp[0][j%DIV] += 1
else:
    dp[0][int(tmp)%DIV] += 1

for i in range(1, len(s)):
    tmp = s[len(s)-i-1]
    ten = (10**i)%DIV
    if tmp == '?':
        for j in range(10):
            for k in range(DIV):
                dp[i][(j*ten+k)%DIV] += dp[i-1][k]
    else:
        for k in range(DIV):
            dp[i][(int(tmp)*ten+k)%DIV] += dp[i-1][k]

    for k in range(DIV):
        dp[-1][k] %= MOD

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

DIV = 13
MOD = 10**9+7
dp = [[0 for x in range(DIV)] for y in range(len(s))]

tmp = s[-1]
if tmp == '?':
    for j in range(10):
        dp[0][j%DIV] += 1
else:
    dp[0][int(tmp)%DIV] += 1

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

    for k in range(DIV):
        dp[-1][k] %= MOD

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

DIV = 13
MOD = 10**9+7
dp = [[0 for x in range(DIV)] for y in range(len(s))]

tmp = s[-1]
if tmp == '?':
    for j in range(10):
        dp[0][j%DIV] += 1
else:
    dp[0][int(tmp)%DIV] += 1

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

Submission status: Time Limit Exceeded

Solution code:

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

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

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

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:

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


for i in range(n):
    if s[i]=="?":
        si = range(10)
    else:
        si = [int(s[i])]
    
    for sn in si:
        for j in range(13):
            dp[i+1][(10*j+sn)%13]+=dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
a = list(input())
 
b = [[0 for i in range(13)] for i in range(len(a) + 1)]
b[0][0] = 1
 
check = 0
for i in range(len(a)):
    if a[i] == '?':
        check = -1
    else:
        check = int(a[i])
 
    for j in range(10):
        if check == -1 or check == j:
            for k in range(13):
                b[i + 1][(k * 10 + j) % 13] += b[i][k]

print(b[len(a)][5] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
a = list(input())

b = [[0 for i in range(13)] for i in range(len(a) + 1)]
b[0][0] = 1

check = 0
for i in range(len(a)):
    if a[i] == '?':
        check = -1
    else:
        check = int(a[i])

    for j in range(10):
        if check == -1 or check == j:
            for k in range(13):
                b[i + 1][(k * 10 + j) % 13] += b[i][k]
        
    for l in range(13):
        b[i + 1][l] %= 1000000007

print(b[len(a)][5])