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 = list(input().rstrip())
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
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]

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

Submission status: Time Limit Exceeded

Solution code:
s = []
for c in input():
	if c != '?':
		s.append(int(c))
	else:
		s.append(-1)

n = len(s)
mod = int(10**9 + 7)

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

def stfu(i, j, d):
	dp[i + 1][(10 * j + d) % 13] += dp[i][j]
	dp[i + 1][(10 * j + d) % 13] %= mod


for i in range(n):
	for j in range(13):
		if s[i] == -1:
			for d in range(10):
				stfu(i, j, d)
		else:
			stfu(i, j, s[i])

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = []
for c in input():
	if c != '?':
		s.append(int(c))
	else:
		s.append(-1)

n = len(s)
mod = int(10**9 + 7)

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

for i in range(n):
	for j in range(13):
		for d in range(10):
			if s[i] == -1 or d == s[i]:
				dp[i + 1][(10 * j + d) % 13] += dp[i][j]
				dp[i + 1][(10 * j + d) % 13] %= mod

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import re

S = input()

#print('S=', S)

list_S = list(S)

n = len(S)

#print('list_S', list_S)
#print('digit=', n)

count_S = 0

for i in range(len(S)) :
	if S[i] == '?' :
		count_S = count_S + 1 

#print('count_?=', count_S) 

#list_all = [i for i in range(0, 10**n)]
#list_all = [13*i+5 for i in range(0, 10**n)]

list_all = []

i = 0
while 13*i+5 < 10**n :
	list_all.append(13*i+5)
	i = i + 1


#print('list_all=', list_all)

count_judge = 0

#for i in list_all :
#for i in range(0, 10**n) :
#	if list_all[i]%13 != 5 :
#		list_all[i] = 0
#		list_all[i] = str(list_all[i])
#	else :
#		list_all[i] = str(list_all[i])
#		list_all[i] = list_all[i].zfill(n)

#print('list_all=', list_all)





for i in range(len(list_all)) :
	list_all[i] = str(list_all[i])
	list_all[i] = list_all[i].zfill(n)
#for i in range(0, 10**n) :
#if list_all[i] != '0' :
	LIST = list(list_all[i])
	count = 0
	for i in range(len(S)) :
		if list_S[i] != '?' :
			if LIST[i] == list_S[i] :
				count = count + 1 
	if count == n - count_S :
		count_judge = count_judge + 1

print(count_judge%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    s = int(s)
    dp = np.roll(dp, s)
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    s = int(s)
    dp = np.concatenate([dp[13-s:13],dp[:13-s]])
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    s = int(s)
    dp = np.concatenate([dp[13-s:13],dp[:13-s]])
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    mod = 1000000007
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1
    k = 1
    cnt = 0
    for i in range(n):
        t = 0
        for j in range(10):
            if s[n-i-1]=="?":
                for l in range(13):
                    dp[i+1][(l+t)%13]+=dp[i][l]
                    if cnt%1000==0:
                        dp[i+1][(l+t)%13]%=mod
            elif int(s[n-i-1])==j:
                for l in range(13):
                    dp[i+1][(l+t)%13]+=dp[i][l]
                    if cnt%1000==0:
                        dp[i+1][(l+t)%13]%=mod
            t+=k
            if t>=13:
                t-=13
            cnt+=1
        k=t
    print(dp[n][5]%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
sa = np.array(list(s))
dp = np.zeros((N,M),dtype=np.int64)
dp[0,0] = 1
m = list(range(M))
t = list(range(10))

for i in range(len(s)):
    for j in m:
        for k in t:
            if sa[i] == "?" or sa[i] == str(k):
                dp[i+1,(j*10 +k) % M] += dp[i,j]
                dp[i+1,(j*10 +k) % M] %= MOD


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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    mod = 1000000007
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1
    k = 1
    for i in range(n):
        t = 0
        for j in range(10):
            if s[n-i-1]=="?":
                for l in range(13):
                    dp[i+1][(l+t)%13]+=dp[i][l]
                    dp[i+1][(l+t)%13]%=mod
            elif int(s[n-i-1])==j:
                for l in range(13):
                    dp[i+1][(l+t)%13]+=dp[i][l]
                    dp[i+1][(l+t)%13]%=mod
            t+=k
            t%=13
        k=t
    print(dp[n][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 1000000007
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
k = 1
for i in range(n):
    t = 0
    for j in range(10):
        if s[n-i-1]=="?":
            for l in range(13):
                dp[i+1][(l+t)%13]+=dp[i][l]
                dp[i+1][(l+t)%13]%=mod
        elif int(s[n-i-1])==j:
            for l in range(13):
                dp[i+1][(l+t)%13]+=dp[i][l]
                dp[i+1][(l+t)%13]%=mod
        t+=k
        t%=13
    k=t
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
for s in input():
  if s == '?':
    add = np.ones(10, dtype = np.int64)
  else:
    s = int(s)
    add = np.zeros(s+1, dtype=np.int64)
    add[-1] = 1
  dp = np.convolve(dp[move], add)
  dp[:len(dp) - 13] += dp[13:]
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
for s in input():
  prev = dp[move]
  dp = np.zeros(13, dtype=np.int64)
  if s == '?':
    add = np.ones(10, dtype = np.int64)
  else:
    s = int(s)
    add = np.zeros(s+1, dtype=np.int64)
    add[-1] = 1
  dp = np.convolve(prev, add)
  dp[:len(dp) - 13] += dp[13:]
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
qTable = [[(j * i) % 13 for j in range(13)] for i in range(11)]

S = input()

C, tC, qi = [1] + [0] * 12, [0] * 13,  1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = qTable[j][qi]
            for c in range(13):
                tC[(c + q) % 13] += C[c]
    else:
        q = qTable[int(S[-(i + 1)])][qi]
        for c in range(13):
            tC[(c + q) % 13] = C[c]

    qi = qTable[10][qi]
    for c in range(13):
        C[c] = tC[c] % MOD

print(C[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
for s in input():
  prev = dp[move]
  dp = np.zeros(13, dtype=np.int64)
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for x in add:
    dp[x:13] += prev[:13-x]
    dp[0:x] += prev[13-x:13]
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
for s in input():
  prev = dp[move]
  dp = np.zeros(26, dtype=np.int64)
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for x in add:
    dp[x:x+13] += prev
  dp[:13] += dp[13:]
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import re

S = input()

#print('S=', S)

list_S = list(S)

n = len(S)

#print('list_S', list_S)
#print('digit=', n)

count_S = 0

for i in range(len(S)) :
	if S[i] == '?' :
		count_S = count_S + 1 

#print('count_?=', count_S) 

list_all = [i for i in range(0, 10**n)]

#print('list_all=', list_all)

count_judge = 0

for i in list_all :
	if list_all[i]%13 != 5 :
		list_all[i] = 0
		list_all[i] = str(list_all[i])
	else :
		list_all[i] = str(list_all[i])
		list_all[i] = list_all[i].zfill(n)

#print('list_all=', list_all)

for i in range(0, 10**n) :
#	m = re.search(r'0', list[i])
#	if m :
	if list_all[i] != '0' :
#	if '0' in list[i] :
#	if match() 
#	List = list(list[i])
#	if '0' not in List :
		LIST = list(list_all[i])
#		print(count_judge)
		count = 0
		for i in range(len(S)) :
			if list_S[i] != '?' :
#				print(count_judge)
				if LIST[i] == list_S[i] :
					count = count + 1 
#					print(count_judge)
		if count == n - count_S :
			count_judge = count_judge + 1

print(count_judge%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

for s in input():
  prev = dp
  dp = np.zeros(13, dtype=np.int64)
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for x in add:
    dp[(np.arange(x,130,10)) % 13] += prev
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*(10**i) + j) % 13
            dp[i+1][amari] = (dp[i][j] + dp[i+1][amari]) % MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10 ** 9 + 7
S = input()

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

for s in S:
  prev = dp
  dp = np.zeros(13, dtype=np.int64)
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for x in add:
    dp[(np.arange(13) * 10 + x) % 13] += prev
  dp %= MOD
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
def main():
    S = input()
    N = len(S)-1
 
    if S[0] == '?':
        dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        dp[int(S[0])] = 1
 
    for i in range(1,N):
        dppre = dp
        dp = [0] * 13
 
        if S[i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[(j * 10 + k) % 13 ] += dppre[j]
        else:
            for j in range(13):
                dp[(j * 10 + int(S[i])) % 13 ] += dppre[j]
 
        for j in range(13):
            dp[j] %= MOD
 
    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

mul = 1
for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*mul + j) % 13
            dp[i+1][amari] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

    mul *= 10

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*(10**i) + j) % 13
            dp[i+1][amari] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
  M=10**9+7
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[(j-k)*9%13]for j in range(10))%M for k in range(13)]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = np.zeros((N,M),dtype=np.int64)
dp[0,0] = 1
m = list(range(M))
t = list(range(10))

for i in range(len(s)):
    for j in m:
        for k in t:
            if s[i] == "?" or s[i] == str(k):
                dp[i+1,(j*10 +k) % M] += dp[i,j]
                dp[i+1,(j*10 +k) % M] %= MOD


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

Submission status: Time Limit Exceeded

Solution code:
S = input()

C, qi = [1] + [0] * 12, 1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = (j * qi) % 13
            for c in range(13):
                tC[(c + q) % 13] += C[c]
        C = tC
    else:
        q, tC = (int(S[-(i + 1)]) * qi) % 13, [0] * 13
        for c in range(13):
            tC[(c + q) % 13] = C[c]
        C = tC
    qi = (qi * 10) % 13

print(C[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def main():
  d=[1]+[0]*12
  for c in input():
    d=[sum(d[(j-k)*9%13]for j in(range(10)if c>'9'else[int(c)]))%(10**9+7)for k in range(13)]
  print(d[5])
main()

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

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

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

for i in range(N):
    c = S[i]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*(10**i) + j) % 13
            dp[i+1][amari] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
N = 10**5
M = 13

s = input()
dp = np.zeros((N,M),dtype=np.int64)
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1,(j*10 +k) % M] += dp[i,j]
                dp[i+1,(j*10 +k) % M] %= MOD


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

Submission status: Time Limit Exceeded

Solution code:
def main():
  d=[1]+[0]*12
  for c in input():
    d=tuple(sum(d[(j-k)*9%13]for j in c<'?'and[int(c)]or range(10))%(10**9+7)for k in range(13))
  print(d[5])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  d=[1]+[0]*12
  for c in input():
    d=[sum(d[(j-k)*9%13]for j in c<'?'and[int(c)]or range(10))%(10**9+7)for k in range(13)]
  print(d[5])
main()

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()

DIV = 10**9 + 7
digit = 1
log = []

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log.append([int(t < 10) for t in range(13)])
        else:
            log.append([int(t == int(c)) for t in range(13)])
    else:
        log.append([0 for t in range(13)])
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in enumerate(log[i - 1]):
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt)
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in enumerate(log[i - 1]):
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt)
        log[i] = [v % DIV for v in log[i]]
    digit = (digit * 10) % 13

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

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7
s = input().strip()

num = 0
q_list = []
d = 1
for i in range(len(s) - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d = (d * 10) % 13

counts = [0] * 13
counts[0] = 1
counts_save = [0] * 13
for d in q_list:
	for i in range(13):
		counts_save[i] = counts[i] % M
	for n in range(1, 10):
		r = (d * n) % 13
		for m in range(13):
			counts[(r + m) % 13] += counts_save[m]

print(counts[(13 + 5 - num) % 13] % M)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


from functools import lru_cache


def main(): 
    S = SI()

    # 桁DP
    dp_table = [[0 for _ in range(13)] for _ in range(len(S))]

    # 最初の桁を見る。
    if S[0] == '?':
        for i in range(10):
            dp_table[0][i] = 1
    else:
        dp_table[0][int(S[0])] = 1

    # 以降の桁を見ていく。
    for digit in range(1, len(S)):
        if S[digit] == '?':
            for prev_res, comb in enumerate(dp_table[digit-1]):
                for x in range(10):
                    res = (prev_res*10+x)%13
                    dp_table[digit][res] = (dp_table[digit][res] + comb)%MOD

        else:
            for prev_res, comb in enumerate(dp_table[digit-1]):
                res = (prev_res*10+int(S[digit]))%13
                dp_table[digit][res] = (dp_table[digit][res] + comb)%MOD

    print(dp_table[len(S)-1][5])





main()

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()

DIV = 10**9 + 7
digit = 1
log = []

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log.append([int(t < 10) for t in range(13)])
        else:
            log.append([int(t == int(c)) for t in range(13)])
    else:
        log.append([0 for t in range(13)])
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in enumerate(log[i - 1]):
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt)
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in enumerate(log[i - 1]):
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt)
        
    digit = (digit * 10) % 13

print(log[len(s) - 1][5] % DIV)

Submission status: Time Limit Exceeded

Solution code:
""" dpはi桁,あまりj
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
MOD = 10**9+7

S = str(input())
S = S[::-1]
n = len(S)

dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1 #0を割ったあまりは0

q = 1 # はじめの1桁のときはあまりは1

# i桁目のあまりが何通りあるか
for i in range(1,n+1): # 「1-n」桁まで
  s = S[i-1]
  for j in range(13): # 13で割ったあまり
    
    if s == '?': # ?の場合は0-9を計算する
      for k in range(10):
        dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目 +=を忘れずに！
    else:
      k = int(s)
      dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目
  for m in range(13):
    dp[i][m] %= MOD
  q = (10*q)%13 # 「10^iをqで割ったあまり」

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

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()

DIV = 10**9 + 7
digit = 1
log = []

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log.append([int(t < 10) for t in range(13)])
        else:
            log.append([int(t == int(c)) for t in range(13)])
    else:
        log.append([0 for t in range(13)])
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in enumerate(log[i - 1]):
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt) % DIV
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in enumerate(log[i - 1]):
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt) % DIV
    digit = (digit * 10) % 13

print(log[len(s) - 1][5] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


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

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()

DIV = 10**9 + 7
digit = 1
log = {}

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log[0] = {t: int(t < 10) for t in range(13)}
        else:
            log[0] = {t: int(t == int(c)) for t in range(13)}
    else:
        log[i] = {t: 0 for t in range(13)}
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in log[i - 1].items():
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt) % DIV
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in log[i - 1].items():
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt) % DIV
    digit = (digit * 10) % 13

print(log[len(s) - 1][5] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
for s in S:
    p=[x for x in dp]
    dp=[0]*13
    if s=="?":
        a=range(10)
    else:
        a=[int(s)]
    for i in range(13):
        for x in a:
            dp[(10*i+x)%13]+=p[i]
    dp=[x%MOD for x in dp]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
import numpy as np
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ (b*i)%13 for i in range(10) ] )
#
dp= np.zeros( shape=(13),dtype=np.int64 )
dp[0] = 1
for i,c in enumerate(reversed(s)):
    tmp  = dp.copy()
    #
    if c=="?":
        bset = mmap[i%6][1:]
        for m in range(13):
            num= tmp[m]
            if num==0: continue
            for b in bset:
                idx= (m+b)%13
                dp[idx]= ( dp[idx] + num ) % MOD
    else:
        b= mmap[i%6][int(c)]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
#
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9 + 7)
M = 13

s = input()
dp = [0 for x in range(M)]
dp[0] = 1
ndp = [0 for x in range(M)]

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                ndp[(j*10 +k) % M] += dp[j]
                ndp[(j*10 +k) % M] %= MOD
    dp = ndp
    ndp = [0 for x in range(M)]

print(dp[5])

Submission status: Time Limit Exceeded

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

import sys
import numpy as np

s= sys.stdin.readline().strip()
n= len(s)
#
MOD=10**9+7
#
base = 1
dp = np.zeros( shape=(n+1,13),dtype=np.int64 )
dp[0][0] = 1
for i,c in enumerate(reversed(s)):
    prev= dp[i]
    now = dp[i+1]
    #
    if c=="?":
        for b in [ base*i for i in range(10) ]:
            for m,num in enumerate(prev):
                if num==0: continue
                idx= (m+b)%13
                now[idx]= now[idx]+num
        #
        for i in range(13): now[i] %= MOD
    else:
        b= base*int(c)
        for m in range(13):
            idx= (m+b)%13
            now[idx]= prev[m]
    #
    base = base*10
#
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
def main():
    S = input()
    N = len(S)-1
    dp = [[0] * 13  for _   in range(N)]
    

    if S[0] == '?':
        R = range(10)
    else:
        R = [int(S[0])]

    for i in R:
        dp[0][i] = 1

    for i in range(1,N):
        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]

        for j in range(13):
            for k in R:
                dp[i][(j * 10 + k) % 13 ] = (dp[i][(j * 10 + k) % 13 ] + dp[i-1][j]) 
        for j in range(13):
            dp[i][j] %= MOD
    
    print(dp[N-1][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# やりやすさのため、小さい桁からいけるように逆順にしておく
S=input()[::-1]
N=len(S)

# dp[i][j] := 下からi桁を考えた時，13で割ったあまりがjであるものの数
dp=list2d(N+1, 13, 0)
dp[0][0]=1
for i in range(N):
    for j in range(13):
        # ?だったら0~9を全て遷移させる
        if S[i]=='?':
            for k in range(10):
                # 桁を合わせる
                nxt=k*pow(10, i, 13)
                dp[i+1][(j+nxt)%13]+=dp[i][j]
                dp[i+1][(j+nxt)%13]%=MOD      
        else:
            # 決まっていたらその数字のみ遷移させる
            nxt=int(S[i])*pow(10, i, 13)
            dp[i+1][(j+nxt)%13]+=dp[i][j]
            dp[i+1][(j+nxt)%13]%=MOD
# 最終的にN桁終わって余り5の数が答え
print(dp[N][5])