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

P = 10**9+7
LENGTH = len(S)

"""dp[i][j] -> あり得る全ての上からi+1桁目までの数を13で割った余りが j となる状態数"""
dp = [[0 for i in range(13)] for j in range(LENGTH)]

if S[0]=='?':
    for j in range(10):
        dp[0][j]+=1
else:
    dp[0][int(S[0])]+=1

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

print(dp[LENGTH-1][5]%P)

Submission status: Time Limit Exceeded

Solution code:
S = input()

d = [i*10%13 for i in range(13)]

if S[0]=="?":
  res=[[1,1,1,1,1,1,1,1,1,1,0,0,0]]
else:
  res=[[0 if i!=int(S[0]) else 1 for i in range(13) ]]

for i in range(1,len(S)): #N
  res.append([0 for i in range(13)])
  if S[i]=="?":
    for j in range(13): #N*13
      for k in range(10): #N*13*10
        res[i][(d[j]+k)%13]+=res[i-1][j]
  else:
    for j in range(13):
      res[i][(d[j]+int(S[i]))%13]+=res[i-1][j]
      
print(res[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

d = [i*10%13 for i in range(13)]

if S[0]=="?":
  res=[[1,1,1,1,1,1,1,1,1,1,0,0,0]]
else:
  res=[[0 if i!=int(S[0]) else 1 for i in range(13) ]]

for i in range(1,len(S)):
  res.append([0 for i in range(13)])
  if S[i]=="?":
    for j in range(13):
      for k in range(10):
        res[i][(d[j]+k)%13]+=res[i-1][j]
  else:
    for j in range(13):
      res[i][(d[j]+int(S[i]))%13]+=res[i-1][j]
      
print(res[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# 解説YouTubeを参考（写経）
S = input()
N = 13
dp = [0 for _ in range(N)]
dp[0] = 1

mod = 1e9+7
mul = 1
for i in range(len(S)-1, -1, -1):
  nextDP = [0 for _ in range(N)]
  c = S[i]
  if c=="?":
    for k in range(10):
      for j in range(N):
        nextDP[(k*mul + j)%N] += dp[j]
        nextDP[(k*mul + j)%N] %= mod  
  else:
    k = int(c)
    for j in range(N):
      nextDP[(k*mul + j)%N] += dp[j]
      nextDP[(k*mul + j)%N] %= mod  
    
  mul *= 10
  mul %= N
  dp = nextDP
print(int(dp[5]))

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
n=len(s)
mod=10**9 + 7
dp=[[0]*(13) for i in range(n)]

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

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

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
n=len(s)
mod=10**9 + 7
dp=[[0]*(13) for i in range(n)]

saki=[[0]*10 for i in range(n)]
for i in range(10):
    saki[0][i]=i
    for j in range(n-1):
        saki[j+1][i]=saki[j][i]*10%13

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

for i in range(n-1):
    if s[n-2-i]=='?':
        for j in range(13):
            if dp[i][j]>0:
                for k in range(10):
                    dp[i+1][(j+saki[i+1][k])%13]+=dp[i][j]%mod
    else:
        for j in range(13):
            if dp[i][j]>0:
                dp[i+1][(j+saki[i+1][int(s[n-2-i])])%13]+=dp[i][j]%mod
print(dp[n-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
n=len(s)
mod=10**9 + 7
dp=[[0]*(13) for i in range(n)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from functools import lru_cache
# 上がうまく使えない場合、以下を使う(僕はうまくいかなかったのでこっちを使った)
# from functools32 import lru_cache

@lru_cache(maxsize=None)
def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros(13,dtype=np.int)
    dp[0]=1

    for i in range(N):
        temp=np.zeros(13,dtype=np.int)
        if S[i]=="?":
            for s in range(10):
                    A = [(s*(10**i)+j)%13 for j in range(13)]
                    temp[A] += dp[:]
        else:
            s=int(S[i])
            A = [(s*(10**i)+j)%13 for j in range(13)]
            temp[A] += dp[:]
        dp = temp
        # print()
        dp[:] %= MOD
    res = dp[5]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
# 上がうまく使えない場合、以下を使う(僕はうまくいかなかったのでこっちを使った)
# from functools32 import lru_cache

@lru_cache(maxsize=None)

def main():
    MOD=10**9+7

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

    for i in range(N):
        if S[i]=="?":
            for s in range(10):
                for j in range(13):
                    dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                    dp[i+1][(s*(10**i)+j) % 13] %= MOD
        else:
            s=int(S[i])
            for j in range(13):
                dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                dp[i+1][(s*(10**i)+j) % 13] %= MOD
    print(dp[N][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  MOD = 10**9 + 7
  S = input()

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

  a = [i%13 for i in range(130)]
  b = []
  for i in range(10):
      for j in range(13):
          b.append((j*10+i)%13)

  for s in S:
      dp[1] = 0
      if s == '?':
          for i, j in zip(b, a):
              dp[1][i] += dp[0][j] 
              dp[1][i] %= MOD
      else:
          for i in range(13):
              dp[1][(i*10+int(s))%13] += dp[0][i]

      dp[0] = dp[1] % MOD
  print(dp[1][5])
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

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

    for i in range(N):
        if S[i]=="?":
            for s in range(10):
                for j in range(13):
                    dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                    dp[i+1][(s*(10**i)+j) % 13] %= MOD
        else:
            s=int(S[i])
            for j in range(13):
                dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                dp[i+1][(s*(10**i)+j) % 13] %= MOD
    print(dp[N][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros(13,dtype=np.int)
    dp[0]=1
    for i in range(N):
        temp=np.zeros(13,dtype=np.int)
        if S[i]=="?":
            for s in range(10):
                    A = [(s*(10**i)+j)%13 for j in range(13)]
                    temp[A] += dp[:]
        else:
            s=int(S[i])
            A = [(s*(10**i)+j)%13 for j in range(13)]
            temp[A] += dp[:]
        dp = temp
        # print()
        dp[:] %= MOD
    res = dp[5]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros(13,dtype=np.int)
    dp[0]=1
    for i in range(N):
        temp=np.zeros(13,dtype=np.int)
        if S[i]=="?":
            for s in range(10):
                for j in range(13):
                    # A = [(s*(10**i)+j)%13 ]
                    temp[(s*(10**i)+j)%13] += dp[j]
        else:
            s=int(S[i])
            for j in range(13):
                temp[(s*(10**i)+j)%13] += dp[j]
        dp = temp
        # print()
        dp[:] %= MOD
    res = dp[5]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
S = input()
dp = [0] * 13
dp[0] = 1

for s in S:
    next_dp = [0] * 13
    if s == '?':
        for i in range(10):
            for j in range(13):
                next_dp[(j*10+i)%13] += dp[j]
    else:
        for i in range(13):
            next_dp[(i*10+int(s))%13] += dp[i]
            
    for i in range(13):
        dp[i] = next_dp[i] % MOD
    
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros((N+1,13),dtype=np.int)
    dp[0,0]=1

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

        dp[i+1,:] %= MOD

    res = dp[N,5]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros((N+1,13),dtype=np.int)
    dp[0,0]=1

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

    res = dp[N,5]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros((N+1,13),dtype=np.int)
    dp[0,0]=1

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

    res = dp[N,5]
    print(res%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros((N+1,13),dtype=np.int32)
    dp[0,0]=1

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

    res = dp[N,5]
    print(res%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    S = input()
    S = S[::-1]
    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 s in range(10):
                for j in range(13):
                    dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                    dp[i+1][(s*(10**i)+j) % 13] %= MOD
        else:
            s=int(S[i])
            for j in range(13):
                dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                dp[i+1][(s*(10**i)+j) % 13] %= MOD
    print(dp[N][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    MOD=10**9+7

    S = input()
    S = S[::-1]
    N = len(S)
    dp=np.zeros((N+1,13),dtype=np.int)
    dp[0,0]=1

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

    res = dp[N,5]
    print(res%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

S = input()
S = S[::-1]
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 s in range(10):
            for j in range(13):
                dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
                dp[i+1][(s*(10**i)+j) % 13] %= MOD
    else:
        s=int(S[i])
        for j in range(13):
            dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
            dp[i+1][(s*(10**i)+j) % 13] %= MOD
print(dp[N][5])

Submission status: Time Limit Exceeded

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

S = input()
S = S[::-1]
N = len(S)
dp=np.zeros((N+1,13),dtype=np.int)
dp[0,0]=1

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

res = dp[N,5]
print(res%MOD)

Submission status: Time Limit Exceeded

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

S = input()
S = S[::-1]
N = len(S)
dp=np.zeros((N+1,13),dtype=np.int)
dp[0,0]=1

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

res = dp[N,5]
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10**9+7

amari = np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
arrays = [np.eye(13, k=i, dtype=np.int64)+np.eye(13, k=i-13, dtype=np.int64) for i in range(13)]
for i, c in enumerate(reversed(s)) :
    if c != "?" :
        c = int(c)
        array = arrays[c*effects[i%6]%13]
        amari = np.dot(amari, array)
    else :
        array = sum(arrays[c*effects[i%6]%13] for c in range(10))
        amari = np.dot(amari, array)%mod

print(amari[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10**9+7

amari = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i, c in enumerate(reversed(s)) :
    if c != "?" :
        c = int(c)
        effect = c*effects[i%6]%13
        amari = [amari[j-effect] for j in range(13)]
    else :
        amari = [sum(amari[j-c*effects[i%6]%13] for c in range(10))%mod \
                                                 for j in range(13)]

print(amari[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
if s[0]=="?":
    p=[1]*10+[0]*3
else:
    p=[0]*13
    p[int(s[0])]=1
q=10
for i in s[1:]:
    if i!="?":
        i=int(i)
        s=q*i%13
        p=p[-s:]+p[:-s]
    else:
        d=[0]*13
        for j in range(10):
            s=q*j%13
            r=p[-s:]+p[:-s]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
if s[0]=="?":
    p=[1]*10+[0]*3
else:
    p=[0]*13
    p[int(s[0])]=1
q=10
for i in s[1:]:
    if i!="?":
        i=int(i)
        s=q*i%13
        p=p[-s:]+p[:-s]
    else:
        d=[0]*13
        for j in range(10):
            s=q*j%13
            r=p[-s:]+p[:-s]
            d=[r[i]+d[i]for i in range(13)]
        p=[i%(10**9+7) for i in d]
    q=(q*10)%13
print(p[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
if s[0]=="?":
    p=[1]*10+[0]*3
else:
    p=[0]*13
    p[int(s[0])]=1
q=10
for i in s[1:]:
    if i!="?":
        i=int(i)
        s=q*i%13
        p=p[-s:]+p[:-s]
    else:
        d=[0]*13
        for j in range(10):
            s=q*j%13
            r=p[-s:]+p[:-s]
            d=[r[i]+d[i]for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import copy
S=input()

dp=[0]*13
dp[0]=1
for k,s in enumerate(reversed(S)):
    dpt=copy.copy(dp)
    dp=[0]*13
    if s=='?':
        for j in range(10):
            st=(j*10**k)%13
            for i in range(13):
                dp[i]=dp[i]+dpt[i-st]
    else:
        for i in range(13):
            st=(int(s)*10**k)%13
            dp[i]=dpt[i-st]
#    print(dp)
#    print(sum(dp))
print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i] % div
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i] % div
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    div = pow(10, 9) + 7
    rem = [0 for _ in range(13)]
    rem[0] = 1
    for c in S:
        temp = [0 for _ in range(13)]
        if c != "?":
            for i in range(13):
                r = (i*10+int(c)) % 13
                temp[r] += rem[i]
        else:
            for i in range(13):
                for j in range(10):
                    r = (i*10+j) % 13
                    temp[r] += rem[i]
        rem = temp
    return rem[5] % div

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
MOD = 10**9 + 7
n = len(s)

data = [0 for i in range(n+2)] #10**iを13で割ったあまり
data[0] = 1
for i in range(1,n+2):
    data[i] = (data[i-1]*10)%13


dp = [[0 for i in range(13)] for j in range(10**5+100)]

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


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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD

print(cur[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD

print(cur[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] = (cur[q] + pre[j]) % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] =  (cur[p] + pre[j]) % MOD

print(cur[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            cur[(j * 10 + int(s[i])) % 13] = (cur[(j * 10 + int(s[i])) % 13] + pre[j]) % MOD
    else:
        for j in range(13):
            for k in range(10):
                cur[(j * 10 + k) % 13] =  (cur[(j * 10 + k) % 13]+ pre[j]) % MOD

print(cur[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

dp = [[0 for _ in range(13)] for __ in range(len(s))] 

if s[0] != "?":
    dp[0][int(s[0])] = 1
else:
    for j in range(10):
        dp[0][j] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

dp = [[0 for _ in range(13)] for __ in range(len(s))] 

if s[0] != "?":
    dp[0][int(s[0])] = 1
else:
    for j in range(10):
        dp[0][j] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

s = list(s)

dp = [[0 for _ in range(13)] for __ in range(len(s))] 

if s[0] != "?":
    dp[0][int(s[0])] = 1
else:
    for j in range(10):
        dp[0][j] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
#D問題
mod = 1000000007
S = str(input())
N = len(S)

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

Submission status: Time Limit Exceeded

Solution code:
#D問題
mod = 1000000007
S = str(input())
N = len(S)

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

s = list(input())
n = len(s)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

table = [[0] * 13 for i in range(len(S))]

if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1

for i in range(len(S)-1):
    num = S[len(S)-i-2]
    if num =='?':
        for j in range(10):
#            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+(10**(i+1)) * j) % 13] += table[i][k] % (10**9 + 7)
    else:
#        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+(10**(i+1)) * int(num)) % 13] += table[i][k] % (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

table = [[0] * 13 for i in range(len(S))]

if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1

for i in range(len(S)-1):    
    if S[len(S)-i-2] =='?':
        for j in range(10):
#            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+(10**(i+1)) * j) % 13] += table[i][k] % (10**9 + 7)
    else:
        num = int(S[len(S)-i-2])
#        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+(10**(i+1)) * num) % 13] += table[i][k] % (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

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

S = input()

table = [[0] * 13 for i in range(len(S))]

if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1

for i in range(len(S)-1):    
    if S[len(S)-i-2] =='?':
        for j in range(10):
            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+mod) % 13] += table[i][k] % (10**9 + 7)
    else:
        num = int(S[len(S)-i-2])
        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+mod) % 13] += table[i][k] % (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

table = [[0] * 13 for i in range(len(S))]

if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1

for i in range(len(S)-1):    
    if S[len(S)-i-2] =='?':
        for j in range(10):
            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+mod) % 13] += table[i][k] % (10**9 + 7)
    else:
        num = int(S[len(S)-i-2])
        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+mod) % 13] += table[i][k] % (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

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

S = input()

table = [[0] * 13 for i in range(len(S))]

if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1

for i in range(len(S)-1):    
    if S[len(S)-i-2] =='?':
        for j in range(10):
            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+mod) % 13] += table[i][k] #% (10**9 + 7)
    else:
        num = int(S[len(S)-i-2])
        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+mod) % 13] += table[i][k] #% (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:

s=list(input())
l=len(s)
mod=10**9+7
dp=[0]*13
dp[0] = 1
mul=1
for i in s[::-1]:
    nextDp=[0]*13
    if i=="?":
        for k in range(10):
            for j in range(13):
                nextDp[(k*mul+j)%13] += dp[j]
                #nextDp[(k*mul+j)%13]%=mod
    else:
        for j in range(13):
            nextDp[(int(i)*mul+j)%13] += dp[j]
            #nextDp[(int(i)*mul+j)%13]%=mod
    mul *= 10
    dp = nextDp

print(dp[5]%mod)

Submission status: Time Limit Exceeded

Solution code:

s=list(input())
l=len(s)
mod=10**9+7
dp=[0]*13
dp[0] = 1
mul=1
for i in s[::-1]:
    nextDp=[0]*13
    if i=="?":
        for k in range(10):
            for j in range(13):
                nextDp[(k*mul+j)%13] += dp[j]
                nextDp[(k*mul+j)%13]%=mod
    else:
        for j in range(13):
            nextDp[(int(i)*mul+j)%13] += dp[j]
            nextDp[(int(i)*mul+j)%13]%=mod
    mul *= 10
    dp = nextDp

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
s=[x for x in input()]
n=len(s)
dp=[[0 for i in range(13)] for j in range(n+1)]
dp[0][0]=1
for i in range(n):
  for j in range(10):
    if s[i]!='?' and s[i]!=str(j):
      continue
    for k in range(13):
      dp[i+1][(k*10+j)%13] += dp[i][k]
  for j in range(13):
    dp[i+1][j]=dp[i+1][j]%mod
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
mod = 10**9+7
s=[x for x in input()]
n=len(s)
dp=np.zeros((n+1,13)).astype(np.uint64)
dp[0,0]=1
for i in range(n):
  for j in range(10):
    if s[i]!='?' and s[i]!=str(j):
      continue
    for k in range(13):
      dp[i+1,(k*10+j)%13] += dp[i,k]
  for j in range(13):
    dp[i+1,j]%=mod
print(int(dp[n,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(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)