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:
str=list(input())
n=len(str)

dp     = []
old_dp = []

for i in range (13):
    dp.append(0)
    old_dp.append(0)

dp [0] = 1    

for S in str:
    
    old_dp.clear()
    old_dp.extend(dp)

    dp.clear()
    
    for i in range (13):
        dp.append(0)

    if S == '?':
        for k in range(13):
            for j in range(10):
                pop =  ( k * 10 + j )%13
                dp [ pop ] = dp [ pop ] + old_dp [ k ]
                dp [ pop ] = dp [ pop ] % 1000000007
    else :
        j = int ( S )
        for k in range(13):
                pop =  ( k * 10 + j )%13
                dp [ pop ] = dp [ pop ] + old_dp [ k ]
                dp [ pop ] = dp [ pop ] % 1000000007

print ( dp [5] )

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

# dp[i][j] := i文字目（1-index)まで割り算した余りがjになるような'?'の置き換えが何通りあるか。
dp = [[0]*13 for _ in range(100001)]

S_length = len(S)
MOD = 1000000007
dp[0][0] = 1  # dpの初期化。0文字目までの割り算の余りが0になるような置き換えが1通りあると考える。

# 今、計算をしているのがi文字目, dpのiは1-indexだが、Sへのアクセスは0インデックスで行う
for i in range(1, S_length+1):
    for remain in range(13):  # i-1文字目まで計算した余りを決め打ちしているループ変数remain
        if S[i-1] == '?':  # i文字目が'?'であったらそれぞれをjに置き換えて計算
            for j in range(10):
                next_remain = (remain*10+j) % 13  # (i-1)文字目までの余りがremainで，i文字目の'?'に置き換えた場合の，i文字目まで計算した余り

                # dpの遷移
                dp[i][next_remain] += dp[i-1][remain]
                dp[i][next_remain] %= MOD
        else:
            next_remain = (remain*10 + int(S[i-1])) % 13
            # dpの遷移
            dp[i][next_remain] += dp[i-1][remain]
            dp[i][next_remain] %= MOD

print(dp[S_length][5])  # 答えはS_length文字目(つまり最後の文字)まで計算した余りが5になるような'?'の置き換えが何通りあるか

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp = [[0] * 13 for i in range(len(s))]

# 初期値
digit = s[0]
ii = len(s) - 1
if digit == '?':
    for j in range(10):
        num = j * (10**ii)
        amari = num % 13
        dp[0][amari] += 1
else:
    num = int(digit) * (10**ii)
    amari = num % 13
    dp[0][amari] += 1

for i in range(1, len(s)):
    ii = len(s) - 1 - i
    digit = s[i]
    if digit == '?':
        for j in range(10):
            num = j * (10**ii)
            amari = num % 13
            for k in range(13):
                dp[i][k] += dp[i-1][k-amari]
                dp[i][k] = dp[i][k] % (10**9+7)
    else:
        num = int(digit) * (10**ii)
        amari = num % 13
        for k in range(13):
            dp[i][k] += dp[i-1][k-amari]
            dp[i][k] = dp[i][k] % (10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()

dp = np.zeros(shape=(len(s), 13), dtype=int)

# 初期値
digit = s[0]
ii = len(s) - 1
if digit == '?':
    for j in range(10):
        num = j * (10**ii)
        amari = num % 13
        dp[0][amari] += 1
else:
    num = int(digit) * (10**ii)
    amari = num % 13
    dp[0][amari] += 1

for i in range(1, len(s)):
    ii = len(s) - 1 - i
    digit = s[i]
    if digit == '?':
        for j in range(10):
            num = j * (10**ii)
            amari = num % 13
            for k in range(13):
                dp[i][k] += dp[i-1][k-amari]
                dp[i][k] = dp[i][k] % (10**9+7)
    else:
        num = int(digit) * (10**ii)
        amari = num % 13
        for k in range(13):
            dp[i][k] += dp[i-1][k-amari]
            dp[i][k] = dp[i][k] % (10**9+7)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

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

print(ans[length][5] % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) ################「再帰回数上限解放」######################

S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
S=list(S)
dp=[]
for _ in range(len(S)):
    dp.append([0]*13)
if S[0]=='?':
    for i in range(10):
        dp[0][(i*10**(len(S)-1))%13]=1
else:
    dp[0][(int(S[0])*10**(len(S)-1))%13]=1
for j in range(0,len(S)-1):
    for k in range(13):
        if S[j+1]=='?':
            L=[]
            for l in range(10):
                l=(l*10**(len(S)-j-2)%13)
                L.append(dp[j][k-l])
            dp[j+1][k]+=sum(L)%(7+10**9)
        else:
            dp[j+1][k]=dp[j][k-(int(S[j+1]))*10**(len(S)-j-2)%13]
print((dp[len(S)-1][5])%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
S=input()
S=list(S)
dp=[]
for _ in range(len(S)):
    dp.append([0]*13)
if S[0]=='?':
    for i in range(10):
        dp[0][(i*10**(len(S)-1))%13]=1
else:
    dp[0][(int(S[0])*10**(len(S)-1))%13]=1
for j in range(0,len(S)-1):
    for k in range(13):
        if S[j+1]=='?':
            L=[]
            for l in range(10):
                l=(l*10**(len(S)-j-2)%13)
                L.append(dp[j][k-l])
            dp[j+1][k]+=sum(L)
        else:
            dp[j+1][k]=dp[j][k-(int(S[j+1]))*10**(len(S)-j-2)%13]
print((dp[len(S)-1][5])%(7+10**9))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = int(1e9 + 7)
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = int(1e9 + 7)
if s[-1]=="?":
    dp = [1]*13
    dp[12] = 0
    dp[11] = 0
    dp[10] = 0
else:
    dp = [0]*13
    dp[int(s[-1])] = 1

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

Submission status: Time Limit Exceeded

Solution code:
def f(s):
    rd = [[10, 11, 12], [3, 6, 9], [4, 8, 12], [1, 2, 3], [4, 7, 10], [1, 5, 9]]
    k = len(s)
    md = 10 ** 9 + 7
    dp = [0] * 13
    dp[0] = 1
    for i, c in enumerate(s[::-1]):
        if c == "?":
            r1, r2, r3 = rd[i % 6]
            sm = sum(dp)
            dp=[(sm - (dp[j - r1] + dp[j - r2] + dp[j - r3])) % md for j in range(13)]
        else:
            m = int(c) * 10 ** i % 13
            dp=[dp[j - m] for j in range(13)]
    print(dp[5])

s = input()
f(s)

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0 for i in range(13)]for j in range(len(s)+1)]
ten=1
if s[-1]=="?":
  for i in range(10):
    dp[1][i]=1
else:
  dp[1][int(s[-1])]=1
if len(s)>=2:
  for i in range(2,len(s)+1):
    ten*=10
    if s[-1*i]=="?":
      for j in range(10):
        for k in range(13):
          dp[i][(ten*j+k)%13]+=dp[i-1][k]
          dp[i][(ten*j+k)%13]%=1000000007
    else:
      for j in range(13):
        dp[i][(ten*int(s[-1*i])+j)%13]+=dp[i-1][j]
        dp[i][(ten*int(s[-1*i])+j)%13]%=1000000007
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0 for i in range(13)]for j in range(len(s)+1)]
ten=1
if s[-1]=="?":
  for i in range(10):
    dp[1][i]=1
else:
  dp[1][int(s[-1])]=1
if len(s)>=2:
  for i in range(2,len(s)+1):
    ten*=10
    if s[-1*i]=="?":
      for j in range(10):
        for k in range(13):
          dp[i][(ten*j+k)%13]+=dp[i-1][k]
    else:
      for j in range(13):
        dp[i][(ten*int(s[-1*i])+j)%13]+=dp[i-1][j]

while(dp[len(s)][5]>1000000007):
  dp[len(s)][5]%=1000000007
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

for i in range(N):
    s = S[i]
    for j in range(10):
        if s != "?" and s != str(j):
            continue
        for r in range(13):
            dp[i+1][(r * 10 + j) % 13] += dp[i][r]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
#dp[k] -> 13で割ったあまりがkのパターン数
dp = [0] * 13
dp[0] = 1
mul = 1

for c in s[::-1]:
  #次の状態
  nextDP = [0] * 13
  if c == "?":
    for k in range(10):
      for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod
      
  else:
    k = int(c)
    for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod

  mul *= 10
  mul %= 13
  dp = nextDP

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                I=str(i)
                if j=="?":
                    for r in map(str,range(10)):
                        dp[int(I+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(I+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                I=str(i)
                if j=="?":
                    for r in range(10):
                        dp[int(I+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(I+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
#from collections import* #defaultdict Counter deque appendleft
#from fractions import gcd
#from functools import* #reduce
#from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
#from operator import mul,itemgetter
#from bisect import* #bisect_left bisect_right
#from heapq import* #heapify heappop heappushpop
#from math import factorial,pi
#from copy import deepcopy
#import sys
#sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[int(str(i)+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
            else:
                continue
    print(dp[5][-1]%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, S_i in enumerate(S):
    rem13 = (10 ** i) % 13
    for j in range(13):
        if S_i == '?':
            for k in range(10):
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][(j - rem13 * k) % 13]) % mod
        else:
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][(j - rem13 * int(S_i)) % 13]) % mod

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

#from collections import* #defaultdict Counter deque appendleft
#from fractions import gcd
#from functools import* #reduce
#from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
#from operator import mul,itemgetter
#from bisect import* #bisect_left bisect_right
#from heapq import* #heapify heappop heappushpop
#from math import factorial,pi
#from copy import deepcopy
#import sys
#sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[int(str(i)+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
n=len(s)
mod=10**9+7
dp=[[0]*13 for j in range(100005)]
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][(k*10+j)%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%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:

from pprint import pprint
from collections import defaultdict
dp = {5:1}
mapper = {0: 0, 1: 9, 2: 5, 3: 1, 4: 10, 5: 6, 6: 2, 7: 11, 8: 7, 9: 3}
wildcard_mapper = {0: [0, 9, 5, 1, 10, 6, 2, 11, 7, 3],
             1: [4, 0, 9, 5, 1, 10, 6, 2, 11, 7],
             2: [8, 4, 0, 9, 5, 1, 10, 6, 2, 11],
             3: [12, 8, 4, 0, 9, 5, 1, 10, 6, 2],
             4: [3, 12, 8, 4, 0, 9, 5, 1, 10, 6],
             5: [7, 3, 12, 8, 4, 0, 9, 5, 1, 10],
             6: [11, 7, 3, 12, 8, 4, 0, 9, 5, 1],
             7: [2, 11, 7, 3, 12, 8, 4, 0, 9, 5],
             8: [6, 2, 11, 7, 3, 12, 8, 4, 0, 9],
             9: [10, 6, 2, 11, 7, 3, 12, 8, 4, 0],
             10: [1, 10, 6, 2, 11, 7, 3, 12, 8, 4],
             11: [5, 1, 10, 6, 2, 11, 7, 3, 12, 8],
             12: [9, 5, 1, 10, 6, 2, 11, 7, 3, 12]}
cache_mapper = {(0, 0): 0,
 (0, 1): 9,
 (0, 2): 5,
 (0, 3): 1,
 (0, 4): 10,
 (0, 5): 6,
 (0, 6): 2,
 (0, 7): 11,
 (0, 8): 7,
 (0, 9): 3,
 (1, 0): 4,
 (1, 1): 0,
 (1, 2): 9,
 (1, 3): 5,
 (1, 4): 1,
 (1, 5): 10,
 (1, 6): 6,
 (1, 7): 2,
 (1, 8): 11,
 (1, 9): 7,
 (2, 0): 8,
 (2, 1): 4,
 (2, 2): 0,
 (2, 3): 9,
 (2, 4): 5,
 (2, 5): 1,
 (2, 6): 10,
 (2, 7): 6,
 (2, 8): 2,
 (2, 9): 11,
 (3, 0): 12,
 (3, 1): 8,
 (3, 2): 4,
 (3, 3): 0,
 (3, 4): 9,
 (3, 5): 5,
 (3, 6): 1,
 (3, 7): 10,
 (3, 8): 6,
 (3, 9): 2,
 (4, 0): 3,
 (4, 1): 12,
 (4, 2): 8,
 (4, 3): 4,
 (4, 4): 0,
 (4, 5): 9,
 (4, 6): 5,
 (4, 7): 1,
 (4, 8): 10,
 (4, 9): 6,
 (5, 0): 7,
 (5, 1): 3,
 (5, 2): 12,
 (5, 3): 8,
 (5, 4): 4,
 (5, 5): 0,
 (5, 6): 9,
 (5, 7): 5,
 (5, 8): 1,
 (5, 9): 10,
 (6, 0): 11,
 (6, 1): 7,
 (6, 2): 3,
 (6, 3): 12,
 (6, 4): 8,
 (6, 5): 4,
 (6, 6): 0,
 (6, 7): 9,
 (6, 8): 5,
 (6, 9): 1,
 (7, 0): 2,
 (7, 1): 11,
 (7, 2): 7,
 (7, 3): 3,
 (7, 4): 12,
 (7, 5): 8,
 (7, 6): 4,
 (7, 7): 0,
 (7, 8): 9,
 (7, 9): 5,
 (8, 0): 6,
 (8, 1): 2,
 (8, 2): 11,
 (8, 3): 7,
 (8, 4): 3,
 (8, 5): 12,
 (8, 6): 8,
 (8, 7): 4,
 (8, 8): 0,
 (8, 9): 9,
 (9, 0): 10,
 (9, 1): 6,
 (9, 2): 2,
 (9, 3): 11,
 (9, 4): 7,
 (9, 5): 3,
 (9, 6): 12,
 (9, 7): 8,
 (9, 8): 4,
 (9, 9): 0,
 (10, 0): 1,
 (10, 1): 10,
 (10, 2): 6,
 (10, 3): 2,
 (10, 4): 11,
 (10, 5): 7,
 (10, 6): 3,
 (10, 7): 12,
 (10, 8): 8,
 (10, 9): 4,
 (11, 0): 5,
 (11, 1): 1,
 (11, 2): 10,
 (11, 3): 6,
 (11, 4): 2,
 (11, 5): 11,
 (11, 6): 7,
 (11, 7): 3,
 (11, 8): 12,
 (11, 9): 8,
 (12, 0): 9,
 (12, 1): 5,
 (12, 2): 1,
 (12, 3): 10,
 (12, 4): 6,
 (12, 5): 2,
 (12, 6): 11,
 (12, 7): 7,
 (12, 8): 3,
 (12, 9): 12}
n = input().rstrip("\n")
#n = "?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"
rn = reversed(n)

m = 10 ** 9 + 7

for c in rn:
    new_dp = defaultdict(int)
    if c == "?":
        for used, count in dp.items():
            for next_used in wildcard_mapper[used]:
                new_dp[next_used] += count
                
    else:
        digit = int(c)
        for used, count in dp.items():
            next_used = cache_mapper[(used,digit)]
            new_dp[ next_used] += count
            
    dp = new_dp
    #for i in range(13):
    #    dp[i] %= m
print(dp[0] % m)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[int(str(i)+str(r))%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

mod = 10**9+7

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(10*m+d)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod=10**9+7
s=input()
rev=reversed(s)
d=np.array([0 for i in range(13)])
d[0]=1
keep=np.array([0 for _ in range(13)])
mul=1
cal=0
t=np.array([i for i in range(13)])
for v in rev:
    if v!="?":
        cal+=mul*int(v)%13
    else:
        t_d=keep.copy()
        for j in range(1,10):
            t_d[(t+mul*j)%13]+=d
        d+=t_d
        d%=mod
        
    mul*=10
    mul%=13

cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
S = input()
MOD = 10**9 + 7
 
# 縦i,横j, 数字k
dp_ = [[0 for j in range(13)] for i in range(len(S)+1)]
dp_[0][0] = 1
dp = np.array(dp_, dtype=int)
 
for i in range(len(S)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10 + k) % 13] += dp[i][j]
    else:
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD
 
print(dp[-1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
S = input()
MOD = 10**9 + 7
 
# 縦i,横j, 数字k
dp_ = [[0 for j in range(13)] for i in range(len(S)+1)]
dp_[0][0] = 1
dp = np.array(dp_, dtype=int)
 
for i, s in enumerate(S):
    if i == len(S):
        break
    if s == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10 + k) % 13] += dp[i][j] % MOD
    else:
        for j in range(13):
            dp[i+1][(j * 10 + int(s)) % 13] += dp[i][j] % MOD
 
print(dp[-1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:

from pprint import pprint
from collections import defaultdict
dp = {5:1}
mapper = {0: 0, 1: 9, 2: 5, 3: 1, 4: 10, 5: 6, 6: 2, 7: 11, 8: 7, 9: 3}
n = input().rstrip("\n")

rn = reversed(n)

m = 10 ** 9 + 7

for c in rn:
    new_dp = defaultdict(int)
    if c == "?":
        for digit in range(10):
            for used, count in dp.items():
                
                next_used, current_used = divmod(used, 10)
                if current_used > digit:
                    remain = (digit + 10) - current_used
                    next_used += 1
                else:
                    remain = digit - current_used
                next_used = next_used + mapper[remain]
                new_dp[next_used] += count
                
    else:
        digit = int(c)
        for used, count in dp.items():
            next_used, current_used = divmod(used, 10)
            if current_used > digit:
                remain = (digit + 10) - current_used
                next_used += 1
            else:
                remain = digit - current_used
            next_used = next_used + mapper[remain]
            new_dp[ next_used] += count
            
    dp = new_dp
print(dp[0] % m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
x = np.zeros(26, int)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[1:], l[1:]):
    x %= mod
    x[13:] = x[:13]
    if s == "?":
        x[:13] = sum([x[v:v+13] for v in l_])
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
print(x[5] % mod)

Submission status: Time Limit Exceeded

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

n = len(S)
a = S[0]
dp = [0] * 26
l = [[13 - i * j % 13 for j in range(1, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    dp[0:10] = [1] * 10
else:
    dp[int(a)] = 1
for s, l_ in zip(S[1:], l[1:]):
    dp[13:] = dp[:13]
    if s == "?":
        x = dp[:13]
        for v in l_:
            for i, x_ in enumerate(dp[v:v+13]):
                x[i] += x_
        dp[:13] = x
    else:
        if s != "0":
            v = l_[int(s) - 1]
            dp[:13] = dp[v:v+13]
#     x %= mod
print(dp[5] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = list(input())
n =len(s)-1
A=13
data=[4,3,12,9,10,1]*n
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i):
	return a*data[i]%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

			
			
# print(data)
print(dp[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
x = np.zeros(26, int)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[1:], l[1:]):
    x[13:] = x[:13]
    if s == "?":
        x[:13] = np.sum(x[v:v+13] for v in l_)
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
    x %= mod
print(x[5])