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:
# -*- coding: utf-8 -*-

S = input()

MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]
NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]

R10 = range(10)
R13 = range(13)

for i,D in enumerate(S):
    C = -1
    if D != '?':
        C = int(D)
    #end if
    for N in R10:
        if C >= 0 and C != N:
            continue
        for M in R13:
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    for M in R13:
        MOD[M] = NMOD[M]%1000000007
        NMOD[M] = 0
    #end for
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

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

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

Submission status: Time Limit Exceeded

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

S = input()
Symbol = list(S)
MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]
NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]

R10 = range(10)
R13 = range(13)

for D in Symbol:
    C = -1
    if D != '?':
        C = int(D)
    #end if
    for N in R10:
        if C >= 0 and C != N:
            continue
        for M in R13:
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    for M in R13:
        MOD[M] = NMOD[M]%1000000007
        NMOD[M] = 0
    #end for
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

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

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

Submission status: Time Limit Exceeded

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

S = input()
Symbol = list(S)
MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]

R10 = range(10)
R13 = range(13)


for D in Symbol:
    NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]
    for N in R10:
        if D != '?' and int(D) != N:
            continue
        #end if
        for M in R13:
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    for M in R13:
        MOD[M] = NMOD[M]%1000000007
    #end for
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

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

S = input()
Symbol = list(S)
MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]

for D in Symbol:
    NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]
    for N in range(10):
        if D != '?' and int(D) != N:
            continue
        #end if
        for M in range(13):
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    for M in range(13):
        MOD[M] = NMOD[M]%1000000007
    #end for
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

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

S = input()
Symbol = list(S)
MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]

for D in Symbol:
    NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]
    for N in range(10):
        if D != '?' and int(D) != N:
            continue
        #end if
        for M in range(13):
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    MOD = list(map(lambda x:x%1000000007,NMOD))
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [0] * 13
dp[0] = 1

for i, x in enumerate(s):
    next_dp = [0] * 13
    if x == -1:
        for j in range(10):
            for ki in range(13):
                next_dp[(ki * 10 + j) % 13] += dp[ki]
    else:
        for ki in range(13):
                next_dp[(ki * 10 + x) % 13] += dp[ki]
    dp = [k % MOD for k in next_dp]

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [0] * 13
dp[0] = 1

for i, x in enumerate(s):
    next_dp = [0] * 13
    for j in range(10):
        if (x == -1) or (x == j):
            for ki in range(13):
                next_dp[(ki * 10 + j) % 13] += dp[ki]
    dp = [k % MOD for k in next_dp]

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = list(S)
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
from operator import add
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] += dp[i]
    
    for n in nums:
        x = n*dig % 13
        tmp = list(map(add, tmp, dp[13-x:]+dp[:13-x]))
    dp = tmp
    dig = dig * 10 % 13
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
q = len(origin)
from operator import add
for p in range(q):
    s = origin[q-p-1]
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] += dp[i]
    
    for n in nums:
        x = n*dig % 13
        tmp = list(map(add, tmp, dp[13-x:]+dp[:13-x]))
    dp = tmp
    dig = dig * 10 % 13
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
from operator import add
for p in range(len(origin)):
    s = origin[len(origin)-p-1]
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] += dp[i]
    
    for n in nums:
        x = n*dig % 13
        tmp = list(map(add, tmp, dp[13-x:]+dp[:13-x]))
    dp = tmp
    dig = dig * 10 % 13
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
from operator import add
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] += dp[i]
    
    for n in nums:
        x = n*dig % 13
        tmp = list(map(add, tmp, dp[13-x:]+dp[:13-x]))
    dp = tmp
    dig = dig * 10 % 13
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
from operator import add
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] += dp[i]
    
    for n in nums:
        x = n*dig % 13
        tmp = list(map(add, tmp, dp[13-x:]+dp[:13-x]))
    dp = tmp
    dig = dig * 10
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for i in range(13):
        for n in nums:
            tmp[(n*dig%13+i)%13] += dp[i]
    dp = tmp
    dig = dig * 10 % 13
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] = tmp[(n*dig+i)%13] + dp[i]
    for n in nums:
        n *= dig
        for i in range(13):
            tmp[(n+i)%13] += dp[i]
    dp = tmp
    dig = dig * 10
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for i in range(13):
        for n in nums:
            #tmp[(n*dig+i)%13] += dp[i]
            tmp[pow(n*dig+i, 1, 13)] += dp[i]
    dp = tmp
    dig = dig * 10
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for i in range(13):
        for n in nums:
            tmp[(n*dig+i)%13] += dp[i]
    dp = tmp
    dig = dig * 10 % 13
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    MOD = 1000000007
    s = input()
    n = len(s)

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

    for i, c in enumerate(s):
        if c == "?":
            cn = -1
        else:
            cn = int(c)

        dp.append([0 for _ in range(13)])
        for j in range(10):
            if cn != -1 and cn != j: continue
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i + 1][j] %= MOD
    result = dp[n][5]

    print(result)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for i in range(13):
        for n in nums:
            tmp[(n*dig+i)%13] += dp[i]
    dp = tmp
    dig *= 10
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

s= [int(x) if x != "?" else -1 for x in input()]

n=len(s)
T=13
dp=[0]*T
c=s[n-1]
if (c!=-1):
	dp[c]=1
else:
	for i in range(10):dp[i]=1
mul = 10
for i in range(2,n+1):
	c=s[n-i]
	nextdp = [0] * T
	if (c==-1):
		for k in range(10):
			for j in range(T):
				nextdp[(k * mul + j)%T] += dp[j]
				nextdp[(k * mul + j)%T] %= mod
	else:
		k = c
		for j in range(T):
			nextdp[(k * mul + j) % T] += dp[j]
			nextdp[(k * mul + j) % T] %= mod
	mul *= 10
	mul %= T
	dp = nextdp


print (dp[5]%mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
for n in reversed(origin):
    next_dp = [0] * 13
    if n == '?':
        for n in range(10):
            mod = (n * dig)
            for i in range(13):
                next_dp[(i+mod)%13]+=dp[i]
    else:
        mod = (int(n) * dig)
        for i in range(13):
            next_dp[(i+mod)%13]+=dp[i]
    dp = next_dp[:]
    dig = dig * 10
    
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
x={}
x_v=0
count=0
for i,j in enumerate(S):
    if j=="?":
        continue
    else:
        x[len(S)-i-1]=j
for m in x.keys():
    x_v+=int(x[m])*(10**m)
for k in range(10**(len(S))):
    k_l=list(str(k))
    a=0
    b=[]
    c=[]
    for key in x.keys():
        if key>=len(k_l):
            continue
        else:
            b.append( k_l[-key-1]=="0" )
            c.append(1)
    if b==c:
        for n in range(len(k_l)):
            a+=int(k_l[-n-1])*(10**n)
        a+=x_v
        if a%13==5:
            count+=1
    else:
        continue
print(count%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

from operator import add

dig = 1
for n in reversed(origin):
    next_dp = [0] * 13
    if n == '?':
        for n in range(10):
            mod = (n * dig) % 13
            for i in range(13):
                next_dp[(i+mod)%13]+=dp[i]
    else:
        mod = (int(n) * dig) % 13
        for i in range(13):
            next_dp[(i+mod)%13]+=dp[i]
    dp = next_dp[:]
    dig = dig * 10
    
ans = dp[5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

S = list(input())
S = ['?' for i in range(10**4)]
hatena = S.count('?')
hatena_list = [len(S)-1-i for i, x in enumerate(S) if x == '?']

l = [[0]*13 for _ in range(hatena+1)]

SS = copy.deepcopy(S)
for i in range(len(S)):
    if SS[i] == '?':
        SS[i] = '0'
SS_13 = int(''.join(SS))%13
l[0][SS_13] = 1

def function(x):
    if x<0:
        x = 13+x
    return x

for i in range(1,hatena+1):
    s = hatena_list[i-1]
    for j in range(0,10):
        SS_13 = 10**s *j %13
        for k in range(0,13):
            l[i][k] += l[i-1][function(k-SS_13)] % 1000000007
            l[i][k] %= 1000000007
        
print(l[-1][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

for i in range(1,len(s)):
  c = -1 if s[i]=='?' else int(s[i])
  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
    
print(dp[(len(s)-1)%2][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

from operator import add

for dig, n in enumerate(reversed(origin)):
    dig = 10 ** dig
    next_dp = [0] * 13
    if n == '?':
        for n in range(10):
            mod = (n * dig) % 13
            for i in range(13):
                next_dp[(i+mod)%13]+=dp[i]
    else:
        mod = (int(n) * dig) % 13
        for i in range(13):
            next_dp[(i+mod)%13]+=dp[i]
    dp = next_dp[:]
    
ans = dp[5] % (10**9+7)
print(ans)

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

for i in range(1,len(s)):
  c = -1 if s[i]=='?' else int(s[i])
  for k in range(13):
    dp[i%2][k]=0
  for j in range(10):
    if c!=-1 and c!=j:
      continue
    for k in range(13):
      dp[i%2][(k*10+j)%13]+=dp[(i-1)%2][k]
  for j in range(13):
    dp[i%2][j]%=MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys
S=input()
start=pow(10,int(len(S)-1))
end=pow(10,int(len(S)))-1

cnt=0

for i in range(5,end,13):
    clear=1
    input=str(i).zfill(len(S))
    
    for j in range(int(len(S))):
        
      if S[j:j+1] != input[j:j+1] and S[j:j+1] != "?":
        clear=0
        break
    if clear==1:
      cnt=cnt+1
      
print(cnt%(pow(10,7)-7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

origin = S
now_mod = 0
for dig, n in enumerate(reversed(origin)):
    if n == '?':
        pass
    else:
        now_mod += int(n)*(10**(dig)) % 13
now_mod = now_mod % 13

dp = [[0] * 13]
dp[0][now_mod] = 1

idx = 0
for dig, n in enumerate(reversed(origin)):
    if n == '?':
        dp.append([0] * 13)
        pre_idx = idx
        idx += 1
        for n in range(10):
            now_mod = int(n)*(10**(dig)) % 13
            for i, m in enumerate(dp[pre_idx]):
                dp[idx][(i+now_mod)%13] += m
    else:
        pass
        #now_mod = int(n)*(10**(dig)) % 13
        #for i, m in enumerate(dp[pre_idx]):
        #    dp[idx][(i+now_mod)%13] += m
            
print(dp[idx][5] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

import sys
sys.setrecursionlimit(10000)

origin = S

dp = [[0] * 13]
dp[0][0] = 1

idx = 0
for dig, n in enumerate(reversed(origin)):
    dp.append([0] * 13)
    pre_idx = idx
    idx += 1
    
    if n == '?':
        for n in range(10):
            now_mod = int(n)*(10**(dig)) % 13
            for i, m in enumerate(dp[pre_idx]):
                dp[idx][(i+now_mod)%13] += m
    else:
        now_mod = int(n)*(10**(dig)) % 13
        for i, m in enumerate(dp[pre_idx]):
            dp[idx][(i+now_mod)%13] += m
            
print(dp[idx][5] % (10**9+7))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

S = S[::-1]
static = 0
strg = ""
for i,s in enumerate(S):
    if s != "?":
        s = int(s)
        static += s*(10**i)
        strg += "0"
    else:
        strg += "?"
mod = static%13

dp = [0]*13
dp[mod] = 1
for i,s in enumerate(strg):
    new = [0]*13
    if s == "?":
        for j in range(10):
            m = (j*(10**i))%13
            for k in range(13):
                new[k] += dp[k-m]
        for j in range(13):
            dp[j] = new[j]%MOD
print(dp[5])

Submission status: Time Limit Exceeded

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

S = S[::-1]
static = 0
strg = ""
for i,s in enumerate(S):
    if s != "?":
        s = int(s)
        static += s*(10**i)
        strg += "0"
    else:
        strg += "?"
mod = static%13

dp = [0]*13
dp[mod] = 1
for i,s in enumerate(strg):
    new = [0]*13
    if s == "?":
        for j in range(10):
            m = (j*(10**i))%13
            for k in range(13):
                new[k] += dp[k-m]
                new[k] %= MOD
        dp = new
print(dp[5])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import re
number=input()
number=number.replace("?",".",100000)
length=len(number)
i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    checklength=len(checknum)
    if checklength<length:
        while len(checknum)!=length:
            checknum="0"+checknum
 
    if len(checknum)==length:
        m=re.match(number,checknum)
        if m:
            sumnum+=1
            sumnum=sumnum%1000000007
    
            
    if len(checknum)>length:
        break
    i+=1
    
print(sumnum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10**9+7
p = list(input())
# p = list("?"*10**5)

# アルゴリズム
dp = np.zeros((10**5 + 1, 13), dtype=int)
dp[0][0] = 1
idx = 1
for key in p:
    
    if key == "?":
        for i in range(10):
            for j in range(13):
                dp[idx][(j * 10 + i) % 13] += dp[idx-1][j]
                dp[idx][(j * 10 + i) % 13] %= mod
    else:
        
        for j in range(13):
            dp[idx][(j * 10 + int(key)) % 13] += dp[idx-1][j]
            dp[idx][(j * 10 + int(key)) % 13] %= mod

    idx += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10**9+7
# p = list(input())
p = list("?"*10**4)

# アルゴリズム
dp = np.zeros((10**5, 13), dtype=int)
dp[0][0] = 1
idx = 1
for key in p:
    
    if key == "?":
        for i in range(10):
            for j in range(13):
                dp[idx][(j * 10 + i) % 13] += dp[idx-1][j]
                dp[idx][(j * 10 + i) % 13] %= mod
    else:
        
        for j in range(13):
            dp[idx][(j * 10 + int(key)) % 13] += dp[idx-1][j]
            dp[idx][(j * 10 + int(key)) % 13] %= mod

    idx += 1

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

Submission status: Time Limit Exceeded

Solution code:
#数字はnumberに格納
number=input()
length=len(number)


#調整のための数字
sizemin=1000000007

#まずはからのDPリストを用意
dp=[[0 for i in range(13)] for j in range(length)]

#1桁目の情報を入力
if number[-1]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    dp[0][int(number[-1])]=1

#１０〜９０の、13modリストを作る
modlist=[(i*10)%13 for i in range(10)]


        
#二桁目からの情報を更新していく。
for n in range(length-1):
    #n桁目の情報があれば、次のようにn+1行目を更新。

    #n+1のくらいの数をchecknumとする
    checknum=number[-1*(n+1)-1]
#     print(checknum)

    #n+1の位が整数であれば
    if checknum!="?":
        
        #n[m]の値をn+1[m+(その整数)]にすればいい
        for m in range(13):
            dp[n+1][(m+modlist[int(checknum)])%13]=dp[n][m]
#         print(dp)
        
        
        
        
        
    #n+1のくらいが？の時
    else:
    #？が０〜９までの可能性を全て試す  
    
        for checknum in range(10):
            for m in range(13):
                dp[n+1][(m+modlist[int(checknum)])%13]=(dp[n+1][(m+modlist[int(checknum)])%13]+dp[n][m])%sizemin
#             print(dp)

    #modlistを更新
    modlist=[(j*10)%13 for j in modlist]


print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10**9+7
p = list(input())
# p = list("?"*10**4)

# アルゴリズム
dp = np.zeros((10**5, 13), dtype=int)
dp[0][0] = 1
mul = 1
idx = 1
for key in reversed(p):
    
    if key == "?":
        for i in range(10):
            for j in range(13):
                dp[idx][(j + i * mul) % 13] += dp[idx-1][j]
                dp[idx][(j + i * mul) % 13] %= mod
    else:
        
        for j in range(13):
            dp[idx][(j + int(key) * mul) % 13] += dp[idx-1][j]
            dp[idx][(j + int(key) * mul) % 13] %= mod

    mul *= 10
    idx += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10**9+7
# p = list(input())
p = list("?"*10**4)

# アルゴリズム
dp = np.zeros((10**5, 13), dtype=int)
dp[0][0] = 1
mul = 1
idx = 1
for key in reversed(p):
    
    if key == "?":
        for i in range(10):
            for j in range(13):
                dp[idx][(j + i * mul) % 13] += dp[idx-1][j]
                dp[idx][(j + i * mul) % 13] %= mod
    else:
        
        for j in range(13):
            dp[idx][(j + int(key) * mul) % 13] += dp[idx-1][j]
            dp[idx][(j + int(key) * mul) % 13] %= mod

    mul *= 10
    idx += 1

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

Submission status: Time Limit Exceeded

Solution code:
x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]
S = S[::-1]

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

dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        digit_r = ((10 ** i) * j) % 13

        for k in range(13):
            r = (digit_r + k) % 13
            dp[i + 1][r] += dp[i][k] % x

print(int(dp[-1][5] % x))

Submission status: Time Limit Exceeded

Solution code:
x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]
S = S[::-1]

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

dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        digit_r = ((10 ** i) * j) % 13

        for k in range(13):
            r = (digit_r + k) % 13
            dp[i + 1][r] += dp[i][k]

    dp[i + 1][r] %= x

print(int(dp[-1][5] % x))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]
S = S[::-1]

r = np.zeros((13,))
new_r = np.zeros((13,))

r[0] = 1

# i : 桁数
for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        digit_r = ((10 ** i) * j) % 13

        for k in range(13):
            new_r[(digit_r + k) % 13] += r[k]

    new_r %= x

    r = new_r
    new_r = np.zeros((13,))

print(int(r[5] % x))

Submission status: Time Limit Exceeded

Solution code:
s=input()
M=10**9+7
import numpy as np
dp=np.zeros((len(s)+1,13),dtype="int64")
dp[0][0]=1
for i in range(-1,-len(s)-1,-1):
    dp[-i-1]%=M
    if s[i]!="?":
        a=(int(s[i])*(10**(-i-1)))%13
        for j in range(13):
            dp[-i][(j+a)%13]=dp[-i-1][j]
    elif s[i]=="?":
        dp[-i]=dp[-i-1]
        for k in range(1,10):
            a=k*(10**(-i-1))%13
            for j in range(13):
                dp[-i][(j+a)%13]+=(dp[-i-1][j])
print(dp[-1][5]%M)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
MOD = 1e9 + 7
dp = [[0] * 13 for _ in range(n)]
for i in range(10):
	if s[0] == "?":
		dp[0][i] = 1
	else:
		cur = ord(s[0]) - ord("0")
		dp[0][cur] = 1
for i in range(1, n):
	if s[i] != "?":
		cur = ord(s[i]) - ord("0")
		for j in range(13):
			dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
	else:
		for j in range(13):
			for cur in range(10):
				dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
#print(dp)
print(int(dp[n - 1][5] % MOD))

Submission status: Time Limit Exceeded

Solution code:
import itertools
S = input()[::-1]
mod = 10**9 + 7
A = [0] * 13
N = 0
for i, v in enumerate(S):
    p = pow(10, i, 13)
    if v == '?':
        A[p] += 1
    else:
        N += int(v) * p
        N %= 13
dp = [0] * 13
dp[N] = 1
for i, v in enumerate(A):
    for _ in range(v):
        dp_old = dp[:]
        for j, k in itertools.product(range(1, 10), range(13)):
            x = (j * i + k) % 13
            dp[x] += dp_old[k]
            dp[x] %= mod
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 1000000007


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

dp[0][0] = 1

for i in range(len(s)):
    if s[len(s)-i-1] != "?":
        temp = int(s[len(s)-i-1])*(10**i) % 13
        for j in range(13):
            dp[i+1][j] = dp[i][(j-temp+13)%13]
            dp[i+1][j] %= mod

    else:
        amari = [(t*(10**i))%13 for t in range(10)]
        for j in range(13):
            for a in amari:
                dp[i+1][j] += dp[i][(j-a+13)%13]
                dp[i+1][j] %= mod
                
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


S = input().strip()

MOD = 10 ** 9 + 7

N = len(S)
DP = np.zeros((N+1, 13))
DP[0, 0] = 1

for _i, s in enumerate(S):
    i = _i + 1

    if s == '?':
        candidate = range(10)
    else:
        candidate = [int(s)]

    for j in range(13):
        for c in candidate:
            m = (j * 10 + c) % 13
            DP[i, m] += DP[i-1, j]
    DP[i] %= MOD

print(int(DP[-1, 5]))

Submission status: Time Limit Exceeded

Solution code:
sentence = input()
len_sentence = len(sentence)
total_number = [0 for _ in range(13)]
sentence = sentence[::-1]
present_remain = 1  # 1のときのあまり
for i, number_str in enumerate(sentence):
    if number_str == '?':
        total_number_list = [0 for _ in range(13)]
        remain_list = []
        for number in range(10):
            remain = (number * present_remain) % 13
            # remain = (number * 10 ** i) % 13
            remain_list.append(remain)
            if i == 0:
                total_number_list[remain] = 1
            else:
                for j in range(13):
                    total_number_list[(j+remain)%13] += total_number[j]
        total_number = total_number_list
        for j in range(13):
            total_number[j] = total_number[j] % (10 ** 9 + 7)
    else:
        number = int(number_str)
        # remain = (number * 10**i) % 13
        remain = (number * present_remain) % 13
        if i == 0:
            total_number[remain] = 1
        else:
            total_number_list = [0 for _ in range(13)]
            for j in range(13):
                total_number_list[(j + remain) % 13] += total_number[j]
            total_number = total_number_list
            # total_number = roll(remain, total_number)
    # for j in range(13):
    #     total_number[j] = total_number[j] % (10**9 + 7)
    present_remain = (present_remain * 10) % 13  # 1のときのあまり
print(total_number[5])

Submission status: Time Limit Exceeded

Solution code:
import re
number=input()
number=number.replace("?",".",100000)
length=len(number)
i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    checklength=len(checknum)
    if checklength<length:
        while len(checknum)!=length:
            checknum="0"+checknum

    if len(checknum)==length:
        m=re.match(number,checknum)
        if m:
            sumnum+=1
            sumnum=sumnum%1000000007
    
            
    if len(checknum)>length:
        break
    i+=1
    
print(sumnum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10**9+7
p = list(input())
# p = list("?"*10**4)

# アルゴリズム
dp = np.zeros(13, dtype=int)
dp[0] = 1
mul = 1
for key in reversed(p):
    new_dp = np.zeros(13, dtype=int)
    if key == "?":
        for i in range(10):
            for j in range(13):
                new_dp[(j + i * mul) % 13] += dp[j]
                new_dp[(j + i * mul) % 13] %= mod
    else:
        
        for j in range(13):
            new_dp[(j + int(key) * mul) % 13] += dp[j]
            new_dp[(j + int(key) * mul) % 13] %= mod
    dp = new_dp.copy()
    mul *= 10

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10**9+7
# p = list(input())
p = list("?"*10**4)

# アルゴリズム
dp = np.zeros(13, dtype=int)
dp[0] = 1
mul = 1
for key in reversed(p):
    new_dp = np.zeros(13, dtype=int)
    if key == "?":
        for i in range(10):
            for j in range(13):
                new_dp[(j + i * mul) % 13] += dp[j]
                new_dp[(j + i * mul) % 13] %= mod
    else:
        
        for j in range(13):
            new_dp[(j + int(key) * mul) % 13] += dp[j]
            new_dp[(j + int(key) * mul) % 13] %= mod
    dp = new_dp.copy()
    mul *= 10

print(dp[5])