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 numpy as np
s=list(input())
n=len(s)
dp=np.zeros((n+1,13),np.int64)
mod=pow(10,9)+7
if s[-1]=='?':
  dp[1][:10]=1
else:
  dp[1][int(s[-1])]=1
for i in range(2,n+1):
  if s[-i]=='?':
    for j in range(10):
      if (j*pow(10,i-1))%13==0:
        dp[i]+=dp[i-1]
      else:
        dp[i][(j*pow(10,i-1))%13:]+=dp[i-1][:-(j*pow(10,i-1))%13]
        dp[i][:(j*pow(10,i-1))%13]+=dp[i-1][-(j*pow(10,i-1))%13:]
  else:
    j=int(s[-i])
    if (j*pow(10,i-1))%13==0:
      dp[i]+=dp[i-1]
    else:
      dp[i][(j*pow(10,i-1))%13:]+=dp[i-1][:-(j*pow(10,i-1))%13]
      dp[i][:(j*pow(10,i-1))%13]+=dp[i-1][-(j*pow(10,i-1))%13:]
  dp[i]%=mod
print(dp[n][5])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s=list(input())
n=len(s)
dp_now=np.zeros(13,np.int64)
dp_pre=np.zeros(13,np.int64)
mod=pow(10,9)+7
if s[-1]=='?':
  dp_pre[:10]=1
else:
  dp_pre[int(s[-1])]=1
for i in range(2,n+1):
  dp_now=np.zeros(13,np.int64)
  if s[-i]=='?':
    for j in range(10):
      if (j*pow(10,i-1))%13==0:
        dp_now+=dp_pre
      else:
        dp_now[(j*pow(10,i-1))%13:]+=dp_pre[:-(j*pow(10,i-1))%13]
        dp_now[:(j*pow(10,i-1))%13]+=dp_pre[-(j*pow(10,i-1))%13:]
  else:
    j=int(s[-i])
    if (j*pow(10,i-1))%13==0:
      dp_now+=dp_pre
    else:
      dp_now[(j*pow(10,i-1))%13:]+=dp_pre[:-(j*pow(10,i-1))%13]
      dp_now[:(j*pow(10,i-1))%13]+=dp_pre[-(j*pow(10,i-1))%13:]
  dp_now%=mod
  dp_pre=dp_now.copy()
print(dp_pre[5])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
len_s = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(len_s)]
if s[-1] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[-1])] = 1

digits = 1
for i in range(1, len_s):
    digits = digits * 10
    for j in range(13):

        if dp[i - 1][j] > 0:
            if s[-(i + 1)] != '?':
                add = int(s[-(i + 1)]) * digits
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod
            else:
                for k in range(10):
                    # k:先頭に加える数字
                    add = k * digits
                    dp[i][(j + add) % 13] = (dp[i][(j + add) % 13] + dp[i - 1][j]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
len_s = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(len_s)]
if s[-1] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[-1])] = 1


for i in range(1, len_s):
    digits = pow(10, i)
    for j in range(13):
        if dp[i - 1][j] > 0:
            if s[-(i + 1)] != '?':
                add = int(s[-(i + 1)]) * digits
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod
            else:
                for k in range(10):
                    # k:先頭に加える数字
                    add = k * digits
                    dp[i][(j + add) % 13] = (dp[i][(j + add) % 13] + dp[i - 1][j]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
len_s = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(len_s)]

for i in range(len_s):
    if s[-(i + 1)] == '?':
        for j in range(13):
            if i == 0:
                if j < 10:
                    dp[i][j] = 1
                continue

            if dp[i - 1][j] > 0:
                for k in range(10):
                #k:先頭に加える数字
                    add = k * pow(10, i)
                    dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod

    else:
        if i == 0:
            dp[i][int(s[-(i + 1)])] = 1
            continue

        add = int(s[-(i + 1)]) * pow(10, i)
        for j in range(13):
            if dp[i - 1][j] > 0:
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.array([0 for j in range(13)])
if s[0] == '?':
    for i in range(10):
        dp[i] = 1
else:
    num = int(s[0])
    dp[num] = 1

for i in range(1, n):
    dp_new = np.array([0 for j in range(13)])
    if s[i] == '?':
        for m in range(10):
            num = (m * 10**i) % 13
            dp_rolled = np.roll(dp, num)
            dp_new += dp_rolled
            dp_new %= mod
    else:
        num = (int(s[i]) * 10**i) % 13
        dp_rolled = np.roll(dp, num)
        dp_new += dp_rolled
        dp_new %= mod
    dp = dp_new

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

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

for i in range(1, n):
    dp_new = [0 for j in range(13)]
    if s[i] == '?':
        for m in range(10):
            num = (m * 10**i) % 13
            for j in range(13):
                dp_new[(j+num)%13] += dp[j]
                dp_new[(j+num)%13] %= mod
    else:
        num = (int(s[i]) * 10**i) % 13
        for j in range(13):
            dp_new[(j+num)%13] += dp[j]
            dp_new[(j+num)%13] %= mod
    dp = dp_new

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

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

for i in range(1, n):
    dp_new = [0 for j in range(13)]
    if s[i] == '?':
        for m in range(10):
            num = (m * 10**i) % 13
            for j in range(13):
                dp_new[(j+num)%13] = (dp_new[(j+num)%13] + dp[j]) % mod
    else:
        num = (int(s[i]) * 10**i) % 13
        for j in range(13):
            dp_new[(j+num)%13] = (dp_new[(j+num)%13] + dp[j]) % mod
    dp = dp_new

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    len_s=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ in range(len_s+1)] #i(1-)桁目までについて，13で割った余り
    dp[0][0]=1
    for i in range(len_s):
        if s[i]=="?":
            for j in range(13):
                for k in range(10):
                    dp[i+1][(10*j+k)%13]+=dp[i][j]%mod
        else:
            c=int(s[i])
            for j in range(13):
                dp[i+1][(10*j+c)%13]=dp[i][j]
        for j in range(13):
            dp[i+1][j]%=mod
    print(dp[len_s][5])

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = {i: 0 for i in range(13)}
    table2 = {i: 0 for i in range(13)}
    table1[0] = 1
    pre = {i: [((10 * i + j) % 13) for j in range(10)] for i in range(13)}

    for l in s:
        if l == '?':
            for i in range(13):
                q = table1[i]
                for k in pre[i]:
                    table2[k] += q % mod
        else:
            for i in range(13):
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q % mod

        table1 = table2
        table2 = {i: 0 for i in range(13)}

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = {i: 0 for i in range(13)}
    table2 = {i: 0 for i in range(13)}
    table1[0] = 1
    pre = [[((10 * i + j) % 13) for j in range(10)] for i in range(13)]

    for l in s:
        if l == '?':
            for i in range(13):
                q = table1[i]
                for k in pre[i]:
                    table2[k] += q % mod
        else:
            for i in range(13):
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q % mod

        table1 = table2
        table2 = {i: 0 for i in range(13)}

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from copy import copy
    s = input()
    mod = 10 ** 9 + 7
    table1 = {i: 0 for i in range(13)}
    table2 = {i: 0 for i in range(13)}
    table3 = {i: 0 for i in range(13)}
    table1[0] = 1
    pre = {i: {j: ((10 * i + j) % 13) for j in range(10)} for i in range(13)}

    for l in s:
        if l == '?':
            for i in range(13):
                q = table1[i]
                for k in pre[i].values():
                    table2[k] += q
        else:
            for i in range(13):
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q

        table1 = table2
        table2 = table3.copy()

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7

    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[(10 * i + j) % 13 for j in range(10)] for i in range(13)]
    r13 = range(13)
    for l in s:
        if l == '?':
            for i in r13:
                q = table1[i]
                for k in pre[i]:
                    table2[k] += q
        else:
            for i in r13:
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7

    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[(10 * i + j) % 13 for j in range(10)] for i in range(13)]
    r13 = range(13)
    for l in s:
        for i in r13:
            q = table1[i]
            if l == '?':
                for k in pre[i]:
                    table2[k] += q
            else:
                k = pre[i][int(l)]
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7

    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[(10 * i + j) % 13 for j in range(10)] for i in range(13)]

    for l in s:
        for i in range(13):
            q = table1[i]
            if q == 0:
                continue
            if l == '?':
                for k in pre[i]:
                    table2[k] += q
            else:
                k = (10 * i + int(l)) % 13
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    n = len(s)
    mod = 10 ** 9 + 7

    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    for l in s:
        for i in range(13):
            q = table1[i]
            r = [int(l)] if l != '?' else range(10)
            for d in r:
                k = (10 * i + d) % 13
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[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] * 13 for _ in range(n + 2)]
    dp[n + 1][0] = 1
    for i, t in zip(range(n, 0, -1), s):
        x = dp[i]
        y = dp[i + 1]
        for j in range(13):
            z = y[j]
            if not z:
                continue
            if t == '?':
                for d in range(10):
                    k = (10 * j + d) % 13
                    x[k] += z
            else:
                k = (10 * j + int(t)) % 13
                x[k] += z

    print(dp[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]*13 for _ in range(n+1)]
dp[0][0]=1
mul=1

for i in range(n):
    x=s[-(i+1)]  # 後ろから見ていく
    if x=='?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j)%13]+=dp[i][j]
                dp[i+1][(mul*k+j)%13]%=mod
    else:
        k=int(x)
        for j in range(13):
            dp[i+1][(mul*k+j)%13]+=dp[i][j]
            dp[i+1][(mul*k+j)%13]%=mod
    mul=mul*10%13
# print(dp)
print(dp[n][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
mod = 10**9+7

# dp[i][j] : 上から i 桁までの数字で, 13で割ったあまりが j になる場合の数
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

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

print(dp[-1][5])

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

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

print(dp[keta][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

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

print(dp[keta][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

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

print(dp[keta][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

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

print(dp[keta][5] % mod)

Submission status: Time Limit Exceeded

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

mod13 = [1, 10, 9, 12, 3, 4]
moddict = {i:[0] for i in mod13}
for i in moddict:
  for j in range(1, 10):
    if (i*j)%13 not in moddict[i]:
      moddict[i].append((i*j)%13)

S = S[::-1]
modS = 0
hatenas = [0]*6
for i in range(N):
  imod6 = i%6
  if S[i] == '?':
    hatenas[imod6] += 1
  else:
    modS += int(S[i])*mod13[imod6]

modS = modS%13
target = (5 - modS)%13

count = 0
dpi = []
for i in range(6):
  if hatenas[i] >= 1:
    count += 1
    dpnow = [[0]*13 for _ in range(hatenas[i]+1)]
    dpnow[0][0] = 1
    
    modi = mod13[i]
    for j in range(hatenas[i]):
      for k in moddict[modi]:
        for l in range(13):
          dpnow[j+1][(l+k)%13] = (dpnow[j+1][(l+k)%13]+dpnow[j][l])%1000000007
    dpi.append(dpnow[-1])

dpnew = [[0]*13 for _ in range(count+1)]
dpnew[0][0] = 1
for i in range(count):
  dpinow = dpi[i]
  for j in range(13):
    for l in range(13):
      dpnew[i+1][(j+l)%13] += (dpnew[i][j] * dpinow[l])
print(dpnew[-1][target]%1000000007)

Submission status: Time Limit Exceeded

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

mod13 = [1, 10, 9, 12, 3, 4]
moddict = {i:[0] for i in mod13}
for i in moddict:
  for j in range(1, 10):
    if (i*j)%13 not in moddict[i]:
      moddict[i].append((i*j)%13)

S = S[::-1]
modS = 0
hatenas = [0]*6
for i in range(N):
  imod6 = i%6
  if S[i] == '?':
    hatenas[imod6] += 1
  else:
    modS += int(S[i])*mod13[imod6]

modS = modS%13
target = (5 - modS)%13
     
dpzero = [0]*13
dpzero[0] = 1
for i in range(6):
  if hatenas[i] >= 1:
    dpnow = [[0]*13 for _ in range(hatenas[i]+1)]
    for i2 in range(13):
      dpnow[0][i2] = dpzero[i2]
    modi = mod13[i]
    for j in range(hatenas[i]):
      for k in moddict[modi]:
        for l in range(13):
          dpnow[j+1][(l+k)%13] = (dpnow[j+1][(l+k)%13]+dpnow[j][l])%1000000007
    dpzero = dpnow[-1]          
          
print(dpzero[target])

Submission status: Time Limit Exceeded

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

mod13 = [1, 10, 9, 12, 3, 4]
moddict = {i:[0] for i in mod13}
for i in moddict:
  for j in range(1, 10):
    if (i*j)%13 not in moddict[i]:
      moddict[i].append((i*j)%13)

S = S[::-1]
modS = 0
hatenas = [0]*6
for i in range(N):
  imod6 = i%6
  if S[i] == '?':
    hatenas[imod6] += 1
  else:
    modS += int(S[i])*mod13[imod6]

modS = modS%13
target = (5 - modS)%13

count = 0
dp = [[0]*13 for _ in range(sum(hatenas)+1)]
dp[0][0] = 1

for i in range(6):
  if hatenas[i] >= 1:
    for j in range(hatenas[i]):
      count += 1
      for k in moddict[mod13[i]]:
        for l in range(13):
          dp[count][(l+k)%13] = (dp[count][(l+k)%13]+dp[count-1][l])%1000000007 

print(dp[-1][target])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10**9+7
S = str(input())
check = []
ans = 0
plo = np.array([1]+[0] * 12)
N = len(S)
for i in range(N):
    if S[N - 1 - i] == '?':
        temp = np.copy(plo)
        for k in range(1, 10):
            j = (k * 10 ** i) % 13
            temp += np.r_[plo[-j:],plo[:-j]]
        plo = temp % MOD
    else:
        j = (int(S[N - 1 - i]) * 10 ** i) % 13
        plo = np.r_[plo[-j:],plo[:-j]]
print(plo[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
s = input()
now = [0] * 13
now[0] = 1
k = 1
for c in reversed(s):
    nxt = [0] * 13
    if c == '?':
        for i in range(10):
            a = k * i % 13
            for j in range(13):
                nxt[(j + a) % 13] += now[j]
                nxt[(j + a) % 13] %= MOD
    else:
        i = int(c)
        a = k * i % 13
        for j in range(13):
            nxt[(j + a) % 13] += now[j]
            nxt[(j + a) % 13] %= MOD
    now = nxt
    k = k * 10 % 13
print(now[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10**9+7
S = str(input())
check = []
ans = 0
plo = np.array([1]+[0] * 12)
N = len(S)
for i in range(N):
    if S[N - 1 - i] == '?':
        temp = np.array([0] * 13)
        for k in range(10):
            j = (k * 10 ** i) % 13
            temp += np.r_[plo[-j:],plo[:-j]]
        plo = temp % MOD
    else:
        j = (int(S[N - 1 - i]) * 10 ** i) % 13
        plo = np.r_[plo[-j:],plo[:-j]]
print(plo[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10**9+7
S = str(input())
check = []
ans = 0
plo = np.zeros(13, dtype = int)
plo[0] = 1
N = len(S)
for i in range(N):
    if S[N - 1 - i] == '?':
        temp = np.zeros(13, dtype = int)
        for k in range(10):
            j = (k * 10 ** i) % 13
            temp += np.r_[plo[-j:],plo[:-j]]
        plo = temp
        plo = plo % MOD
    else:
        p = int(S[N - 1 - i])
        j = (p * 10 ** i) % 13
        plo = np.r_[plo[-j:],plo[:-j]]
print(plo[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
check = []
ans = 0
plo = np.zeros(13, dtype = int)
N = len(S)
for i in range(N):
    if S[N - 1 - i] == '?':
        check.append(i)
    else:
        ans += int(S[N - 1 - i])*10**i
if len(check) == 0:
    print((ans % 13 == 5) * 1)
else:
    p = check.pop()
    for i in range(10):
        j = (i * 10 ** p) % 13
        plo[j] = 1
    for p in check:
        temp = np.zeros(13, dtype = int)
        for i in range(10):
            j = (i * 10 ** p) % 13
            temp += np.r_[plo[-j:],plo[:-j]]
        plo = temp
        plo = plo % (10**9+7)
    l = (5 - ans % 13) % 13
    print(plo[l] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10
    index %= 13

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

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

s = list(str(input()))

s.reverse()
# print(s)
mod = 10**9+7

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

if s[0] == "?":
    dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    num = int(s[0]) % 13
    dp[1][num] += 1
# print(s[0])
# print(dp)
p = 1
for i in range(1, len(s)):
    # print(s[i])
    p *= 10
    if s[i] == "?":
        for j in range(10):
            num = j*p
            num %= 13
            for j in range(13):
                dp[i+1][(j+num) % 13] += dp[i][j] % mod
    else:
        num = (int(s[i]) * p) % 13
        for j in range(13):
            dp[i+1][(j+num) % 13] += dp[i][j]
    # print(dp)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

s = list(str(input()))

s.reverse()
# print(s)
mod = 10**9+7

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

if s[0] == "?":
    dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    num = int(s[0]) % 13
    dp[1][num] += 1
# print(s[0])
# print(dp)
for i in range(1, len(s)):
    # print(s[i])
    if s[i] == "?":
        for j in range(10):
            num = j*10**i
            num %= 13
            for j in range(13):
                dp[i+1][(j+num) % 13] += dp[i][j] % mod
    else:
        num = (int(s[i]) * 10**i) % 13
        for j in range(13):
            dp[i+1][(j+num) % 13] += dp[i][j]
    # print(dp)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()

#i桁以下の数字でmodがjの数
#dp[i][j]=

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

MOD=10**9+7

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


for i in range(1,len(s)):
    si=s[i]


    if s[i]!="?":
        #数字,300のmodをtempに
        for j in range(13):
            dp[i][(j*10+int(si))%13]+=dp[i-1][j]%MOD
    else:
        for l in range(10):
            for j in range(13):
                dp[i][(j*10+l)%13]+=dp[i-1][j]%MOD
    #print(dp[i],sum(dp[i]))



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

Submission status: Time Limit Exceeded

Solution code:
# D - Digits Parade
# https://atcoder.jp/contests/abc135/tasks/abc135_d

S = input()
n = len(S)

MOD = 10 ** 9 + 7

# dp[i][j] i桁目まででj余る数
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
  for j in range(10):
    if s == "?" or int(s) == j:
      for k in range(13):
        dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= MOD

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

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

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

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

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