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
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1
"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1
for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
N = len(S)
M = 13

dp = [[0]*M for _ in range(N)]
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#print(c)
c.reverse()
#print(c)

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

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
sl = len(S)
dp = [[0] * 13 for _ in range(sl+1)]
dp[0][0] = 1

c = ''
for i in range(sl):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki] 

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

Submission status: Time Limit Exceeded

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

DIV = 10**9+7
s = input()
n = len(s)-1
ary = [ (int(s[i]) if s[i] != '?' else -1) for i in range(n) ]
dp = [ [0 for _ in range(13)] for _ in range(n+1) ]
dp[0][0] = 1
for i in range(n):
    for j in range(10):
        if ary[i] != -1 and ary[i] != j:
            continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]

    for j in range(13):
        dp[i+1][j] %= DIV
print(dp[n][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7

    dp = [[0] * 13 for _ in range(s)]
    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            for j in range(13):
                for k in range(10):
                    dp[i][table[j][k]] = (dp[i][table[j][k]] + dp[i - 1][j]) % mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [[0] * 13 for _ in range(s)]
table = [[0] * 10 for _ in range(13)]
for i in range(13):
    for j in range(10):
        table[i][j] = (i * 10 + j) % 13

if S[0] == -1:
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][S[0] % 13] += 1

for i in range(1, s):
    if S[i] == -1:
        for j in range(13):
            for k in range(10):
                dp[i][table[j][k]] = (dp[i][table[j][k]] + dp[i - 1][j]) % mod
    else:
        t = S[i]
        for j in range(13):
            dp[i][table[j][t]] = dp[i - 1][j]

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
s = len(S)
mod = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(s)]
table = [[0] * 10 for _ in range(13)]
for i in range(13):
    for j in range(10):
        table[i][j] = (i * 10 + j) % 13

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

for i in range(1, s):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][table[j][k]] = (dp[i][table[j][k]] + dp[i - 1][j]) % mod
    else:
        t = int(S[i])
        for j in range(13):
            dp[i][table[j][t]] = dp[i - 1][j]

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
s = len(S)
mod = 10 ** 9 + 7

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
s = len(S)
mod = 10 ** 9 + 7

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
S_len = len(S)

DP = [[0 for j in range(13)] for i in range(S_len + 1)]
DP[S_len][0] = 1

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if S[i] != "?":
        for j in range(13):
            DP[i][(j + int(S[i]) * num) % 13] += DP[i + 1][j] % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                DP[i][(j + k * num) % 13] += DP[i + 1][j] % 1000000007

print(DP[0][5] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len + 1)]
DP[S_len][0] = 1

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if S[i] != "?":
        for j in range(13):
            if DP[i + 1][j] != 0:
                DP[i][(j + int(S[i]) * num) % 13] += DP[i + 1][j] % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                DP[i][(j + k * num) % 13] += DP[i + 1][j] % 1000000007

print(DP[0][5] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len+1)]
DP[S_len][0] = 1

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if S[i] != "?":
        for j in range(13):
            if DP[i + 1][j] != 0:
                DP[i][(j + int(S[i]) * num) % 13] = (DP[i][(j + int(S[i]) * num) % 13] + DP[i + 1][j]) % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                if DP[i + 1][j] != 0:
                    DP[i][(j + k * num) % 13] = (DP[i][
                                                     (j + k * num) % 13] +
                                                 DP[i + 1][j]) % 1000000007

print(DP[0][5])

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len)]

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * num) % 13] = (DP[i][(j + int(S[i]) * num) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * num) % 13] = (DP[i][
                                                         (j + k * num) % 13] +
                                                     DP[i + 1][j]) % 1000000007

print(DP[0][5])

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len)]

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * num) % 13] = (DP[i][(j + int(S[i]) * (
                            10 ** (S_len - 1 - i))) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * num) % 13] = (DP[i][
                                                         (j + k * num) % 13] +
                                                     DP[i + 1][j]) % 1000000007

print(DP[0][5])

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
S_len = len(S)

DP = list = [[0] * 13 for i in range(S_len)]

for i in reversed(range(S_len)):

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * (10 ** (S_len - 1 - i))) % 13] = (DP[i][(j + int(S[i]) * (
                                10 ** (S_len - 1 - i))) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * (10 ** (S_len - 1 - i))) % 13] = (DP[i][
                                                                              (j + k * (10 ** (S_len - 1 - i))) % 13] +
                                                                          DP[i + 1][j]) % 1000000007

print(DP[0][5])

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

DP = list = [[0] * 13 for i in range(len(S))]

for i in reversed(range(len(S))):

    if i == len(S) - 1:
        if S[i] != "?":
            DP[i][int(S[i]) % 13] = 1
        else:
            for j in range(10):
                DP[i][j] = 1

    else:

        if S[i] != "?":
            for j in range(13):
                if DP[i + 1][j] != 0:
                    DP[i][(j + int(S[i]) * (10 ** (len(S) - 1 - i))) % 13] = (DP[i][(j + int(S[i]) * (
                                10 ** (len(S) - 1 - i))) % 13] + DP[i + 1][j]) % 1000000007
        else:
            for j in range(13):
                for k in range(10):
                    if DP[i + 1][j] != 0:
                        DP[i][(j + k * (10 ** (len(S) - 1 - i))) % 13] = (DP[i][
                                                                              (j + k * (10 ** (len(S) - 1 - i))) % 13] +
                                                                          DP[i + 1][j]) % 1000000007

print(DP[0][5])

Submission status: Time Limit Exceeded

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

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

#13で割ったあまりの判定方法
if s[0]!="?":
    modlist[0][int(s[0])]=1
elif s[0]=="?":
    for  i in range(10):
        modlist[0][i]=1
for i in range(1,n):
    if s[i]!="?":
        add=(int(s[i])*(10**(i)))%13
        for  j in range(13):
            modlist[i][j]+=modlist[i-1][(j-add)%13]
            modlist[i][j]%(10**9+7)
            

    else:
        for nums in range(10):
                add=nums*(10**i)%13
                for  j in range(13):
                    modlist[i][j]+=modlist[i-1][(j-add)%13]
                    modlist[i][j]=modlist[i][j]%(10**9+7)

print(modlist[-2][5])

Submission status: Time Limit Exceeded

Solution code:

def main():
    S = input()

    modN = 13
    modAns = 10**9+7
    dp_table = [[0 for idx in range(modN)] for _ in range(len(S)+1)]
    dp_table[0][0] = 1

    for digit in range(len(S)):
        if S[digit] == '?':
            for mod in range(modN):
                for add_num in range(10):
                    next_mod = (10*mod + add_num) % 13
                    dp_table[digit+1][next_mod] += dp_table[digit][mod]
        else:
            val = int(S[digit])
            for mod in range(modN):
                next_mod = (10*mod + val) % 13
                dp_table[digit+1][next_mod] += dp_table[digit][mod]
        for idx in range(modN):
            dp_table[digit+1][idx] %= modAns

    print(dp_table[-1][5])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade

# dp[i][j] Sの大きい位からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート
# 大きい位から順に始めないと13で割ったときの余りを求める計算量が大きくなる

S = input()

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

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

for i in range(1, len(S)):
    if S[i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for front_number in range(13):
                dp[i][(10 * front_number + q_number) % 13] += dp[i-1][front_number]
                dp[i][(10 * front_number + q_number) % 13] %= MOD
    else:
        for front_number in range(13):
            dp[i][(10 * front_number + int(S[i])) % 13] += dp[i-1][front_number]
            dp[i][(10 * front_number + int(S[i])) % 13] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

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

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

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            tmp = (q_number * 10**(i-1)) % 13
            for back_number in range(13):
                dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
                dp[i-1][(tmp + back_number) % 13] %= MOD
    else:
        for back_number in range(13):
            tmp = (int(S[-i]) * 10**(i-1)) % 13
            dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
            dp[i-1][(tmp + back_number) % 13] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

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

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

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            tmp = (q_number * 10**(i-1)) % 13
            for back_number in range(13):
                dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
                dp[i-1][(tmp + back_number) % 13] %= MOD
    else:
        for back_number in range(13):
            tmp = (int(S[-i]) * 10**(i-1)) % 13
            dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
            dp[i-1][(tmp + back_number) % 13] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

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

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

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for back_number in range(13):
                dp[i-1][(q_number * 10**(i-1) + back_number) % 13] += dp[i-2][back_number]
                dp[i-1][(q_number * 10**(i-1) + back_number) % 13] %= MOD
    else:
        for back_number in range(13):
            dp[i-1][(int(S[-i]) * 10**(i-1) + back_number) % 13] += dp[i-2][back_number]
            dp[i-1][(int(S[-i]) * 10**(i-1) + back_number) % 13] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

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

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

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for back_number in range(13):
                dp[i-1][(q_number * 10**(i-1) + back_number) % 13] += dp[i-2][back_number] % MOD
    else:
        for back_number in range(13):
            dp[i-1][(int(S[-i]) * 10**(i-1) + back_number) % 13] += dp[i-2][back_number] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

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

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

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for back_number in range(13):
                dp[i-1][(q_number * 10**(i-1) + back_number) % 13] += dp[i-2][back_number]
    else:
        for back_number in range(13):
            dp[i-1][(int(S[-i]) * 10**(i-1) + back_number) % 13] += dp[i-2][back_number]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    sts=input()
    n= len(sts)
    s = []
    for c in sts:
        s.append(c)

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

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

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    sts=input()
    n= len(sts)
    s = []
    for c in sts:
        s.append(c)

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

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

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    n= len(s)
    dp = [[0 for _ in range(13)]for _ in range(n)]

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

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
n= len(s)
dp = [[0 for _ in range(13)]for _ in range(n)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    is_first = True
    ls = [[0] * 13 for _ in range(len(s))]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if is_first:
            is_first = False
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                t = int(s[-i-1])
                ls[i][t] += 1
        else:
            mlt = pow(10, i)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        r = (j + mlt * k) % 13
                        ls[i][r] += ls[i-1][j]
                        ls[i][r] %= mod
            else:
                t = int(s[-i-1])
                for j in range(13):
                    r = (j + mlt * t) % 13
                    ls[i][r] += ls[i-1][j]
                    ls[i][r] %= mod
    print(ls[-1][5])


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    is_first = True
    ls = [[0] * 13 for _ in range(len(s))]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if is_first:
            is_first = False
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                t = int(s[-i-1])
                ls[i][t] += 1
        else:
            mlt = pow(10, i)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        r = (j + mlt * k) % 13
                        ls[i][r] += ls[i-1][j]
            else:
                t = int(s[-i-1])
                for j in range(13):
                    r = (j + mlt * t) % 13
                    ls[i][r] += ls[i-1][j]
            for j in range(13):
                ls[i][j] %= mod
    print(ls[-1][5])

if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
s = list(str(input()))
mod = 10**9 + 7
a = []
n = len(s)
for i in range(13):
  r = [0,0,0,0,0,0,0,0,0,0,0,0,0]
  for j in range(10):
    r[(i*10+j)%13] = 1
  a.append(copy.deepcopy(r))
a = np.array(a)
if s[0] == "?":
  start = np.array([1,1,1,1,1,1,1,1,1,1,0,0,0])
else:
  start = np.array([0,0,0,0,0,0,0,0,0,0,0,0,0])
  start[int(s[0])] = 1
for i in range(1,n):
  if s[i] == "?":
    start = np.dot(start,a)
    for j in range(13):
      start[j] = start[j] % mod
  else:
    nxt = [0]*13
    for j in range(13):
      nxt[(j*10+int(s[i]))%13] += int(start[j])
    start = copy.deepcopy(np.array(nxt))
print(start[5])

Submission status: Time Limit Exceeded

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

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

n = len(S)
for i in range(n):
    if i == 0:
        mod_array = [i for i in range(10)]
    else:
        mod_array = [i * 10 % 13 for i in mod_array]
    s = S[n-i-1]
    if s == '?':
        for a in mod_array:
            for k in range(13):
                dp[1][(k+a)%13] += dp[0][k]
    else:
        a = mod_array[int(s)]
        for k in range(13):
            dp[1][(k + a) % 13] += dp[0][k]
    for k in range(13):
        dp[0][k] = dp[1][k] % MOD
        dp[1][k] = 0

print(dp[0][5])

Submission status: Time Limit Exceeded

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

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

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

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
# ポイント
# 123 = 100 + 20 + 3 = 9 + 7 + 3 = 6 mod 13と桁ごとに分割して考えられる
# →　桁で区切って漸化式化し、テーブルを埋める

S = input()
N = 13
mod = 1000000007
mul = 1

# 1?2?3なら 0 -> 3 -> ?3 -> 2?3 -> ...と逐次的に計算していく
dp = [0 for i in range(N)]
dp[0] = 1 # dp[k] = 13で割ったあまりがkになるパターン数

for s in S[::-1]:
    next_dp = [0 for i in range(N)]
    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])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	else:
		num = int(ch)
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	
	for i in range(13):
		memo[idx+1][i] %= MOD

print(memo[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

modmemo = []
modmemo.append(1)
for idx in range(len(S)):
	modmemo.append((modmemo[len(modmemo) - 1] * 10) % 13)


for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			mod = (modmemo[len(S) - idx - 1] * num)%13
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i+mod)%13] += memo[idx][i] 
	else:
		num = int(ch)
		mod = (modmemo[len(S) - idx - 1] * num)%13
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i+mod)%13] += memo[idx][i] 
	
	for i in range(13):
		memo[idx+1][i] %= MOD

print(memo[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

modmemo = []
modmemo.append(1)
for idx in range(len(S)):
	modmemo.append((modmemo[len(modmemo) - 1] * 10) % 13)


for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			mod = (modmemo[len(S) - idx - 1] * num)%13
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i+mod)%13] += memo[idx][i] 
					memo[idx+1][(i+mod)%13] %= MOD
	else:
		num = int(ch)
		mod = (modmemo[len(S) - idx - 1] * num)%13
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i+mod)%13] += memo[idx][i] 
				memo[idx+1][(i+mod)%13] %= MOD

print(memo[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

def modpow(ori, po):
	res = 1;
	while(po > 0):
		if(po&1):
			res *= ori;
			res %= 13;
		ori *= ori;
		ori %= 13;
		po >>= 1;
	return res;


S = input()
memo = [[0] * 13 for i in range(len(S)+1)]

memo[0][0] = 1
for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			mod = (modpow(10, (len(S) - idx - 1)) * num)%13
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i+mod)%13] += memo[idx][i] 
					memo[idx+1][(i+mod)%13] %= MOD
	else:
		num = int(ch)
		mod = (modpow(10, (len(S) - idx - 1)) * num)%13
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i+mod)%13] += memo[idx][i] 
				memo[idx+1][(i+mod)%13] %= MOD

print(memo[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

S = input()
memo = [[0] * 13 for i in range(len(S)+1)]

memo[0][0] = 1
for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			mod = ((10**(len(S) - idx - 1)) * num)%13
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i+mod)%13] += memo[idx][i] 
					memo[idx+1][(i+mod)%13] %= MOD
	else:
		num = int(ch)
		mod = ((10**(len(S) - idx - 1)) * num)%13
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i+mod)%13] += memo[idx][i] 
				memo[idx+1][(i+mod)%13] %= MOD

print(memo[len(S)][5]%MOD)