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()
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
rank = 1
dp[0][0] = 1

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

    rank *= 10

ans = dp[len(S)][5] % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

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

    rank *= 10

ans = dp[len(S)][5] % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    s = input()
    if len(s) % 2 == 1:
        s_list = ['0']
    else:
        s_list = []
    s_list = s_list[:] + list(s)

    counts = [-1] * 13
    for i in range(0, len(s_list), 2):
        temp_counts = [0] * 13
        figure_len_mod = pow(10, i, 13)
        for j in range(100):
            temp_mod = (j * figure_len_mod) % 13
            j_list = list('{:02d}'.format((j)))
            if j_list[0] == s_list[-(1 + i + 1)] or s_list[-(1 + i + 1)] == '?':
                if j_list[1] == s_list[-(1 + i + 0)] or s_list[-(1 + i + 0)] == '?':
                    temp_counts[temp_mod] += 1

        next_counts = [0] * 13
        for idx, c in enumerate(counts):
            if c == -1:
                next_counts[idx] = temp_counts[idx]
            else:
                for t_idx, t_c in enumerate(temp_counts):
                    temp_mod = (idx + t_idx) % 13
                    count = c * t_c
                    next_counts[temp_mod] += count
        for idx in range(len(counts)):
            counts[idx] = next_counts[idx] % MOD

    print(counts[5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

dp = [[0,0,0,0,0,0,0,0,0,0,0,0,0] for i in range(len(S) + 2)]
INF = 10**9 + 7
for num, dig in enumerate(S):
    if num == 0:
        if dig == '?':
            dp[num] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
        else:
            dp[num] = [0,0,0,0,0,0,0,0,0,0,0,0,0]
            dp[num][int(dig)] = 1

    elif dig == '?':
        for j in range(10):
            for i in range(13):
                dp[num][(i * 10 + j) % 13] += dp[num - 1][i] % INF
                dp[num][(i * 10 + j) % 13] %= INF

    else:
        for i in range(13):
            dp[num][(i*10 + int(dig))%13] += dp[num - 1][i] % INF
            dp[num][(i * 10 + int(dig)) % 13] %= INF

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod_n = 10 ** 9 + 7
q_lis = []
for i, t_s in enumerate(s):
    if t_s == '?':
        q_lis.append(i)
len_s = len(s)
max_num = 10 ** len_s        
num = 5
cnt = 0
while num < max_num:
    s_num = str(num).zfill(len_s)
    for i in q_lis:
        s_num = s_num[:i] + '?' + s_num[i + 1:]
    if s_num == s:
        cnt += 1
        cnt = cnt % mod_n
    num += 13
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1

# i: i桁目
for i in range(1,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*(10**(i-1)) % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] += x
    else:
        jmod = int(S[-i])*(10**(i-1)) % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] += x

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
mod = 10**9 + 7
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.dot(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = ndp % mod

print(int(dp[5]))

Submission status: Time Limit Exceeded

Solution code:
def digits_parade(S: str)->int:
    MOD = 10**9 + 7
    DIV = 13
    # dp[i][j] = S の i 桁目までを利用してできる整数で 13 で割ったあまりが j になる組み合わせ
    dp = [[0] * DIV for _ in range(len(S)+1)]
    dp[0][0] = 1

    # digit: 10^n % 13 を計算するための変数
    digit = 1

    for i, c in enumerate(reversed(S)):
        if c == '?':
            for n in range(10):
                d = (n * digit) % DIV
                for j in range(DIV):
                    dp[i+1][(j+d) % DIV] += dp[i][j]
                    dp[i+1][(j+d) % DIV] %= MOD
        else:
            d = (int(c) * digit) % DIV
            for j in range(DIV):
                dp[i+1][(j+d) % DIV] += dp[i][j]
                dp[i+1][(j+d) % DIV] %= MOD

        digit = (digit * 10) % DIV

    return dp[len(S)][5]


if __name__ == "__main__":
    S = input()
    ans = digits_parade(S)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10**9 + 7
dp = [[0] * 13 for i in range(len(S)+1)]  # the number of ways to make a number with remainder j using the first i digits
dp[0][0] = 1
for i in range(len(S)):

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10**9 + 7
dp = [[0] * 13 for i in range(len(S)+1)]  # the number of ways to make a number with remainder j using the first i digit
dp[0][0] = 1
mod13 = [i*10 % 13 for i in range(13)]
for i in range(1, len(S) + 1):
    temp = [0] * 13
    for j, k in enumerate(mod13):
        temp[k] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

S = input().rstrip()

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

#print(dp)

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

#print(dp)
print((dp[len(S)][5])%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    dp=[0]*13
    if s[-1]=="?":
        dp=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**i %13
        ss0=s[n-i-1]
        if ss0!="?":
            dpnew = [ dp[(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dpnew = [sum( dp[(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
        dp=dpnew[:]
    print(dp[5])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

print(modlist[-2][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#d
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    dp=[[0]*13 for _ in range(n)]
    if s[-1]=="?":
        dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[0][int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**i %13
        ss0=s[n-i-1]
        if ss0!="?":
            dp[i] = [ dp[i-1][(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dp[i] = [sum( dp[i-1][(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
    print(dp[-1][5])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    dp=[[0]*13 for _ in range(n)]
    if s[-1]=="?":
        dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[0][int(s[-1])]=1
    
    for i in range(1,n):
        ss0=s[n-i-1]
        if ss0!="?":
            dp[i] = [ dp[i-1][(j-int(ss0)*10**i)%13] %mod for j in range(13)]
        else:
            dp[i] = [sum( dp[i-1][(j-k*10**i)%13] for k in range(10)) %mod for j in range(13) ]
    print(dp[-1][5])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    dp=[[0]*13 for _ in range(n)]
    if s[-1]=="?":
        dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[0][int(s[-1])]=1
    
    for i in range(1,n):
        ss=s[n-i-1:n]
    #     print(i,ss)
        ss0=ss[0]
        if ss0!="?":
            dp[i] = [ dp[i-1][(j-int(ss0)*10**i)%13] %mod for j in range(13)]
        else:
            dp[i] = [sum( dp[i-1][(j-k*10**i)%13] for k in range(10)) %mod for j in range(13) ]
    print(dp[-1][5])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp=[[0]*13 for _ in range(n)]
if s[-1]=="?":
    dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    dp[0][int(s[-1])]=1

for i in range(1,n):
    ss=s[n-i-1:n]
    ss0=ss[0]
    if ss0!="?":
        for j in range(13):
            dp[i][j] = dp[i-1][(j-int(ss0)*10**i)%13] %mod
    else:
        for j in range(13):
            dp[i][j] = sum( dp[i-1][(j-k*10**i)%13] for k in range(10)) %mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
dp = np.array([[0]*13]*(len(S)+1))
dp[0][0] = 1

for i,s in enumerate(S):
    if s == '?':
        for j in range(10):
            for ki in range(13):
                dp[i+1][(ki*10+j)%13] += dp[i][ki]

    else:
        for ki in range(13):
            dp[i+1][(ki*10+int(s))%13] += dp[i][ki]
    for j in range(13):
        dp[i+1][j] %= 10**9+7
    
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
dp = np.array([[0]*13]*(len(S)+1))
dp[0][0] = 1

for i,s in enumerate(S):
    if s == '?':
        for j in range(10):
            for ki in range(13):
                dp[i+1][(ki*10+j)%13] += dp[i][ki]
                dp[i+1][(ki*10+j)%13] %= 10**9+7
    else:
        for ki in range(13):
            dp[i+1][(ki*10+int(s))%13] += dp[i][ki]
            dp[i+1][(ki*10+int(s))%13] %= 10**9+7


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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
S = input()
LenS = len(S)
DP = [[0] * 13 for _ in range(LenS+1)]

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

for i in range(2,LenS+1):
    c = S[i-1]
    if c == '?':
        for n in range(10):
            for j in range(13):
                k = (10*j+n) % 13
                DP[i][k] += DP[i-1][j] 
                DP[i][k] %= MOD
    else:
        n = int(c)  
        for j in range(13):
            k = (10*j+n) % 13
            DP[i][k] = DP[i-1][j] 
            DP[i][k] %= MOD

print(DP[LenS][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s, p=13):
    s = s[::-1]
    n = len(s)
    a = np.zeros(p, dtype=int)
    b = np.zeros(p, dtype=int)
    if s[0] == "?":
        a[:10] = 1
    else:
        a[int(s[0])] = 1
    D = {str(i): [i] for i in range(10)}
    D["?"] = list(range(10))
    q = [(10**i) % p for i in range(6)]
    for i in range(1,n):
        b[:] = 0
        for s_i in D[s[i]]:
            for j in range(p):
                k = (j + s_i * q[i%6]) % p
                b[k] += a[j]
        a = b % MOD
    return a[5]

s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

S = input()
N = len(S)

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

mul = 1

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

  mul = mul * 10

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
MOD=10**9+7
dp=[[0 for i in range(13)] for j in range(2)]

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

i=1
for c in s[1:]:
  c = -1 if c=='?' else int(c)

  D=dp[i%2]
  S=dp[(i-1)%2]
  if c==-1:
    for k in range(13):
      for j in range(k*10,k*10+10):
        D[j%13]+=S[k]
  else:
    for k in range(13):
      D[(k*10+c)%13]+=S[k]

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

print(dp[(i-1)%2][5])

Submission status: Time Limit Exceeded

Solution code:
MOD = pow(10, 9) + 7
s = list(input())
s.reverse()
def main():

    dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
    if s[0] == "?":
        for i in range(10):
          dp[1][i] = 1
    else:
        dp[1][int(s[0])%13] = 1

    for i in range(2, len(s) + 1):
        for amari in range(13):
            if s[i-1] != "?":
                dp[i][(amari + int(s[i-1]) * pow(10, i-1, 13)) % 13] += (dp[i-1][amari])%MOD
            else:
                for val in range(10):
                    dp[i][(amari + val * pow(10, i - 1, 13)) % 13] += dp[i - 1][amari]%MOD
    print((dp[len(s)][5] %MOD ))

main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
MOD=10**9+7
dp=[[0 for i in range(13)] for j in range(2)]

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

i=1
for c in s[1:]:
  c = -1 if c=='?' else int(c)

  D=dp[i%2]
  S=dp[(i-1)%2]
  if c==-1:
    for j in range(10):
      for k in range(13):
        D[(k*10+j)%13]+=S[k]
  else:
    for k in range(13):
      D[(k*10+c)%13]+=S[k]

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

print(dp[(i-1)%2][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
MOD=10**9+7
dp=[[0 for i in range(13)] for j in range(2)]

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

i=1
for c in s[1:]:
  c = -1 if c=='?' else int(c)
  for k in range(13):
    dp[i%2][k]=0

  if c==-1:
    for j in range(10):
      for k in range(13):
        dp[i%2][(k*10+j)%13]+=dp[(i-1)%2][k]
  else:
    for k in range(13):
      dp[i%2][(k*10+c)%13]+=dp[(i-1)%2][k]

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

print(dp[(i-1)%2][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s, p=13):
    s = s[::-1]
    n = len(s)
    cur = np.zeros(p, dtype=np.uint64)
    if s[0] == "?":
        cur[:10] = 1
    else:
        cur[int(s[0])] = 1
    D = {str(i): [i] for i in range(10)}
    D["?"] = list(range(10))
    q = [(10**i) % p for i in range(6)]
    for i in range(1,n):
        next = np.zeros(p, dtype=np.uint64)
        for x in D[s[i]]:
            for j in range(p):
                k = (j + x * q[i%6]) % p
                next[k] += cur[j]
        cur = next % MOD
    return cur[5]

s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
S = input()
keta = len(S)
dp = [[0 for _ in range(13)] for _ in range(keta+1)]
dp[0][0] = 1
MOD = 10**9+7
for i in range(1,keta+1):
	if S[-i] != "?":
		n = int(S[-i])
		mod = n*(10**(i-1))%13
		for k in range(13):
			if k+mod <13:
				dp[i][k+mod] += dp[i-1][k]
				dp[i][k+mod] %= MOD
			else:
				dp[i][k+mod-13] += dp[i-1][k]
				dp[i][k+mod-13] %= MOD

	else:
		for j in range(10):
			mod = (j*(10**(i-1)))%13
			for k in range(13):
				if k+mod <13:
					dp[i][k+mod] += dp[i-1][k]
					dp[i][k+mod] %= MOD
				else:
					dp[i][k+mod-13] += dp[i-1][k]
					dp[i][k+mod-13] %= MOD

print(dp[keta][5])

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	s=input().rstrip().decode('utf-8')
	n=len(s)
	
	dp=[[0]*13 for _ in range(n+1)]
	dp[0][0]=1
	
	for i in range(1,n+1):
		now=s[i-1]
		if now=="?":
			for j in range(13):
				for k in range(10):
					dp[i][(10*j+k)%13]+=dp[i-1][j]
		else:
			k=int(now)
			for j in range(13):
				dp[i][(10*j+k)%13]+=dp[i-1][j]
		
		for j in range(13):
			dp[i][j]%=MOD
	
	print(dp[n][5])
	
	
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s, p=13):
    s = s[::-1]
    n = len(s)
    dp = np.zeros((n, p), dtype=int)
    if s[0] == "?":
        dp[0, :10] = 1
    else:
        dp[0, int(s[0])] = 1
    D = {str(i): [i] for i in range(10)}
    D["?"] = list(range(10))
    q = [(10**i) % p for i in range(6)]
    for i in range(1,n):
        for x in D[s[i]]:
            for j in range(p):
                k = (j + x * q[i%6]) % p
                dp[i, k] = (dp[i, k] + dp[i-1, j]) % MOD
    return dp[n-1, 5]

s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9 + 7
def solve(s, p=13):
    s = s[::-1]
    n = len(s)
    dp = np.zeros((n, p), dtype=int)
    if s[0] == "?":
        dp[0, :10] = 1
    else:
        dp[0, int(s[0])] = 1
    for i in range(1,n):
        if s[i] == "?":
            v = list(range(10))
        else:
            v = [int(s[i])]
        for x in v:
            for j in range(p):
                k = (j + x * (10**i)) % p
                dp[i, k] = (dp[i, k] + dp[i-1, j]) % MOD
    return dp[n-1, 5]

s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

mod = 10**9+7
mul = 1
dp[0][0] = 1

for i in reversed(range(len(s))):
    keta = len(s) - i - 1
    if s[i] == '?':
        for k in range(10):
            for j in range(13):
                amari = (j+k*(10**keta)) % 13
                #print(amari,i)
                dp[keta+1][amari] += dp[keta][j]
                dp[keta+1][amari] %= mod
    else:
        num = int(s[i])
        for j in range(13):
            amari = (j+(num*(10**keta))) % 13
            #print(keta,amari)
            dp[keta+1][amari] += dp[keta][j]
            dp[keta+1][amari] %= mod
    #mul = mul*10%13
            
print(dp[len(s)][5])
#print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

mod = 10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for d in range(N):
    if S[d] == '?':
        for i, j in product(range(13), range(10)): # '?' = j
            rem = ((10 * i) % 13 + j) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
    else:
        for i in range(13):
            rem = ((10 * i) % 13 + int(S[d])) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    temp = 10**(N-i-1)
    if S[i] == '?':
        for j, k in product(range(13), range(10)):
            rem = (k * temp) % 13
            target = (j + rem) % 13
            dp[i+1][target] += dp[i][j]
            dp[i+1][target] %= MOD
    else:
        rem = (int(S[i]) * temp) % 13
        for j in range(13):
            target = (j + rem) % 13
            dp[i+1][target] += dp[i][j]
            dp[i+1][target] %= MOD
print(dp[N][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    if s[i] == '?':
        for k in range(10):
            l = (k*10**c) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        l = (int(s[i])*10**c) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]    
            now[(j+l)%13] = now[(j+l)%13] % mod
    # print(now)
print(now[5])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
n = len(s)
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    if s[i] == '?':
        for k in range(10):
            l = (k*10**c) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        l = (int(s[i])*10**c) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]    
            now[(j+l)%13] = now[(j+l)%13] % mod
    # print(now)
print(now[5])

Submission status: Time Limit Exceeded

Solution code:
n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
modlist=[1,10,9,12,3,4]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=modlist[i%6]
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=(10**i)%13
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = np.zeros(N)
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
for i in range(len(S) - 1, -1, -1):
    nextDP = np.zeros(N)
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP
 
print(int(DP[5]))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    l = (j + r * k) % 13
                    dp[i][l] += dp[i - 1][j]
                    dp[i][l] %= MOD
        else:
            for j in range(13):
                l = (j + r * int(c)) % 13
                dp[i][l] += dp[i - 1][j]
                dp[i][l] %= MOD
print(dp[n - 1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
        for j in range(13):
            dp[i][j] %= MOD
print(dp[n - 1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
print(dp[n - 1][5] % MOD)

Submission status: Time Limit Exceeded

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

def key(l):
    for k in range(13):
        dp[i+1][(k * 10 + l) % 13] += dp[i][k]

for i in range(len(s)):
    if s[i] == '?':
        for j in range(10):
            key(j)
    else:
        key(int(s[i]))

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