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:
S = input()
S_r = []
for i in range(len(S)-1,-1,-1):
    S_r.append(S[i])
#print(S_r)
modlist_r =[1,10,9,12,3,4]
modlist = [4,3,12,9,10,1]
basemod = 0
for i in range(len(S_r)):
    if S_r[i] == '?':
        continue
    else:
        basemod= (basemod+modlist_r[i%6]*int(S_r[i]))%13
#print(basemod)

p_keys={}

for i in range(13):
    if i == basemod :
        p_keys[i] =1
    else:
        p_keys[i] =0

#print(p_keys)

for i in range(len(S_r)):
    if S_r[i] == '?':
        #basemod= (basemod+modlist_r[i%6]*int(S_r[i]))%13
        next_keys={}
        for j in range(10):
            for k in range(13):
                if (modlist_r[i%6]*j+k)%13 in next_keys.keys():
                    next_keys[ (modlist_r[i%6]*j+k)%13 ] = next_keys[ (modlist_r[i%6]*j+k)%13 ] +p_keys[k]
                    next_keys[ (modlist_r[i%6]*j+k)%13 ] = next_keys[ (modlist_r[i%6]*j+k)%13 ] %(10**9+7)
                else:
                    next_keys[ (modlist_r[i%6]*j+k)%13 ] = p_keys[k]
                    next_keys[ (modlist_r[i%6]*j+k)%13 ] = next_keys[ (modlist_r[i%6]*j+k)%13 ] %(10**9+7)
        p_keys=next_keys
            #p_keys[ (modlist_r[i%6]*j)%13 ] = p_keys[ (modlist_r[i%6]*j)%13 ] %(10**9+7)
    else:
        continue

print(p_keys[5])


#print(2005%13)
#for i in range(30):
#    print(i,10**i % 13)

#for i in modlist_r:
#    nlist=[]
#    for j in range(10):
#        nlist.append( (i*j) %13)
#    nlist.sort()
#    print(i,nlist)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0]*13 for _ in range(len(S))]
if S[0]=="?":
  dp[0] = [1]*10+[0]*3
else:
  dp[0][int(S[0])] = 1
mod = 10**9+7
table = {str(i):[(10*j+i)%13 for j in range(13)] for i in range(10)}
for k in range(1,len(S)):
  tmp = dp[k-1]
  if S[k] != "?":
    for i,t in enumerate(table[S[k]]):
      dp[k][t]= tmp[i]
  else:
    for j in range(10):
      for i,t in enumerate(table[str(j)]):
        dp[k][t] += tmp[i]%mod
    dp[k] = [p%mod for p in dp[k]]
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    S = S[::-1]

    dp = [0] * 13
    dp[0] = 1
    MOD = 10**9 + 7

    for i in range(len(S)):
        nextdp = [0] * 13
        for j in range(13):
            if S[i] != '?':
                k = int(S[i])
                nextdp[(j+k*10**i)%13] += dp[j]
                nextdp[(j+k*10**i)%13] %= MOD
            else:
                for k in range(10):
                    nextdp[(j+k*10**i)%13] += dp[j]
                    nextdp[(j+k*10**i)%13] %= MOD
        dp = nextdp


    print(dp[5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

    dp[0][0] = 1

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    S = S[::-1]

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

    dp[0][0] = 1

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


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



main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s=input()
l=len(s)
a=10**9+7

if s[l-1] == '?':
  n=np.array([1,1,1,1,1,1,1,1,1,1,0,0,0], dtype='uint64')
else:
  n=np.array([0,0,0,0,0,0,0,0,0,0,0,0,0], dtype='uint64')
  n[int(s[l-1])]=1
d=np.array([0,0,0,0,0,0,0,0,0,0,0,0,0], dtype='uint64')

m=1
for i in range(1,len(s)):
  m=(m*10)%13
  if s[l-1-i] == '?':
    for j in range(13):
      for k in range(10):
        d[(m*k+j)%13] += n[j]
  else:
    for j in range(13):
      d[(m*int(s[l-1-i])+j)%13] += n[j]

  for j in range(13):
    n[j]=d[j]%a
    d[j]=0

print(n[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s)
a=10**9+7

if s[l-1]=='?':
  n=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  n=[0,0,0,0,0,0,0,0,0,0,0,0,0]
  n[int(s[l-1])]=1
d=[0,0,0,0,0,0,0,0,0,0,0,0,0]

m=1
for i in range(1,len(s)):
  m=(m*10)%13
  if s[l-1-i] == '?':
    for j in range(13):
      for k in range(10):
        d[(m*k+j)%13] += n[j]
  else:
    for j in range(13):
      d[(m*int(s[l-1-i])+j)%13] += n[j]

  for j in range(13):
    n[j]=d[j]%a
    d[j]=0

print(n[5])

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

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

for i in range(n):
    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]
    for j in range(13):
        dp[i + 1][j] %= 10**9 + 7

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
# sも10**5と大きい
# 愚直にやると探索はO(10**n)

# 桁の先頭から筆算の要領で桁を落としていく
# 余り0~12で場合分け

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

print(num_mod[len(s)][5] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# sも10**5と大きい
# 愚直にやると探索はO(10**n)

# 桁の先頭から筆算の要領で桁を落としていく
# 余り0~12で場合分け

s = input()
num_mod = [[0 for _ in range(13)] for _ in range(len(s)+1)]
num_mod[0][0] = 1
for i in range(len(s)):
    for j in range(13):
        num_mod[i][j] %= (10**9+7)
        if s[i] != '?':
            num_mod[i+1][(j*10+int(s[i])) % 13] += num_mod[i][j]
        else:
            for k in range(10):
                num_mod[i+1][(j*10+k) % 13] += num_mod[i][j]

print(num_mod[len(s)][5] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# %10**9+7
# sの桁も10**5と大きい
# 愚直にやると探索は10**count(?)
# 仮に全部?で10**5としたら...
# 13で割って余り5を使ってどうにか小さくしたい

# 桁の先頭から剰余の筆算の容量で桁を落としていく
# ?で余り0~12に分岐
import sys
sys.setrecursionlimit(10**9)
s = input()
num_mod = [[0 for _ in range(13)] for _ in range(len(s)+1)]
num_mod[0][0] = 1
for i in range(len(s)):
    for j in range(13):
        if s[i] != '?':
            num_mod[i+1][(j*10+int(s[i])) % 13] += num_mod[i][j]
        else:
            for k in range(10):
                num_mod[i+1][(j*10+k) % 13] += num_mod[i][j]

print(num_mod[len(s)][5] % (10**9+7))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
for i in range(len(S)):
    if S[i] != '?':
        S[i] = int(S[i])
    else:
        S[i] = -1

R = [[None]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        R[i][j] = (10*i+j) % 13

Q = [[] for i in range(13)]
for j in range(10):
    for i in range(13):
        Q[R[i][j]] += [[i,j]]

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

for i in range(len(S)):
    for j in range(13):
        if S[i]!=-1:
            dp[i+1][j] += dp[i][Q[j][S[i]][0]]
        else:
            for k in range(10):
                dp[i+1][j] += dp[i][Q[j][k][0]]

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

R = [[None]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        R[i][j] = (10*i+j) % 13
        
Q = [[] for i in range(13)]
for j in range(10):
    for i in range(13):
        Q[R[i][j]] += [[i,j]]

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

for i in range(len(S)):
    for j in range(13):
        if S[i]!='?':
            dp[i+1][j] += dp[i][Q[j][int(S[i])][0]]
        else:
            for k in range(10):
                dp[i+1][j] += dp[i][Q[j][k][0]]
                
print(dp[len(S)][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

def is_match(S, I):
    num = len(S) - len(I)
    I_2 = []
    if num > 0:
        I_2 = ['0'] * (num)
        I_2.extend(I)
    else:
        I_2 = I
    for s, i in zip(S, I_2):
        if s == i or s == '?':
            continue
        else:
            return False
    return True

S = list(input())

denominator = 10 ** 9 + 7

answer = 0

i = 5
while i < 10 ** len(S):
    if is_match(S, list(str(i))):
        answer += 1
    i += 13

print(answer % denominator)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def is_match(S, I):
    num = len(S) - len(I)
    I_2 = []
    if num > 0:
        I_2 = ['0'] * (num)
        I_2.extend(I)
    else:
        I_2 = I
    for s, i in zip(S, I_2):
        if s == i or s == '?':
            continue
        else:
            return False
    return True

S = list(input())

denominator = 10 ** 9 + 7

answer = 0

i = 5
while i < 10 ** len(S):
    if is_match(S, list(str(i))):
        answer += 1
    i += 13

print(answer % denominator)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)
n=len(s)
for i in range(1,n):
    if s[i]=="?":
        now=-1
    else:
        now=int(s[i])
    if now==-1:
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
                cnt[i][(j*10+k)%13]%=mod
    else:
        for j in range(13):
            cnt[i][(j*10+now)%13]+=cnt[i-1][j]
            cnt[i][(j*10+now)%13]%=mod

# print(cnt)
print(cnt[n-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
ans=1
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)
n=len(s)
for i in range(1,n):
    if s[i]=="?":
        now=-1
    else:
        now=int(s[i])
    if now==-1:
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
    else:
        for j in range(13):
            cnt[i][(j*10+now)%13]+=cnt[i-1][j]

# print(cnt)
print(cnt[len(s)-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
ans=1
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)

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

# print(cnt)
print(cnt[len(s)-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


S = input().strip()
# S = '?' * (10**4)

dp = [[0 for _ in range(13)] for _ in range(len(S))]
digits = list(S)
digits.reverse()

if digits[0] == '?':
    dp[0] = [1 for _ in range(10)] + [0 for _ in range(3)]
else:
    dp[0][int(digits[0])] = 1

# 調べる桁
index = 1

for digit in digits[1:]:
    # print(dp)
    if digit == '?':
        # 0~9 まで前の桁をベースに軸を動かす
        for i in range(10):
            mod = i * (10**index) % 13
            dp[index] = [a + b for a, b in zip(dp[index], dp[index - 1][-mod:] + dp[index - 1][:13-mod])]
    else:
        # その数で前の桁をベースに軸を動かす
        mod = int(digit) * (10**index) % 13
        dp[index] = [a + b for a, b in zip(dp[index], dp[index - 1][-mod:] + dp[index - 1][:13-mod])]

    dp[index] = [x % (10**9 + 7) for x in dp[index]]
    index += 1

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

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int


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

    n = len(S)
    dp[0][0] = 1
    for i in range(n):
        c = -1 if S[i] == "?" else int(S[i]) 

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

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

    print(dp[n][5])

    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


# S = '?44'
# S = '6???'
# S = '0???76???'
S = input().strip()

dp = [[0 for _ in range(13)] for _ in range(len(S))]
digits = list(S)
digits.reverse()

if digits[0] == '?':
    dp[0] = [1 for _ in range(10)] + [0 for _ in range(3)]
else:
    dp[0][int(digits[0])] = 1

# 調べる桁
index = 1

for digit in digits[1:]:
    # print(dp)
    if digit == '?':
        # 0~9 まで前の桁をベースに軸を動かす
        for i in range(10):
            mod = i * (10**index) % 13
            # previous_digit_mods の各々の値を mod だけずらす
            previous_digit_mods = dp[index - 1][:]  # copy
            tmp_list = []
            for j in range(mod):
                tmp_list.insert(0, previous_digit_mods.pop())
            dp[index] = [a + b for a, b in zip(dp[index], tmp_list + previous_digit_mods)]
    else:
        # その数で前の桁をベースに軸を動かす
        mod = int(digit) * (10**index) % 13
        # print('mod', mod)
        previous_digit_mods = dp[index - 1][:]
        tmp_list = []
        for j in range(mod):
            tmp_list.insert(0, previous_digit_mods.pop())
        dp[index] = [a + b for a, b in zip(dp[index], tmp_list + previous_digit_mods)]

    index += 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
# for _ in range(len(s) + 1):
#     l = []
#     for __ in range(13):
#         l.append(0)
#     dp.append(l)
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    if si == '?':
        for n in range(10):
            a = n * (10 ** i)
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * (10 ** i)
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
# for _ in range(len(s) + 1):
#     l = []
#     for __ in range(13):
#         l.append(0)
#     dp.append(l)
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    if si == '?':
        for n in range(10):
            a = n * (10 ** i) % 13
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * (10 ** i) % 13
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
dp = []
for _ in range(len(s) + 1):
    l = []
    for __ in range(13):
        l.append(0)
    dp.append(l)
# [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    if si == '?':
        for n in range(10):
            a = n * (10 ** i) % 13
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * (10 ** i) % 13
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
dp = []
for _ in range(len(s) + 1):
    l = []
    for __ in range(13):
        l.append(0)
    dp.append(l)
# [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[-i-1] == '?':
        for n in range(10):
            a = n * (10 ** i) % 13
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(s[-i-1]) * (10 ** i) % 13
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def is_match(str_num):
  for idx, num in nums.items():
    if str_num[idx] != num: return False
  return True

S = input()
lenS = len(S)
nums = {idx: s for idx, s in enumerate(S) if s != '?' }

MOD = 10**9 + 7
ans = 0

for i in range(int(S.replace('?', '9'))//13 + 1):
  num = i*13 + 5
  str_num = str(num).zfill(lenS)

  if is_match(str_num) is True:
    ans += 1
    ans = ans % MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()

rs = [0] * 13

M = 10**9 + 7

if S[-1] == "?":
    rs[:10] = [1] * 10
else:
    rs[int(S[-1])] = 1

for i in range(1, len(S)):
    nrs = [0] * 13
    c = S[-i - 1]
    if c == "?":
        ns = range(10)
    else:
        ns = [int(c)]
    for n in ns:
        r = (10 ** i) * n % 13
        for j in range(13):
            jj = (j + r) % 13
            nrs[jj] = (nrs[jj] + rs[j]) % M
    rs = nrs

# print(rs)
print(rs[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
dp=[0]*13
if s[-1]=='?':
    dp[:10]=[1]*10
else:
    dp[int(s[-1])]=1
for i in range(1,n):
    if s[~i]=='?':
        a=[0]*13
        l=[j*10**i%13 for j in range(10)]
        for i in range(13):
            a[i]=sum(dp[(i-x)%13] for x in l)%(10**9+7)
        dp=a
    else:
        a=int(s[~i])*10**i%13
        dp=dp[-a:]+dp[:-a]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    s = input().strip()[::-1]

    dp = np.zeros((len(s)+1, 13), dtype=int)
    dp[0][0] = 1
    MOD = int(1e9) + 7
    keta = 1
    for i in range(len(s)):
        if s[i] != "?":
            t = int(s[i]) * keta
            t %= 13
            if t == 0:
                dp[i+1] = dp[i]
            else:
                dp[i+1][:t] = dp[i][-t:]
                dp[i+1][t:] = dp[i][:-t]
        else:
            dp[i+1] = dp[i]
            for t in range(1, 10):
                t *= keta
                t %= 13
                dp[i+1][:t] += dp[i][-t:]
                dp[i+1][t:] += dp[i][:-t]
                dp[i+1] %= MOD
        keta *= 10
        keta %= 13
    print(dp[-1][5])

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()[::-1]

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

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

amari=[[(10**i)*x%13 for x in range(10)] for i in range(6)]
dp=[1]+[0]*12
new_dp=[0]*13

mod=10**9+7

for id,char in enumerate(s):
    new_dp=[0]*13
    if char!='?':
        for i in range(13):
            new_i=(i+amari[id%6][int(char)])%13
            new_dp[new_i]+=dp[i]
        dp=new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i=(i+amari[id%6][j])%13
                new_dp[new_i]+=dp[i]
        dp=[x%mod for x in new_dp]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
inf = 10**9+7
modlist = [1, 10, 9, 12, 3, 4]

S = list(input())
S.reverse()

dp = [[0 for i in range(13)] for j 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 l in range(10):
        if S[i] != "?" and int(S[i]) != l:
            continue
        for j in range(13):
            dp[i][(l*modlist[i%6]+j)%13] += dp[i-1][j]
            dp[i][(l*modlist[i%6]+j)%13] %= inf

ans = dp[len(S)-1][5]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def main():
    s = open(0).read()[:-1][::-1]
    n = len(s)

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

    mod13 = [1, 10, 9, 12, 3, 4]
    for i, cur_s in enumerate(s[1:], start=1):
        next = [0] * 13
        if cur_s == '?':
            for j in range(10):
                remain = j * mod13[i % 6] % 13
                for k in range(13):
                    next[(k + remain) % 13] += prev[k]
        else:
            remain = int(cur_s) * mod13[i % 6] % 13
            for k in range(13):
                next[(k + remain) % 13] += prev[k]
        prev = [cur_next % MOD for cur_next in next]

    ans = prev[5] % MOD
    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

def main():
    s = open(0).read()[:-1][::-1]
    n = len(s)

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

    for i, cur_s in enumerate(s[1:], start=1):
        if cur_s == '?':
            for j in range(10):
                remain = j * 10**i % 13
                for k in range(13):
                    dp[i][(k + remain) % 13] += dp[i-1][k]
        else:
            remain = int(cur_s) * 10**i % 13
            for k in range(13):
                dp[i][(k + remain) % 13] += dp[i-1][k]
    ans = dp[-1][5] % mod
    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
#S = "?" * 100000
S = S[::-1]
N = 13
mod = 10 ** 9 + 7
dp = [0] * 26
dp[13] = 1
digit = 1
for c in range(len(S)):
    dp[:13] = [0] * N
    if S[c] == '?':
        for k in range(10):
            for j in range(N):
                idx = (k * digit + j) % N
                dp[idx] = (dp[idx] + dp[j + 13]) % mod
    else:
        k = int(S[c])
        for j in range(N):
            idx = (k * digit + j) % N
            dp[idx] = (dp[idx] + dp[j + 13]) % mod
    digit *= 10
    digit %= N
    #print(dp)
    dp[13:26] = dp[:13]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
#S = "?" * 100000
S = S[::-1]
N = 13
mod = 10 ** 9 + 7
dp = [0] * 26
dp[13] = 1
digit = 1
for c in range(len(S)):
    dp[:13] = [0] * N
    if S[c] == '?':
        for k in range(10):
            for j in range(N):
                idx = (k * digit + j) % N
                dp[idx] += dp[j + 13]
                dp[idx] %= mod
    else:
        k = int(S[c])
        for j in range(N):
            #index = (k * digit + j) % N
            idx = (k * digit + j) % N
            dp[idx] += dp[j + 13]
            dp[idx] %= mod

    digit *= 10
    digit %= N
    #print(dp)
    dp[13:26] = dp[:13]
    #print(dp)
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 1000000007
s = [int(x) if x!="?" else -1 for x in input()]
#s = s[::-1]
dp = np.full((len(s), 13), 0, dtype="int64")

if s[0] == -1:
    dp[0][0:10] = 1
else:
    dp[0][int(s[0])] = 1

table = [ s % 13 for s in range(130)]
for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])

        for old_amari in range(13):
            new_amari = (table[old_amari * 10] + value) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (table[old_amari * 10] + value) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]

    dp[index] = dp[index] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 1000000007
#s = (list(input()))
s = [int(x) if x!="?" else -1 for x in reversed(input())]
#s = s[::-1]

dp = np.full((len(s), 13), 0, dtype="int64")

if s[0] == -1:
    dp[0][0:10] = 1
else:
    dp[0][int(s[0])] = 1

for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])
        for old_amari in range(13):
            new_amari = (value * pow(10, index) + old_amari) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (value * pow(10, index) + old_amari) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
    dp[index] = dp[index] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 1000000007
s = (list(input()))
s = s[::-1]
dp = np.full((len(s), 13), 0, dtype="int64")

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

for index in range(1, len(s)):
    if not s[index] == "?":
        value = int(s[index])
        for old_amari in range(13):
            new_amari = (value * pow(10, index) + old_amari) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (value * pow(10, index) + old_amari) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
    dp[index] = dp[index] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
 
dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0]=1

res = [[x * 10 ** i % 13 for x in range(10)] for i in range(6)]
 
mod = 10 ** 9 + 7
 
for idx, char in enumerate(s):

    if char != "?":
        for i in range(13):
            new_i = (i + res[idx % 6][int(char)]) % 13
            dp[idx+1][new_i] += dp[idx][i]
    else:
        for i in range(13):
            for j in range(10):
                new_i = (i + res[idx % 6][j]) % 13
                dp[idx+1][new_i] += dp[idx][i] % mod
        #dp = [x % mod for x in new_dp]

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