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:
def main():
    S = input()
    N = len(S)

    MOD = 10**9 + 7
    dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

    # 初期値
    if S[0] == "?":
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    # dpテーブル更新式
    for i in range(1, N):
        if S[i] == "?":
            for si in range(10):
                for j in range(13):
                    dp[i][(j*10 + si)%13] += dp[i-1][j]
                    dp[i][(j*10 + si)%13] %= MOD
        else:
            si = int(S[i])
            for j in range(13):
                dp[i][(j*10 + si)%13] += dp[i-1][j]
                dp[i][(j*10 + si)%13] %= MOD

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    N = len(S)

    MOD = 10**9 + 7
    dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

    # 初期値
    if S[0] == "?":
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    # dpテーブル更新式
    for i in range(1, N):
        if S[i] == "?":
            for si in range(10):
                for j in range(13):
                    dp[i][(j*10 + si)%13] += dp[i-1][j] % MOD
        else:
            si = int(S[i])
            for j in range(13):
                dp[i][(j*10 + si)%13] += dp[i-1][j] % MOD

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    N = len(S)

    MOD = 10**9 + 7
    dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

    # 初期値
    if S[0] == "?":
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1


    # dpテーブル更新式
    for i in range(1, N):
        si = S[i]
        if si == "?":
            for si_cand in range(10):
                for j in range(13):
                    dp[i][(j*10+si_cand)%13] += dp[i-1][j] % MOD
        else:
            for j in range(13):
                dp[i][(j*10+int(si))%13] += dp[i-1][j] % MOD

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

# 初期値
if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1


# dpテーブル更新式
for i in range(1, N):
    si = S[i]
    if si == "?":
        for si_cand in range(10):
            for j in range(13):
                dp[i][(j*10+si_cand)%13] += dp[i-1][j] % MOD
    else:
        for j in range(13):
            dp[i][(j*10+int(si))%13] += dp[i-1][j] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

DIVIDER = 13

mod_digit = [i % DIVIDER for i in range(10)]
mod_level = []
tmp = 1
for _ in range(len(S)):
    mod_level.append(tmp % DIVIDER)
    tmp *= 10
mod_level = mod_level[::-1]

memo = [[0] * DIVIDER for _ in range(len(S) + 1)]
# def dp(pos, mod_tmp):
for idx in range(len(S) + 1):
    # if pos < 0:
    #     if mod_tmp == 5:
    #         return 1
    #     else:
    #         return 0
    # elif memo[pos][mod_tmp] != None: return memo[pos][mod_tmp]
    if idx == 0:
        for mod_tmp in range(DIVIDER):
            if mod_tmp == 5:
                memo[0][mod_tmp] = 1
            else:
                memo[0][mod_tmp] = 0
    else:
        pos = idx - 1
        for mod_tmp in range(DIVIDER):
            ret = 0
            if S[pos] == '?':
                for d in range(10):
                    mod_nxt = (mod_tmp + mod_digit[d] * mod_level[pos]) % DIVIDER
                    ret += memo[idx - 1][mod_nxt]
            else:
                d = int(S[pos])
                mod_nxt = (mod_tmp + mod_digit[d] * mod_level[pos]) % DIVIDER
                ret += memo[idx - 1][mod_nxt]
            #
            memo[idx][mod_tmp] = ret % 1000000007

print(memo[len(S)][0])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

DIVIDER = 13

mod_digit = [i % DIVIDER for i in range(10)]
mod_level = []
tmp = 1
for _ in range(len(S)):
    mod_level.append(tmp % DIVIDER)
    tmp *= 10
mod_level = mod_level[::-1]

memo = [[0] * DIVIDER for _ in range(len(S) + 1)]
# def dp(pos, mod_tmp):
for idx in range(len(S) + 1):
    # if pos < 0:
    #     if mod_tmp == 5:
    #         return 1
    #     else:
    #         return 0
    # elif memo[pos][mod_tmp] != None: return memo[pos][mod_tmp]
    if idx == 0:
        for mod_tmp in range(DIVIDER):
            if mod_tmp == 5:
                memo[0][mod_tmp] = 1
            else:
                memo[0][mod_tmp] = 0
    else:
        pos = idx - 1
        for mod_tmp in range(DIVIDER):
            ret = 0
            if S[pos] == '?':
                for d in range(10):
                    mod_nxt = (mod_tmp + mod_digit[d] * mod_level[pos]) % DIVIDER
                    ret += memo[idx - 1][mod_nxt]
            else:
                d = int(S[pos])
                mod_nxt = (mod_tmp + mod_digit[d] * mod_level[pos]) % DIVIDER
                ret += memo[idx - 1][mod_nxt]
            #
            memo[idx][mod_tmp] = ret % 1000000007

print(memo[len(S)][0])

Submission status: Time Limit Exceeded

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

s = input().rstrip()
n = len(s)
s = s[::-1]

dp = [[0]*13 for _ in range(n + 1)] # dp[i][j] : i桁目まで見て13で割ってj余る個数
dp[0][0] = 1
for i in range(n):
    if s[i] != '?':
        s_ = int(s[i]) * 10**i
        for j in range(13):
            dp[i + 1][(j + s_) % 13] += dp[i][j]
            dp[i + 1][(j + s_) % 13] %= mod
    else:
        for j in range(13):
            for k in range(10):
                k *= 10**i
                dp[i + 1][(j + k) % 13] += dp[i][j]
                dp[i + 1][(j + k) % 13] %= mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
MOD = 10**9 + 7
M = 13

dp = [0] * M
dp[0] = 1

for s in S:
    newDp = [0] * M
    if s == '?':
        for s in range(10):
            for i in range(M):
                newDp[(i * 10 + s) % M] += dp[i]
    else:
        s = int(s)
        for i in range(M):
            newDp[(i * 10 + s) % M] = dp[i]
    for i in range(M):
        dp[i] = newDp[i] % MOD

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成
# #6716052を参考


def solve():
    S = [-1 if i == '?' else int(i) for i in input()[::-1]]
    dp = [0] * 13
    mod = 10 ** 9 + 7

    if S[0] == -1:
        dp = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[int(S[0])] = 1
    for i, s in enumerate(S[1:], 1):
        digit = pow(10, i, 13)
        next_dp = [0] * 13
        if s == -1:
            next_dp = [sum([dp[(13 - (digit * j) + nn) % 13] for j in range(10)]) for nn in range(13)]
        else:
            x = (digit * s) % 13
            next_dp = [dp[(13 - x + nn) % 13] for nn in range(13)]
        dp = [ndp % mod for ndp in next_dp]
    print(dp[5])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成
# #6716052を参考


def solve():
    S = [-1 if i == '?' else int(i) for i in input()[::-1]]
    dp = [0] * 13
    mod = 10 ** 9 + 7

    if S[0] == -1:
        dp = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[int(S[0])] = 1
    # print(S)
    for i, s in enumerate(S[1:], 1):
        # print(dp)
        digit = pow(10, i, 13)
        next_dp = [0] * 13
        if s == -1:
            for j in range(10):
                x = (digit * j) % 13
                for k in range(13):
                    next_dp[(x + k) % 13] += dp[k]
            pass
        else:
            x = (digit * s) % 13
            for k in range(13):
                next_dp[(x + k) % 13] += dp[k]
        dp = [ndp % mod for ndp in next_dp]
    # print(dp)
    print(dp[5])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成

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

    if S[-1] == '?':
        dp[0] = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[0][int(S[-1])] = 1

    for i, s in enumerate(S[::-1][1:], 1):
        digit = pow(10, i, 13)
        if s == '?':
            for j in range(10):
                x = (j * digit) % 13
                for k in range(13):
                    # print(s, i, j, k, x)
                    dp[i][(x + k) % 13] += dp[i - 1][k] % mod
                    # dp[i][(x + k) % 13] += pow(dp[i - 1][k], 1, mod)
        else:
            x = (int(s) * digit) % 13
            for k in range(13):
                # print(s, i, 'X', k, x)
                dp[i][(x + k) % 13] += dp[i - 1][k] % mod
                # dp[i][(x + k) % 13] += pow(dp[i - 1][k], 1, mod)
    print(dp[-1][5] % mod)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成

def solve():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S))]

    if S[-1] == '?':
        dp[0] = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[0][int(S[-1])] = 1

    for i, s in enumerate(S[::-1][1:], 1):
        digit = pow(10, i, 13)
        if s == '?':
            for j in range(10):
                x = (j * digit) % 13
                for k in range(13):
                    # print(s, i, j, k, x)
                    dp[i][(x + k) % 13] += dp[i - 1][k] % (10 ** 9 + 7)
        else:
            x = (int(s) * digit) % 13
            for k in range(13):
                # print(s, i, 'X', k, x)
                dp[i][(x + k) % 13] += dp[i - 1][k] % (10 ** 9 + 7)
    print(dp[-1][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    s = list(S)
    n = len(s)
    ans = [[0 for i in range(13)]for i in range(n)]
    if s[0] == '?':
        for i in range(10):
            ans[0][i] += 1
    else:
        ans[0][int(s[0])] += 1
    for i in range(n-1):
        if s[i+1] == '?':
            for j in range(10):
                for k in range(13):
                    ans[i+1][(10*k+j)%13] += ans[i][k]
        else:
            for k in range(13):
                ans[i+1][(10*k+int(s[i+1]))%13] += ans[i][k]
    print((ans[n-1][5])%(10**9+7))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int32)
    m13 = [(10**i) % 13 for i in range(12)]
    npa13 = np.array([i * np.arange(10) % 13 for i in range(13)], dtype=np.int8)
    memo[0] = 1
    for j, i in enumerate(s):
        memo2 = np.zeros(13, dtype=np.int32)
        a = m13[j % 12]
        if i == "?":
            for l in npa13[a]:
                memo2[l:] += memo[:13-l]
                memo2[:l] += memo[13-l:]
                memo2 = memo2 % mod
            memo = memo2 % mod
        else:
            l = a*int(i) % 13
            memo = np.append(memo[13-l:], memo[:13-l]) % mod
    print(int(memo[5]))


main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
def main():
    s = list(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] != '?':
            s[i] = int(s[i])
            for j in range(13):
                index = (j*10+s[i])%13
                dp[i+1][index] += dp[i][j]
        else:
            for j in range(10):
                for k in range(13):
                    index = (k*10+j)%13
                    dp[i+1][index] += dp[i][k]
        for j in range(13):
            dp[i+1][j] %= mod
    print(dp[n][5])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(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):
        if s[i] != '?':
            for j in range(13):
                index = (j*10+int(s[i]))%13
                dp[i+1][index] += dp[i][j]
        else:
            for j in range(10):
                for k in range(13):
                    index = (k*10+j)%13
                    dp[i+1][index] += dp[i][k]
        for j in range(13):
            dp[i+1][j] %= mod
    print(dp[n][5])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(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):
        if s[i] != '?':
            for j in range(13):
                index = (j*10+int(s[i]))%13
                dp[i+1][index] = (dp[i+1][index]+dp[i][j])%mod
        else:
            for j in range(10):
                for k in range(13):
                    index = (k*10+j)%13
                    dp[i+1][index] = (dp[i+1][index]+dp[i][k])%mod
    print(dp[n][5])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(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):
        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 j in range(10):
                for k in range(13):
                    dp[i+1][(k*10+j)%13] += dp[i][k]
                    dp[i+1][(k*10+j)%13] %= mod
    print(dp[n][5])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

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

Submission status: Time Limit Exceeded

Solution code:
# 17:02-17:26
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

F = [0]*N
for i in range(N):
    F[i] = pow(10,i,13)
D = [[[0]*13 for j in range(10)] for i in range(N)]
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            k = (F[i]*j)%13
            if i==0:
                D[i][j][k] = 1
            else:
                for l in range(10):
                    for m in range(13):
                        D[i][j][(m+k)%13] += D[i-1][l][m]
    else:
        j = int(S[i])
        k = (F[i]*j)%13
        if i==0:
            D[i][j][k] = 1
        else:
            for l in range(10):
                for m in range(13):
                    D[i][j][(m+k)%13] += D[i-1][l][m]
    if i%1000==0:
        for j in range(10):
            for k in range(13):
                D[i][j][k] = D[i][j][k]%MOD
ans = 0
for j in range(10):
    ans += D[N-1][j][5]
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
# 17:02-17:26
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

F = [0]*N
for i in range(N):
    F[i] = pow(10,i,13)
D = [[[0]*13 for j in range(10)] for i in range(N)]
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            k = (F[i]*j)%13
            if i==0:
                D[i][j][k] = 1
            else:
                for l in range(10):
                    for m in range(13):
                        D[i][j][(m+k)%13] += D[i-1][l][m]
    else:
        j = int(S[i])
        k = (F[i]*j)%13
        if i==0:
            D[i][j][k] = 1
        else:
            for l in range(10):
                for m in range(13):
                    D[i][j][(m+k)%13] += D[i-1][l][m]
ans = 0
for j in range(10):
    ans += D[N-1][j][5]
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
# 17:02-17:26
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

F = [0]*N
for i in range(N):
    F[i] = pow(10,i,13)
D = [[[0]*13 for j in range(10)] for i in range(N)]
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            k = (F[i]*j)%13
            if i==0:
                D[i][j][k] = 1
            else:
                for l in range(10):
                    for m in range(13):
                        D[i][j][(m+k)%13] += D[i-1][l][m]
    else:
        j = int(S[i])
        k = (F[i]*j)%13
        if i==0:
            D[i][j][k] = 1
        else:
            for l in range(10):
                for m in range(13):
                    D[i][j][(m+k)%13] += D[i-1][l][m]
    for j in range(10):
        for k in range(13):
            D[i][j][k] = D[i][j][k]%MOD
ans = 0
for j in range(10):
    ans += D[N-1][j][5]
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
# 17:02-17:26
MOD = pow(10,9)+7
S = input()[::-1]
N = len(S)

F = [0]*N
for i in range(N):
    F[i] = pow(10,i,13)
D = [[[0]*13 for j in range(10)] for i in range(N)]
for i in range(N):
    if S[i]=="?":
        for j in range(10):
            k = (F[i]*j)%13
            if i==0:
                D[i][j][k] = 1
            else:
                for l in range(10):
                    for m in range(13):
                        D[i][j][(m+k)%13] += D[i-1][l][m]%MOD
    else:
        j = int(S[i])
        k = (F[i]*j)%13
        if i==0:
            D[i][j][k] = 1
        else:
            for l in range(10):
                for m in range(13):
                    D[i][j][(m+k)%13] += D[i-1][l][m]%MOD
ans = 0
for j in range(10):
    ans += D[N-1][j][5]
print(ans%MOD)

Submission status: Time Limit Exceeded

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

def main():
    S = readline().rstrip()
    N = 13
    dp = [0] * 13  # dp[k]: 13で割った余りがkのパターン数
    dp[0] = 1
    
    mul = 1
    for i in range(len(S)-1, -1, -1):
        next_dp = [0] * N
        s = S[i]
        if s == '?':
            for k in range(10):
                for j in range(N):
                    next_dp[(k * mul + j) % N] += dp[j]
                    next_dp[(k * mul + j) % N] %= MOD
        else:
            k = int(s)
            for j in range(N):
                next_dp[(k * mul + j) % N] += dp[j]
                next_dp[(k * mul + j) % N] %= MOD
        mul *= 10
        mul %= N
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  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)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
mod = 10**9+7
P = 13

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

# 1桁目だけ事前計算
if S[N-1] == '?':
    tmp = [0 for _ in range(P)]
    for i in range(10):
        tmp[i % P] = 1
    dp[0] = tmp
else:
    dp[0][int(S[N-1]) % P] = 1

for i in range(1, N):
    k = N-i-1
    if S[k] == '?':
        base = 10**i % P
        rems = [0 for _ in range(P)]
        for j in range(10):
            rems[base * j % P] += 1
        for m in range(P):
            for n in range(P):
                a = dp[i-1][m] * rems[n] % mod
                dp[i][(m+n) % P] = (dp[i][(m+n) % P] + a) % mod
    else:
        r = 10**i * int(S[k]) % P
        for j in range(P):
            dp[i][(j+r)%P] = max(dp[i][(j+r)%P], dp[i-1][j])

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
m = [[0, 4, 8, 12, 3, 7, 11, 2, 6, 10],[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],[0, 10, 7, 4, 1, 11, 8, 5, 2, 12],[0, 9, 5, 1, 10, 6, 2, 11, 7, 3],[0, 12, 11, 10, 9, 8, 7, 6, 5, 4],[0, 3, 6, 9, 12, 2, 5, 8, 11, 1]]
S = list(input())
d = len(S)
dp = [[0] * 13 for _ in range(d)]
if S[0] == '?':
    for x in m[d%6]:
        dp[0][x] = 1
else:
    dp[0][m[d%6][int(S[0])]] = 1
for i in range(1,d):
    if S[i] == '?':
        for j in range(13):
            dp[i][j] = sum(dp[i-1][(13+j-x) % 13] for x in m[(d-i)%6]) % 1000000007
    else:
        for j in range(13):
            dp[i][j] = dp[i-1][(13+j-m[(d-i)%6][int(S[i])])%13]
print(dp[d-1][5])

Submission status: Time Limit Exceeded

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

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

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

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

Submission status: Time Limit Exceeded

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

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

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

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

Submission status: Time Limit Exceeded

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

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

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

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

Submission status: Time Limit Exceeded

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

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
INF = 10 ** 9 + 7
 
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1 # 後ろからi文字目までで、13で割った余りがjであるものの個数 0 → 3 → 43 → 543
# 実際にはjの部分に0 → 3 → 43 → 543が入るイメージだが、13で割って入れている
mul = 1 # 桁の部分を示す
 
for i in range(len(S)):
    x = S[-(i+1)] 
    if x == "?":
        for k in range(10): # ?の場合は、?の部分を0から9まで埋めた上で、余りが0から12のケースの個数を数える
            for j in range(13):
                dp[i+1][(mul * k + j) % 13] += dp[i][j] # 例えば43の時の個数は、3の時の個数に40の時の個数を加えたもの
                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])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from copy import copy 
def main():
    S = readline().decode().rstrip()    
    P = int(1e9)+7
    dp = [0 for _ in range(13)]
    dp[0] = 1
    mul = 1
    for s in reversed(S):
        nxDP = [0 for _ in range(13)]
        if s == '?':
            for i in range(10):
                for j in range(13):
                    nxr = (i*mul+j)%13
                    nxDP[nxr] += dp[j]
                    nxDP[nxr] %= P
        else:
            for j in range(13):
                nxr = ((ord(s)-ord('0'))*mul+j)%13
                nxDP[nxr] += dp[j]
                nxDP[nxr] %= P
        dp = copy(nxDP)
        mul *= 10
        mul %= 13

    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = input()
    L = len(s)
    dp = [[0] * 13 for _ in range(L + 1)]
    dp[0][0] = 1

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

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


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for n in range(N):
    s = S[n]
    if s!='?':
        s = int(s)*pow(10, (N-n-1), 13)%13
        for i in range(13):
            idx = (s+i)%13
            dp[n+1][idx] = dp[n][i]%mod
    else:
        for i in range(10):
            s = i*pow(10, (N-n-1), 13)%13
            for j in range(13):
                idx = (s+j)%13
                dp[n+1][idx] += dp[n][j]%mod

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
dp = [[0]*(13) for _ in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for n in range(N):
    s = S[n]
    if s!='?':
        s = int(s)*(10**(N-n-1))%13
        for i in range(13):
            idx = (s+i)%13
            dp[n+1][idx] = dp[n][i]%mod
    else:
        for i in range(10):
            s = i*(10**(N-n-1))%13
            for j in range(13):
                idx = (s+j)%13
                dp[n+1][idx] += dp[n][j]%mod

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