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()
MOD = 10 ** 9 + 7
N = len(S)

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

for i in range(N):
    for j in range(0, 10):
        if (S[i] != '?' and S[i] != str(j)):
            continue
        for k in range(0, 13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

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

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:

mod = 10 ** 9 + 7
S = input()[::-1]
W = [1, 10, 9, 12, 3, 4]

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

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

    if s == "?":
        for n in range(10):
            r = (n * W[i % 6]) % 13
            for j in range(13):
                dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

    else:
        n = int(s)
        r = (n * W[i % 6]) % 13
        for j in range(13):
            dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
divisor = 1000000007
answer=1
# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
s = list(input())
t = []

for i in range( len(s) ):
    if s[i] == '?':
        t.append(-1)
    else:
        t.append(int(s[i]))

dp = [[0 for i in range(13)] for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    for j in range(10):
        if t[i] == -1 or t[i] == j:
            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] % divisor

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

Submission status: Time Limit Exceeded

Solution code:

import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

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

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = [c for c in s]
s.reverse()
s = ''.join(s)
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  if s[i] != '?':
    r = (int(s[i]) * multiplier) % 13
    np = [0 for j in range(13)]
    for j in range(len(p)):
      np[(j + r) % 13] = p[j]
    for j in range(13):
      p[j] = np[j]
  else:
    np = [0 for j in range(13)]
    for j in range(10):
      r = (j * multiplier) % 13
      for k in range(len(p)):
        np[(k + r) % 13] += p[k]
    for j in range(13):
      p[j] = np[j]
print(p[5] % divisor)

Submission status: Time Limit Exceeded

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

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

def main():
    S_tmp = input()
    N = len(S_tmp)-1
    S = [S_tmp[i] for i in range(N)]                          
    
    ans = [0]*13
    ans[0] = 1
    
    for i in range(N):
        ans_pre = [x for x in ans]
        ans = [0]*13
        
        if S[i] == "?":                   
            for j in range(13):                   
                for k in range(10):                           
                    ans[(j*10+k)%13] += ans_pre[j]
        else:       
            for j in range(13):
                ans[(j*10+int(S[i]))%13] += ans_pre[j]
                
        for j in range(13):
            ans[j] %= 10**9+7
            
    print(ans[5])
                
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
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 = S.copy()
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()
l = len(S)
# S = S[::-1]
S = list(reversed(S))

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

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )

Submission status: Time Limit Exceeded

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

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [0 for _ in range(13)]
  if s[-1] == '?':
    for i in range(10):
      sd[i] = 1
  else:
    sd[int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    tmpd = [0 for _ in range(13)]
    if _s != '?':
      rem = int(_s) * pow(10, i) % 13
      for j in range(13):
        tmpd[(j+rem)%13] = sd[j]
    else:
      for k in range(10):
        rem = k * pow(10, i) % 13
        for j in range(13):
          tmpd[(j+rem)%13] += sd[j]
          tmpd[(j+rem)%13] %= MOD
    sd = tmpd[:]
  print(sd[5])


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
x = 10 ** 9 + 7
a = [1,0,0,0,0,0,0,0,0,0,0,0,0]
 
c = [1, -3, -4, -1, 3, 4]
for i in range(n):
    b = [0] * 13
    p = i % 6
    if S[n - i - 1] == "?":
        for j in range(13):
            for k in range(10):
                b[j] += a[(j - c[p] * k) % 13]
            b[j] = b[j] % x
        a = b
    else:
        s = int(S[n - i - 1])
        for j in range(13):
            b[j] = a[(j - c[p] * s) % 13]
        a = b
print(a[5])

Submission status: Time Limit Exceeded

Solution code:


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

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
  mod = 10**9+7 
  import numpy as np
  s = input()
  n = len(s)
  ans = [0 for i in range(13)]
  ans[0] = 1
  
  for i in range(n):
    tmp = [0 for i in range(13)]
    if s[i] == "?":
      for j in range(10):
        num = int(j*(10**(n-i-1)))%13
        #print(j,num,np.roll(ans,num))
        tmp = np.add(tmp,np.roll(ans,num))
    else:
      num = int(s[i])*(10**(n-i-1)%13)
      #print("A",np.roll(ans,num))
      tmp = np.roll(ans,num)
      #print("tmp",tmp)
    ans = [tmp[i]%mod for i in range(len(tmp))]
      
      
  #print(ans)
  print(ans[5])
 

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()

k = len(S)
k0 = (len(S)%6-1)%6
k1 = (len(S)%6-2)%6
k2 = (len(S)%6-3)%6
k3 = (len(S)%6-4)%6
k4 = (len(S)%6-5)%6
k5 = (len(S)%6-6)%6

a0 = S[k0::6] 
a1 = S[k1::6] 
a2 = S[k2::6] 
a3 = S[k3::6] 
a4 = S[k4::6] 
a5 = S[k5::6] 

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

A = np.zeros(6)
B = np.zeros(6)


b0 = a0.replace("?", "")
B[0] = int(len(a0) - len(b0))
A[0] = digitSum(b0)

b1 = a1.replace("?", "")
B[1] = int(len(a1) - len(b1))
A[1] = digitSum(b1)

b2 = a2.replace("?", "")
B[2] = int(len(a2) - len(b2))
A[2] = digitSum(b2)

b3 = a3.replace("?", "")
B[3] = int(len(a3) - len(b3))
A[3] = digitSum(b3)

b4 = a4.replace("?", "")
B[4] = int(len(a4) - len(b4))
A[4] = digitSum(b4)

b5 = a5.replace("?", "")
B[5] = int(len(a5) - len(b5))
A[5] = digitSum(b5)

for i in range(6):
    if B[i] == 0:
        B[i] = 1
    else:
        B[i] = B[i] *10
    
ans = 0

a = A[0] + A[1]*10 + A[2]*100 + A[3]*1000 + A[4]*10000 + A[5]*100000 
a = a%13
    
for i0 in range(int(B[0])):
    for i1 in range(int(B[1])):
        for i2 in range(int(B[2])):
            for i3 in range(int(B[3])):
                for i4 in range(int(B[4])):
                    for i5 in range(int(B[5])):
                        if (i0 + i1*10 + i2*100 + i3*(-1) + i4*(-10) + i5*(-100) + a)%13 == 5:
                            ans += 1
                            
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

    for keta in range(len(S)):
        c =S[keta]

        if c == "?":
            for j in range(0,10):
                kurai %= 13
                temp = (j * kurai) % 13
                for i in range(13):
                    dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                    dp[keta + 1][(temp + i) % 13] %= MOD
        else:
            temp = (int(c) * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
        kurai *= 10
        keta %= MOD
    print(dp[-1][5] % MOD)

if __name__ == "__main__":
    do()

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
N = len(S)
sum = 0
dp = [0] * 13
dp[0] = 1

for i, s in enumerate(S):
    n = N - i - 1
    if s == '?':
        # print("{}".format(10 ** n))
        a = [0] * 13
        for j in range(10):
            m = j * (10 ** n) % 13
            a[m] += 1

        newDP = [0] * 13
        for j1 in range(13):
            for j2 in range(13):
                newDP[(j1 + j2) % 13] += ((dp[j1] * a[j2]) % MOD)
        dp = [x % MOD for x in newDP]

    else:
        sum += (int(s) * (10 ** n))
        sum = sum % 13

print(dp[(-sum + 5 + 13) % 13])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
            
    for j in range(10):
        dp[i + 1][j] %= MOD
        
print(dp[-1][5])

Submission status: Time Limit Exceeded

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

a = [0] * 13
n = [0] * 13

from functools import lru_cache

@lru_cache(maxsize=10000000)
def get_base(d):
    if d==0:
        return 1
    base = get_base(d-1)
    base *= 10
    base %= 13
    return base

@lru_cache(maxsize=1000)
def get_shift(d, num):
    shift = num
    shift *= get_base(d)
    shift %= 13
    return shift

def calc(d, num):
#    shift = (num * (10 ** d))%13
    shift = get_shift(d, num)
    if d==0:
        n[shift] = 1
    else:
        for i in range(13):
            n[(i+shift)%13] += a[i]
    

for d, s in enumerate(S):
    if s=='?':
        for i in range(10):
            calc(d, i)
    else:
        calc(d, int(s[0]))
    a, n = n, a
    for i in range(13):
        a[i] %= 1000000007
        n[i] = 0

print(a[5])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = ( j * 10 ** (i) ) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] += dp[i-1][k]
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = ( val * 10 ** (i) ) % 13
            for k in range(13):
                dp[i][(k+amari)%13] += dp[i-1][k]
    
print(dp[digits-1][5]%(10**9 + 7))

Submission status: Time Limit Exceeded

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

a = [0] * 13
n = [0] * 13

from functools import lru_cache

@lru_cache(maxsize=10000000)
def get_base(d):
    base = 1
    for _ in range(d):
        base *= 10
        base %= 13
    return base

@lru_cache(maxsize=1000)
def get_shift(d, num):
    shift = num
    shift *= get_base(d)
    shift %= 13
    return shift

def calc(d, num):
#    shift = (num * (10 ** d))%13
    shift = get_shift(d, num)
    if d==0:
        n[shift] = 1
    else:
        for i in range(13):
            n[(i+shift)%13] += a[i]
    

for d, s in enumerate(S):
    if s=='?':
        for i in range(10):
            calc(d, i)
    else:
        calc(d, int(s[0]))
    a, n = n, a
    for i in range(13):
        a[i] %= 1000000007
        n[i] = 0

print(a[5])

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
        DP[i+1][k]%=mod
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=(10**(n-1-i))%13
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
        DP[i+1][k]%=mod
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ
C = 10 ** 9 + 7

L = len(S) - 1
mem = [[-1 for _ in range(13)] for _ in range(len(S))]


def calc(i, m):  # i桁目以下で余りがmとなるようにする
    if mem[i][m] >= 0:
        return mem[i][m]
    t = S[L - i]
    if t == '?':
        if i == 0:
            if m < 10:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += calc(i - 1, tm)
            s %= C
            mem[i][m] = s
            return s
    else:
        tn = int(t)
        if i == 0:
            if m == tn:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            tm = m - ((Ls[i % 6] * tn) % 13)
            if tm < 0:
                tm += 13
            k = calc(i - 1, tm) % C
            mem[i][m] = k
            return k


print(calc(len(S) - 1, 5))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
N = len(S)
sum = 0
dp = [0] * 13
dp[0] = 1

for i, s in enumerate(S):
    n = N - i - 1
    if s == '?':
        # print("{}".format(10 ** n))
        a = [0] * 13
        for j in range(10):
            m = j * (10 ** n) % 13
            a[m] += 1

        newDP = [0] * 13
        for j1 in range(13):
            for j2 in range(13):
                newDP[(j1 + j2) % 13] += dp[j1] * a[j2]
        dp = [x % MOD for x in newDP]

    else:
        # print("{}".format(int(s) * (10 ** n)))
        sum += (int(s) * (10 ** n))
        sum = sum % 13
        # m2 = int(s) * (10 ** n)
        # m = (int(s) * (10 ** n)) % 13
        # dp = dp[m:] + dp[:m]

# print("sum:{}, sum%13:{}".format(sum, sum % 13))
# print(dp)
print(dp[(-(sum % 13) + 5 + 13) % 13])
# for i in range(13):
#     print("{:3} : {}".format(i, dp[i] % MOD))

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])

Submission status: Time Limit Exceeded

Solution code:

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

    for keta,c in  enumerate(S):

        if c == "?":
            for j in range(0,10):
                kurai %= 13
                temp = (j * kurai) % 13
                for i in range(13):
                    dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                    dp[keta + 1][(temp + i) % 13] %= MOD
        else:
            temp = (int(c) * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
        kurai *= 10
        keta %= MOD
    print(dp[-1][5] % MOD)

if __name__ == "__main__":
    do()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
def rec(k, m):
    if k == N:
        return m == 5
    if memo[k][m] != -1:
        return memo[k][m]
    res = 0
    d = D[N-k-1]
    if S[k] != '?':
        res += rec(k+1, (m+int(S[k])*d)%13)
    else:
        for i in range(10):
            res += rec(k+1, (m+i*d)%13)
    res %= mod
    memo[k][m] = res
    return res

S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
memo = [[-1] * 13 for i in range(N+1)]
print(rec(0, 0))

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
ans = [[0] * 13 for _ in range(len(S))]
MOD = 10 ** 9 + 7
if S[0] == "?":
    for i in range(10):
        ans[0][i] = 1
else:
    ans[0][int(S[0])] = 1

for i, s in enumerate(S):
    base = 10 ** i
    if i == 0:
        continue
    if s == "?":
        for n in range(10):
            for j in range(13):
                ans[i][(j + n * base) % 13] += ans[i - 1][j]
                ans[i][(j + n * base) % 13] %= MOD
    else:
        for j in range(13):
            ans[i][(j + int(s) * base) % 13] = ans[i - 1][j]

print(ans[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
from collections import defaultdict
O=[defaultdict(int) for i in range(N+1)]
O[0][5]=1
mod=10**9+7
for i in range(N):
    for o in O[i].keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    O[i+1][x//10]=O[i][o]
                    break
        else:
            for j in range(10):
                x=13*j+o
                O[i+1][x//10]=(O[i+1][x//10]+O[i][o])%mod
print(O[N][0])

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
q=[ i for i in range(len(s)) if s[i]=='?']
l=len(q)
c=0
for i in range(10**l):
    for n,_q in zip(str(i).zfill(l),q):
        s[_q]=n
    if int("".join(s))%13 == 5:
        c+=1
print(c%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()

k = len(S)
k0 = (len(S)%6-1)%6
k1 = (len(S)%6-2)%6
k2 = (len(S)%6-3)%6
k3 = (len(S)%6-4)%6
k4 = (len(S)%6-5)%6
k5 = (len(S)%6-6)%6

a0 = S[k0::6] 
a1 = S[k1::6] 
a2 = S[k2::6] 
a3 = S[k3::6] 
a4 = S[k4::6] 
a5 = S[k5::6] 

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

A = np.zeros(6)
B = np.zeros(6)


b0 = a0.replace("?", "")
B[0] = int(len(a0) - len(b0))
A[0] = digitSum(b0)

b1 = a1.replace("?", "")
B[1] = int(len(a1) - len(b1))
A[1] = digitSum(b1)

b2 = a2.replace("?", "")
B[2] = int(len(a2) - len(b2))
A[2] = digitSum(b2)

b3 = a3.replace("?", "")
B[3] = int(len(a3) - len(b3))
A[3] = digitSum(b3)

b4 = a4.replace("?", "")
B[4] = int(len(a4) - len(b4))
A[4] = digitSum(b4)

b5 = a5.replace("?", "")
B[5] = int(len(a5) - len(b5))
A[5] = digitSum(b5)

for i in range(6):
    if B[i] == 0:
        B[i] = 1
    else:
        B[i] = B[i] *10
    
ans = 0

a = A[0] + A[1]*10 + A[2]*100 + A[3]*1000 + A[4]*10000 + A[5]*100000 
a = a%13
    
for i0 in range(int(B[0])):
    for i1 in range(int(B[1])):
        for i2 in range(int(B[2])):
            for i3 in range(int(B[3])):
                for i4 in range(int(B[4])):
                    for i5 in range(int(B[5])):
                        if (i0 + i1*10 + i2*100 + i3*1000 + i4*10000 + i5*100000 + a)%13 == 5:
                            ans += 1
                            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
N = len(S)
sum = 0
dp = [0] * 13
dp[0] = 1

for i, s in enumerate(S):
    n = N - i - 1
    if s == '?':
        # print("{}".format(10 ** n))
        a = [0] * 13
        for j in range(10):
            m = j * (10 ** n) % 13
            a[m] += 1

        newDP = [0] * 13
        for j1 in range(13):
            for j2 in range(13):
                newDP[(j1 + j2) % 13] += dp[j1] * a[j2]
        dp = [x % MOD for x in newDP]

    else:
        # print("{}".format(int(s) * (10 ** n)))
        sum += (int(s) * (10 ** n))
        # m2 = int(s) * (10 ** n)
        # m = (int(s) * (10 ** n)) % 13
        # dp = dp[m:] + dp[:m]

# print("sum:{}, sum%13:{}".format(sum, sum % 13))
# print(dp)
print(dp[(-(sum % 13) + 5 + 13) % 13])
# for i in range(13):
#     print("{:3} : {}".format(i, dp[i] % MOD))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
q = []
A = 13-5
for i in range(N-1,-1,-1):
    if S[i] == '?':
        q.append(N-i-1)
    else:
        A = (A+int(S[i])*(10**(N-i-1)))%13
DP= [[0]*13 for i in range(len(q)+1)]
DP[0][A] = 1
T = [1,10,9,12,3,4]
for i in range(len(q)):
    for j in range(13):
        for k in range(10):
            DP[i+1][(j+k*T[q[i]%6])%13] = (DP[i+1][(j+k*T[q[i]%6])%13]+DP[i][j])%(10**9+7)
print(DP[-1][0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
dp = [[(0,0)]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = (1,1)
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      if (dp[k-1][i][1] == 1):
        tmp = (i * 10) + l
        m = tmp % 13
        dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod, 1)
  k += 1
print(dp[k-1][5][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

ls = [0,4,8,12,3,7,11,2,6,10,1,5,9]
S = input()
dp = [[None]*13 for _ in range(len(S))]
mod = 10**9+7
def f(i, r):
    if dp[i][r] != None:
        return dp[i][r]
    if i == 0:
        if S[0] == "?":
            dp[i][r] = 1 if r <= 9 else 0
            return dp[i][r]
        else:
            dp[i][r] = 1 if int(S[0]) == r else 0
            return dp[i][r]
    if S[i] != "?":
        c = int(S[i])
        tmp = (r-c) % 13
        dp[i][r] = f(i-1, ls[tmp]) % mod 
        return dp[i][r]
    else:
        ans = 0
        for j in range(10):
            tmp = (r-j) % 13
            ans = (ans +f(i-1, ls[tmp])) % mod
        dp[i][r] = ans % mod
        return dp[i][r]

print(f(len(S)-1, 5))

Submission status: Time Limit Exceeded

Solution code:
#code
s = input()
mod = pow(10,9) + 7
maxn = int(s.replace("?","9"))
maxn = maxn - (maxn%13)
l = len(s)
a = {}
for s0 in range(len(s)):
    if s[s0] != "?":
        a[s0] = s[s0]
n = 0
i = 0
ctr = 0
b = []
while n <= maxn:
    n = 13 * i + 5
    sn = format(n,'0'+str(l)+'d')
    flag = 0
    for k in a.keys():
        if(len(sn) > k):
            if(sn[k] != a[k]):
                flag = 1
                break
        else:
            flag = 1
    if(flag == 0):
        ctr += 1
        b.append(n)
    i += 1
    
print(ctr%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
s = input()

undef = s.count("?")
stack = []
prace = []
c = 0

for i in range(undef):
    stack.append(0)

prace_i = 0
for i,j in enumerate(range(len(s))):
    if s[i:].find("?") == 0:
        prace.append(i)

for i in range(10**undef):
    i_pad = "0" * (undef - len(str(i))) + str(i)
    s_i = ""
    k = 0
    for j in range(len(s)):
        if j in prace:
            s_i += str(i_pad)[k]
            k+=1
        else:
            s_i += s[j]

    if int(s_i) % 13 == 5:
        c += 1
    if c == 10 ** 9 + 7:
        c = 0
print(c)

Submission status: Time Limit Exceeded

Solution code:
z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  f=(t[d]=='?')
  for i in range(k):
    for x in range(1+f*9):
      r=pow(z,d,k)
      r*=int(x if f else t[d])
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)