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:
def main():
  s = input()
  mod = 10**9+7
  dp = [0]*13
  dp[0] = 1
  digit = 1
  for i in range(len(s)-1, -1, -1):
    nextDP = [0]*13
    if s[i] == "?":
      for k in range(10):
        for j in range(13):
          t = (digit * k + j)%13
          nextDP[t] = (dp[j] + nextDP[t]) % mod
    else:
      si = int(s[i])
      for j in range(13):
        t = (digit * si + j)%13
        nextDP[t] = (dp[j] + nextDP[t]) % mod
    dp = nextDP
    digit *= 10
  print(dp[5])

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  mod = 10**9+7
  dp = [0]*13
  dp[0] = 1
  digit = 1
  for index, i in enumerate(s[::-1], start=1):
    nextDP = [0]*13
    if i == "?":
      for k in range(10):
        for j in range(13):
          nextDP[(digit * k + j)%13] += dp[j]
          nextDP[(digit * k + j)%13] %= mod
    else:
      for j in range(13):
        nextDP[(digit * int(i) + j)%13] += dp[j]
        nextDP[(digit * int(i) + j)%13] %= mod
    dp = nextDP
    digit *= 10
  print(dp[5])

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  mod = 10**9+7
  dp = [[0]*13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  digit = 1
  for index, i in enumerate(s[::-1], start=1):
    if i == "?":
      for k in range(10):
        for j in range(13):
          dp[index][(digit * k + j)%13] += dp[index - 1][j]
          dp[index][(digit * k + j)%13] %= mod
    else:
      for j in range(13):
        dp[index][(digit * int(i) + j)%13] += dp[index - 1][j]
        dp[index][(digit * int(i) + j)%13] %= mod
    digit *= 10
  print(dp[-1][5])

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0]*13 for _ in [0]*-~len(S)]
dp[0][0] = 1
mod = 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 1000000007
    S = input()
    n = len(S)

    # dp[i][j] 左からi文字目までの数で, 余りがjになるものの総数
    dp = [[0] * 13 for i in range(n)]

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

    for i in range(1,n):
        s = S[i]
        if s == "?":
            for rem in range(10):
                for pre in range(13):
                    dp[i][(10*pre + rem) % 13] += dp[i-1][pre]
                    dp[i][(10*pre + rem) % 13] %= mod

        else:
            rem = int(s)
            for pre in range(13):
                    dp[i][(10*pre + rem) % 13] += dp[i-1][pre]
                    dp[i][(10*pre + rem) % 13] %= mod

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
mod=10**9+7
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):
        a=(10*j+k)%13
        dp[i+1][a]=(dp[i][j]+dp[i+1][a])%mod
    else:
      b=int(S[i])
      a=(10*j+b)%13
      dp[i+1][a]=(dp[i+1][a]+dp[i][j])%mod
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    S = list(input())
    MOD = 10**9+7
    dp = [[0 for _ in range(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*10+k)%13] += dp[i][j]
                    if dp[i+1][(j*10+k)%13] > MOD:
                        dp[i+1][(j*10+k)%13] -= MOD
            else:
                k = int(S[i])
                dp[i+1][(j*10+k)%13] += dp[i][j]
                if dp[i+1][(j*10+k)%13] > MOD:
                    dp[i+1][(j*10+k)%13] -= MOD
    print(dp[len(S)][5])

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
MOD = 10**9+7
dp = [[0]*(14) for i in range(100010)]
dp[0][0] = 1

for i in range(N):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
        
    for j in range(10):
        if c != -1 and c != j:
            continue
        else:
            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(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
s = input()[::-1]
mod = 10**9 + 7
dp = [0 for i in range(13)]

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

if len(s) == 1:
    print(dp[5])
    sys.exit()

for i, x in enumerate(s[1:], start=1):
    nextdp = [0 for j in range(13)]
    if x != '?':
        a = int(x) * pow(10, i, 13)
        for k in range(13):
            nextdp[(k + a)%13] += dp[k]%mod
            nextdp[(k + a)%13] %= mod
    else:
        for y in range(10):
            a = y * pow(10, i, 13)
            for k in range(13):
                nextdp[(k + a)%13] += dp[k]%mod
                nextdp[(k + a)%13] %= mod
    dp = nextdp
print(dp[5])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
MOD = 10**9 + 7
cnt = [[] for _ in range(len(s))]
i = len(s) - 1
de = 1

while i >= 0:
    if s[i] == '?':
        for j in range(10):
            cnt[i].append((j * de) % 13)
    else: cnt[i].append((int(s[i]) * de) % 13)
    i -= 1
    de *= 10
    de %= 13

dp = [[0]*13 for _ in range(len(s))]
for i in cnt[0]:
    dp[0][i] = 1
for i in range(1, len(s)):
    for j in cnt[i]:
        for k in range(13):
            if dp[i-1][k] != 0:
                dp[i][(j + k)%13] += dp[i - 1][k]
                dp[i][(j + k)%13] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13

#print(dp)
print(dp[5])
#print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
MOD = 10**9 + 7
cnt = [[] for _ in range(len(s))]
i = len(s) - 1
de = 1

while i >= 0:
    if s[i] == '?':
        for j in range(10):
            cnt[i].append((j * de) % 13)
    else: cnt[i].append((int(s[i]) * de) % 13)
    i -= 1
    de *= 10

dp = [[0]*13 for _ in range(len(s))]
for i in cnt[0]:
    dp[0][i] = 1
for i in range(1, len(s)):
    for j in cnt[i]:
        for k in range(13):
            if dp[i-1][k] != 0:
                dp[i][(j + k)%13] += dp[i - 1][k]
                dp[i][(j + k)%13] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
MOD = 10**9 + 7
cnt = [[] for _ in range(len(s))]
i = len(s) - 1
de = 1

while i >= 0:
    if s[i] == '?':
        for j in range(10):
            cnt[i].append((j * de) % 13)
    else: cnt[i].append((int(s[i]) * de) % 13)
    i -= 1
    de *= 10

dp = [[0]*13 for _ in range(len(s))]
for i in cnt[0]:
    dp[0][i] = 1
for i in range(1, len(s)):
    for j in cnt[i]:
        for k in range(13):
            if dp[i-1][k] != 0:
                dp[i][(j + k)%13] += dp[i - 1][k]
                dp[i][(j + k)%13] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
leng=len(s)

dp = [[0]*13 for i in range(leng)]
mod = 10 ** 9 + 7
s=s[::-1]

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

for i in range(1, leng):
  if s[i]!="?":
    #temp = ((10**i)*int(rev[i]))%13
    for j in range(13):
      x=((10**i)*int(s[i])+j)%13
      #dp[i][(j+temp)%13]=dp[i-1][j]
      dp[i][x]=dp[i-1][j]
  else:
    for l in range(10):
      #temp = ((10**i)*l)%13
      for j in range(13):
        x=((10**i)*l+j)%13
        #dp[i][(j+temp)%13]+=dp[i-1][j]
        #dp[i][(j+temp)%13]%=mod
        dp[i][x]+=dp[i-1][j]
        dp[i][x]%=mod
print(dp[leng-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0]*13 for i in range(len(s))]
mod = 10 ** 9 + 7
s=s[::-1]
leng=len(s)
if s[0]!="?":
  dp[0][int(s[0])]=1
else:
  for i in range(10):
    dp[0][i]=1

for i in range(1, leng):
  if s[i]!="?":
    #temp = ((10**i)*int(rev[i]))%13
    for j in range(13):
      x=((10**i)*int(s[i])+j)%13
      #dp[i][(j+temp)%13]=dp[i-1][j]
      dp[i][x]=dp[i-1][j]
  else:
    for l in range(10):
      #temp = ((10**i)*l)%13
      for j in range(13):
        x=((10**i)*l+j)%13
        #dp[i][(j+temp)%13]+=dp[i-1][j]
        #dp[i][(j+temp)%13]%=mod
        dp[i][x]+=dp[i-1][j]
        dp[i][x]%=mod
print(dp[leng-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0]*13 for i in range(len(s))]
mod = 10 ** 9 + 7
rev=s[::-1]
if rev[0]!="?":
  dp[0][int(s[-1])]=1
else:
  for i in range(10):
    dp[0][i]=1

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0]*13 for i in range(len(s))]
mod = 10 ** 9 + 7
if s[-1]!="?":
  dp[0][int(s[-1])]=1
else:
  for i in range(10):
    dp[0][i]=1

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0]*13 for i in range(len(s))]

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
# import numpy as np
# import time
# import itertools
# import pprint
# import copy # deepcopy用
# import collections
# import bisect
# import heapq
# from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

input = sys.stdin.readline
def main():

#---------------------------------------------------------

    s = list(input())
    s.pop()
    s.reverse()
    
    MOD = 10**9+7
    dp  = [0]*13
    ndp = [0]*13
    
    mul   = 1
    dp[0] = 1
    
    for i in range(len(s)):
        if s[i]=='?':
            for j in range(10):
                for k in range(13):
                    ndp[(k+mul*j%13)%13] += dp[k]%MOD
        else:
            for k in range(13):
                    ndp[(k+mul*int(s[i])%13)%13] += dp[k]%MOD
        dp  = ndp
        ndp = [0]*13
        mul *= 10
    
    print(dp[5]%MOD)

#---------------------------------------------------------

if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
N = 10**9+7

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 10**9 + 7
dp = [[0 for i in range(13)] for i in range(n)]
if s[n-1] == "?":
    for i in range(10):
        dp[n-1][i] = 1
else:
    dp[n-1][int(s[n-1])] = 1

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)

mod = 10**9 + 7

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

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

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1
pow10 = 4
for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow10*10%13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*(10**i)+j)%13] = (dpnew[(k*(10**i)+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*(10**i)+j)%13] = (dpnew[(k*(10**i)+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin
s = stdin.readline()[:-1]

length = len(s)

dp = np.zeros((100100,13))

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()

length = len(s)

dp = np.zeros((100100,13))

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()

dp = np.zeros((100100,13))

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007

length = len(s)

for i in range(length):
	if s[i] == '?':
		for num in range(10):
			for j in range(13):
				dp[i+1][(j+num*ten)%13] += dp[i][j]
				dp[i+1][(j+num*ten)%13] %= mod
	else:
		num = int(s[i])
		for j in range(13):
			dp[i+1][(j+num*ten)%13] += dp[i][j]
			dp[i+1][(j+num*ten)%13] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()

dp = np.zeros((100100,13))

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007

for i in range(len(s)):
	if s[i] == '?':
		for num in range(10):
			for j in range(13):
				dp[i+1][(j+num*ten)%13] += dp[i][j]
				dp[i+1][(j+num*ten)%13] %= mod
	else:
		num = int(s[i])
		for j in range(13):
			dp[i+1][(j+num*ten)%13] += dp[i][j]
			dp[i+1][(j+num*ten)%13] %= mod
	ten *= 10
	ten %= 13

print(int(dp[len(s)][5]%mod))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

s = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(s)):
    dp2 = [0] * 13
    for j in range(10):
        if (s[i] == '?') | (s[i] == str(j)):
            for k in range(13):
                dp2[(10 * k + j) % 13] += dp[k]
                dp2[(10 * k + j) % 13] %= mod
    dp = dp2
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

s = input()
dp = [[0 for _ in range(13)] for _ in range(len(s) + 1)]
for i in range(len(s) - 1,  -1, -1):
    digit = len(s) - i - 1
    ddd = 10 ** digit
    if digit == 0:
        if s[i] != '?':
            dp[digit + 1][int(s[i])] += 1
        else:
            for j in range(10):
                dp[digit + 1][j] += 1    
    elif s[i] != '?':    
        s_i = (int(s[i]) * ddd) % 13
        for k in range(13):
            dp[digit + 1][(s_i + k) % 13] += dp[digit][k]
    else:        
        for j in range(10):
            s_i = (ddd * j) % 13
            for k in range(13):
                dp[digit + 1][(s_i + k) % 13] += dp[digit][k]
print(dp[len(s)][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    S = S[::-1]

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

    for c in S:
        dp, dp_prev = [0] * 13, dp
        for k in range(13):
            if c == '?':
                for j in range(10):
                    dp[(p * j + k) % 13] = (dp[(p * j + k) % 13] + dp_prev[k]) % MOD
            else:
                dp[(p * int(c) + k) % 13] = (dp[(p * int(c) + k) % 13] + dp_prev[k]) % MOD

        p = p * 10 % 13

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

s = input()
n = len(s)

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

for i in range(n):
  dp2 = [0]*13  
  for j in range(10):
    if s[i] == '?' or s[i] == str(j):
      for k in range(13):
        dp2[(k*10 + j)%13] += dp[k]
        dp2[(k*10 + j)%13] %= mod
        
  dp = dp2

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

S = list(input())
pre = [0]*13
now = [0]*13
pre[0]=1

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

print(now[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

S = input().rstrip()
n = len(S)
mod = 10**9+7
dp = np.zeros((n+1, 13), dtype=np.int64)
dp[0][0] = 1
j = np.arange(13)*10%13
for i, s in enumerate(S):
  if s != "?":
    t = int(s)
    dp[i+1][j] += np.roll(dp[i], t)
    dp[i+1] %= mod
  else:
    for t in range(10):
      dp[i+1][j] += np.roll(dp[i], t)
      dp[i+1] %= mod
print(dp[n][11])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
# import time
# import itertools
# import pprint
# import copy # deepcopy用
# import collections
# import bisect
# import heapq
# from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

input = sys.stdin.readline
def main():

#---------------------------------------------------------

    # path = 'input.txt'
    # f = open(path, "r")
    
    # s = list(f.readline())
    s = list(input())
    s.pop()
    s.reverse()
    
    MOD = 10**9+7
    dp  = np.array([0]*13)
    ndp = np.array([0]*13)
    tmp = np.arange(10)
    
    mul   = 1
    dp[0] = 1

    # t1 = time.time()

    for i in s:
        if i=='?':
            sh = tmp*mul%13
            for j in sh:
                ndp += np.append(dp[-j:],dp[:-j])
            ndp %= MOD
        else:
            sh = mul*int(i)%13
            ndp += np.append(dp[-sh:],dp[:-sh])
            ndp %= MOD

        dp  = ndp
        ndp = np.array([0]*13)
        mul *= 10

    # t2 = time.time()
    # print(t2-t1)

    print(dp[5])

#---------------------------------------------------------

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()

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

mul = 1
dp[0][0] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()

MOD = 10**9+7
dp  = [0]*13
ndp = [0]*13

mul   = 1
dp[0] = 1

for i in range(len(s)):
    if s[i]=='?':
        for j in range(10):
            for k in range(13):
                ndp[(k+mul*j%13)%13] += dp[k]%MOD
    else:
        for k in range(13):
                ndp[(k+mul*int(s[i])%13)%13] += dp[k]%MOD
    dp  = ndp
    ndp = [0]*13
    mul *= 10

print(dp[5]%MOD)

Submission status: Time Limit Exceeded

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

mul = 1
cnt = 0
dp  = [[0 for _ in range(13)] for _ in range(keta+1)]
dp[0][0] = 1

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

    mul *= 10

print(dp[keta][5])

Submission status: Time Limit Exceeded

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

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

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

    dp = nextdp
    mul *= 10

print(dp[5])

Submission status: Time Limit Exceeded

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

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

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

    dp = nextdp
    mul *= 10

print(dp[5])

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int


def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = None, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, [0] * 13
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))

def test():
    import doctest
    doctest.testmod()

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

Submission status: Time Limit Exceeded

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