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()

MOD = 10**9+7

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


dp[0][0] = 1

for index in range(1, len(S) + 1):
    s = S[len(S) - index ]
    mul = (10 ** (index - 1)) % 13
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul  +  pre_index ) % 13
                dp[index][next_i] += dp[index - 1][pre_index] 
    else:
        i = int(s)
        for pre_index in range(13):
            next_i = (i * mul +  pre_index ) % 13
            dp[index][next_i] += dp[index - 1][pre_index] 

    for i in range(13):
        dp[index][i] %= 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 index in range(1, len(S) + 1):
    s = S[len(S) - index ]
    mul = (10 ** (index - 1)) % 13
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul  +  pre_index ) % 13
                dp[index][next_i] += dp[index - 1][pre_index] 
    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i * mul +  pre_index ) % 13
            dp[index][next_i] += dp[index - 1][pre_index] 

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



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

Submission status: Time Limit Exceeded

Solution code:
S = input()
# dp = [[0] * 13 for _ in range(len(S) + 1)]  # np.zeros([len(S) + 1, 13]).tolist()
dp = [0] * 13
dp[0] = 1
next_dp = [0] * 13
L = len(S)

MOD = 10 ** 9 + 7

for i in range(1, L + 1):
    m = (10 ** (L - i)) % 13
    # print(m)
    s = S[i - 1]

    if s == '?':
        _range = range(10)
    else:
        _range = range(int(s), int(s) + 1)
    for j in range(13):
        for k in _range:
            next_dp[(j + (k * m)) % 13] += dp[j] % MOD

    for i in range(13):
        dp[i] = next_dp[i]
        next_dp[i] = 0

print(dp[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]  # np.zeros([len(S) + 1, 13]).tolist()
dp[0][0] = 1
L = len(S)

MOD = 10 ** 9 + 7

for i in range(1, L + 1):
    m = (10 ** (L - i)) % 13
    # print(m)
    s = S[i - 1]

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
dp = np.zeros([len(S) + 1, 13]).tolist()
dp[0][0] = 1
L = len(S)

for i in range(1, L + 1):
    m = (10 ** (L - i)) % 13
    # print(m)
    s = S[i - 1]

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

print(int(dp[L][5]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
ns=[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 10, 7, 4, 1, 11, 8, 5, 2, 12], [0, 9, 5, 1, 10, 6, 2, 11, 7, 3], [0, 12, 11, 10, 9, 8, 7, 6, 5, 4], [0, 3, 6, 9, 12, 2, 5, 8, 11, 1], [0, 4, 8, 12, 3, 7, 11, 2, 6, 10]]
miti=[0,0,0,0,0,0]
now=0
for i in range(len(s)):
  if s[-i-1]=="?":
    miti[i%6]+=1
  else:
    now+=ns[i%6][int(s[-i-1])]
now=now%13
#print(now,miti)

dp=[[0]*13 for j in range(len(s)+1)]
dp[0][now]=1
ii=0
for i in range(6):
  nsi=ns[i]
  for j in range(miti[i]):
    dp1=dp[ii]
    dp2=dp[ii+1]
    #print(dp1)
    #print(dp2)
    for n in range(13):
      dp1[n]=dp1[n]%mod
    for k in range(10):
      nsik=nsi[k]
      for l in range(13):
        dp2[(l+nsik)%13]+=dp1[l]
    ii+=1
print(dp[ii][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=list(input())
ns=[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 10, 7, 4, 1, 11, 8, 5, 2, 12], [0, 9, 5, 1, 10, 6, 2, 11, 7, 3], [0, 12, 11, 10, 9, 8, 7, 6, 5, 4], [0, 3, 6, 9, 12, 2, 5, 8, 11, 1], [0, 4, 8, 12, 3, 7, 11, 2, 6, 10]]
miti=[0,0,0,0,0,0]
now=0
for i in range(len(s)):
  if s[-i-1]=="?":
    miti[i%6]+=1
  else:
    now+=ns[i%6][int(s[-i-1])]
now=now%13
#print(now,miti)

dp=[0 for i in range(26)]
dp[now]=1
for i in range(6):
  for j in range(miti[i]):
    for n in range(13):
      dp[n]=dp[n]%mod
    for k in range(10):
      for l in range(13):
        dp[(l+ns[i][k])%13+13]+=dp[l]
    #print("1",dp)
    dp[0:13]=dp[13:26]
    dp[13:26]=[0]*13
    #print("2",dp)
print(dp[5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import re
S = input()

hatena = S.count('?')

MOD = 10 ** 9 + 7
S_len = len(S)
pattern = S.replace('?', '\d')
repatter = re.compile(pattern)

count = 0
for i in range(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000):
    if len(str(i * 13 + 5)) > S_len:
        break
    s = str(i * 13 + 5).zfill(S_len)
    result = repatter.match(s)
    if result:
        count += 1

print(count)

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,d in enumerate(s):
	if d=="?":
		for x in range(10):
			for y in range(13):
				dp[i+1][(y*10+x)%13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i+1][(y*10+d)%13] += dp[i][y]
	for j in range(13):
		dp[i+1][j] %= mod
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for i in range(length):
    
    x = S[- (i + 1)]
    
    if x == "?":
        
        for j in range(13):
            
            for k in range(10):
            
                dp[i + 1][(k * mul + j) % 13] += dp[i][j]
                dp[i + 1][(k * mul + j) % 13] %= INF
                
    else:
        
        c = int(x)
        
        for j in range(13):
            
            dp[i + 1][(c * mul + j) % 13] += dp[i][j]
            dp[i + 1][(c * mul + j) % 13] %= INF
            
    mul = (mul * 10) % 13
    
print(dp[length][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for i in range(length):
    
    x = S[-(i + 1)]
    
    if x == "?":
        
        for j in range(13):
            
            for k in range(10):
            
                dp[i + 1][(k * mul + j) % 13] += dp[i][j]
                dp[i + 1][(k * mul + j) % 13] %= INF
                
    else:
        
        c = int(x)
        
        for j in range(13):
            
            dp[i + 1][(c * mul + j) % 13] += dp[i][j]
            dp[i + 1][(c * mul + j) % 13] %= INF
            
    mul *= 10
    
print(dp[length][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
t = 10
for i in range(1, len(s)):
    if s[-1*i-1] == "?":
        c = pre.copy()
        for j in range(1,10):
            te = t*j % 13
            for k in range(13):
                c[k] = c[k] + pre[(13+k-te)%13]
        pre = c.copy()
        for k in range(13):
            pre[k] %= n
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
    t = t*10%13
print(pre[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
for i in range(len(s)):
    t = 10**i % 13
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
print(pre[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
#tem = [i%13 for i in range(130)]
tem = [[i*j%13 for i in range(10)] for j in range(13)]
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
tem = [i%13 for i in range(130)]
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        te = tem[:t*10:t]
        pre = [np.sum([pre[(13+k-i)%13] for i in te])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = pre.copy()
        for j in range(1,10):
            te = t*j % 13
            for k in range(13):
                c[k] = c[k] + pre[(13+k-te)%13]
        pre = c.copy()
        for k in range(13):
            pre[k] %= n
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = pre.copy()
        for j in range(1,10):
            te = t*j % 13
            for k in range(13):
                c[k] = (c[k] + pre[(13+k-te)%13]) % n
        pre = c.copy()
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5]%n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = np.array(pre)
        for j in range(1,10):
            te = t*j % 13
            c += pre[13-te:] + pre[:13-te]
        c %= n
        pre = c.tolist()
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5]%n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
if s[-1] == "?":
    pre = [1 for i in range(10)] + [0,0,0]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = np.array(pre)
        for j in range(1,10):
            te = t*j % 13
            c[te:] += pre[:13-te]
            c[:te] += pre[13-te:]
            c %= n
        pre = c.tolist()
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5]%n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()

MOD = 10 ** 9 + 7
mod_change_table = [(i * 10) % 13 for i in range(13)]
dp = np.array([[0] * 13] * (len(S)))
if S[0] == '?':
    dp[0][:10] = 1
else:
    dp[0][int(S[0])] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()

MOD = 10 ** 9 + 7

dp = np.array([[0] * 13] * (len(S) + 1))
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])

    for k in range(10):
        if c == -1 or c == k:
            for j in range(13):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    dp[i + 1] %= MOD
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

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

def main():
    s = list(input().strip())[::-1]
    hatenas = []
    keta = 1
    start = 0
    for i in range(len(s)):
        if s[i] == "?":
            hatenas.append(keta)
        else:
            start += int(s[i]) * keta
            start %= 13
        keta *= 10
        keta %= 13


    dp = np.zeros((len(hatenas)+1, 13), dtype=int)
    MOD = int(1e9) + 7

    # print(hatenas)
    # 1桁目をみて初期値dp[0]を決定
    dp[0][start] = 1
    for i, keta in enumerate(hatenas):
        # 差分だけずらした前の状態を加算
        for t in range(10): # t := 0~9
            tmp = (keta * t) % 13
            dp[i+1][:tmp] += dp[i][13-tmp:]
            dp[i+1][tmp:] += dp[i][:13-tmp]
        dp[i+1] %= MOD
    # print(dp)
    print(int(dp[-1][5]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    dp = np.zeros((len(s), 13))
    MOD = int(1e9) + 7

    # 1桁目をみて初期値dp[0]を決定
    if s[0] == "?":# 0~9全て入れられる
        for i in range(10):
            dp[0][i] = 1
    else:
        tmp = int(s[0])
        dp[0][tmp] = 1
    
    keta = 10
    for i in range(1, len(s)):
        ind = []
        if s[i] == "?":# 0~9全て入れられる
            for t in range(10):# t := 0~9
                ind.append((t * keta) % 13) # ずれる差分を格納
        else:
            ind.append((int(s[i]) * keta) % 13) # ずれる差分を格納
        # 差分だけずらした前の状態を加算
        for tmp in ind:
            dp[i][:tmp] += dp[i-1][13-tmp:]
            dp[i][tmp:] += dp[i-1][:13-tmp]
        dp[i] %= MOD
        keta *= 10
        keta %= 13
    print(int(dp[-1][5]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i in range(len(s)):
    if s[i] == '?':
        for j in range(10):
            next = j * 10 ** i
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = int(s[i]) * 10**i
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
print(rem[len(s)][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i, st in enumerate(s):
    if st == '?':
        for j in range(10):
            next = j * 10 ** i
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = int(st) * 10**i
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
    for _ in range(13):
        rem[i+1][_] %= mod
print(rem[len(s)][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i, st in enumerate(s):
    if st == '?':
        for j in range(10):
            next = j * 10 ** i
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = int(st) * 10**i
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
print(rem[len(s)][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in range(13):
        dpij = dpi[j]
        j10 = j * 10
        for k in range(10):
          dpi1[lut[j10 + k]] += dpij
    else:
      t = int(s[i])
      for j in range(13):
        dpi1[lut[j * 10 + t]] += dpi[j]
    for k in range(13):
      dp[i + 1][k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
divisor = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(s) + 1)]
dp[0][0] = 1
lut = [i % 13 for i in range(130)]
for i in range(len(s)):
  dpi = dp[i]
  dpi1 = dp[i + 1]
  if s[i] == '?':
    for j in range(13):
      dpij = dpi[j]
      j10 = j * 10
      for k in range(10):
        dpi1[lut[j10 + k]] += dpij
  else:
    t = int(s[i])
    for j in range(13):
      dpi1[lut[j * 10 + t]] += dpi[j]
  for k in range(13):
    dp[i + 1][k] %= divisor
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        m = j
        for k in list13:
          dpi1[m] += dpi[k]
          m = lut[m + 10]
    else:
      m = int(s[i])
      for k in list13:
        dpi1[m] += dpi[k]
        m = lut[m + 10]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        m = j
        for k in list13:
          dpi1[lut[m]] += dpi[k]
          m += 10
    else:
      m = int(s[i])
      for k in list13:
        dpi1[lut[m]] += dpi[k]
        m += 10
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  m = [i * 10 % 13 for i in range(13)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        for k in list13:
          dpi1[lut[m[k] + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in list13:
        dpi1[lut[m[k] + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        for k in list13:
          dpi1[lut[k * 10 + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in list13:
        dpi1[lut[k * 10 + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in range(10):
        for k in range(13):
          dpi1[lut[k * 10 + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in range(13):
        dpi1[lut[k * 10 + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in range(10):
        for k in range(13):
          dpi1[(k * 10 + j) % 13] += dpi[k]
    else:
      t = int(s[i])
      for k in range(13):
        dpi1[(k * 10 + t) % 13] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i, st in enumerate(s):
    if st == '?':
        for j in range(10):
            next = (j * 10 ** i) % 13
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = (int(st) * 10**i) % 13
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
    for _ in rem[i]:
        _ %= mod
print(rem[len(s)][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [0] * 13
rem[0] = 1
for i, st in enumerate(s):
    if st == '?':
        tmp = rem[:]
        rem = [0] * 13
        for j in range(10):
            next = (j * 10 ** i) % 13
            for k in range(13):
                rem[(k+next)%13] += tmp[k]
    else:
        next = (int(st) * 10**i) % 13
        tmp = rem[:]
        for j in range(13):
            rem[(j+next)%13] = tmp[j]
    for _ in rem:
        _ %= mod
print(rem[5] % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

for i,s in enumerate(S):
    m = pow(10,(N-i-1),13)
    if s == '?':
        for d in range(10):
            for k in range(13):
                dp[i+1][(k+m*d)%13] += dp[i][k]
    else:
        d = int(s)
        for k in range(13):
            dp[i+1][(k+m*d)%13] += dp[i][k]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()
ss = [i for i in s[::-1]]
rem = [0] * 13
rem[0] = 1
for i, st in enumerate(ss):
    if st == '?':
        tmp = rem[:]
        rem = [0] * 13
        for j in range(10):
            next = (j * 10 ** i) % 13
            for k in range(13):
                rem[(k+next)%13] += tmp[k]
    else:
        next = (int(st) * 10**i) % 13
        tmp = rem[:]
        for j in range(13):
            rem[(j+next)%13] = tmp[j]
print(rem[5] % mod)

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int


def solve(S: str):
    # dp = np.zeros((len(S) + 1, 13))
    dp = [[0 for j in range(13)] for i in range(len(S) + 1)]
    dp[0][0] = 1
    for i in range(len(S)):
        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:
            j = int(S[i])
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
    print(int(dp[-1][5]) % MOD)

    return


# Generated by 1.1.5 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:
#!/usr/bin/env python3
import sys
import numpy as np

MOD = 1000000007  # type: int


def solve(S: str):
    dp = np.zeros((len(S) + 1, 13))
    dp[0, 0] = 1
    for i in range(len(S)):
        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:
            j = int(S[i])
            for k in range(13):
                dp[i + 1, (k * 10 + j) % 13] += dp[i, k] % MOD
    print(int(dp[-1, 5]) % MOD)

    return


# Generated by 1.1.5 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:
import sys
input = sys.stdin.readline
MAX_C = 10**9 + 7


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

#mat = [[0]*13 for _ in range(n)]
p = [0]*13
np = [0]*13

list10 = list(range(10))
list13 = list(range(13))
mods = [i % 13 for i in range(130)]

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

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

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

    for i in list13:
        p[i] = np[i] % MAX_C
        np[i] = 0
        #mat[col_i][i] %= MAX_C

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