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

dp=[]
for i in range(len(S)+1):
  dp.append([0]*13)
dp[0][0]=1
#print(dp)

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
inf = float("inf")

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

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

for i in range(n):
    c = inf
    if s[i] == "?":
        c = -1
    else:
        c = ord(s[i]) - ord('0')
    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(13):
        dp[i + 1][j] %= mod
        
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
 if s[i]=='?': #?のときは各値(0～9)について更新する
   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) 
#最後まで更新を行ったときのあまりが5となる数の個数が答

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
MOD = 1000000007

S = input()

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

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

print(int(dp[len(S)][5]))

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
MOD = 1000000007

S = input()

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

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

print(int(dp[len(S)][5]))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)

MOD = 10**9+7

dp = []

for i in range(N+1):
  dp.append([0]*13)

dp[0][0] =1

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

    else:
      dp[i][(j*10+int(S[i-1])) % 13] += dp[i-1][j]

print(dp[N][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007

S = input().rstrip()

dp = np.zeros((len(S)+1, 13))

dp[0][0] = 1
for i, s in enumerate(S):
    if s == '?':
        for j in range(13):
            for num in range(10):
                state = (10*j+num)%13
                dp[i+1][state] += dp[i][j]
                dp[i+1][state] %= MOD
    else:
        num = int(s)
        for j in range(13):
            state = (10*j+num)%13
            dp[i+1][state] += dp[i][j]
            dp[i+1][state] %= MOD
    # print(dp[i+1])


print(int(dp[len(S)][5]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007

S = input().rstrip()

dp = np.zeros((len(S)+1, 13), dtype=np.int32)

dp[0][0] = 1
for i, s in enumerate(S):
    if s == '?':
        for j in range(13):
            for num in range(10):
                state = (10*j+num)%13
                dp[i+1][state] += dp[i][j]
                dp[i+1][state] %= MOD
    else:
        num = int(s)
        for j in range(13):
            state = (10*j+num)%13
            dp[i+1][state] += dp[i][j]
            dp[i+1][state] %= MOD
    # print(dp[i+1])


print(int(dp[len(S)][5]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007

S = input()

dp = np.zeros((len(S)+1, 13), dtype=np.int32)

dp[0][0] = 1
for i, s in enumerate(S):
    if s == '?':
        for j in range(13):
            for num in range(10):
                state = (10*j+num)%13
                dp[i+1][state] += dp[i][j]
                dp[i+1][state] %= MOD
    else:
        num = int(s)
        for j in range(13):
            state = (10*j+num)%13
            dp[i+1][state] += dp[i][j]
            dp[i+1][state] %= MOD
    # print(dp[i+1])


print(int(dp[len(S)][5]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007

S = input()

dp = np.zeros(13, dtype=np.int32)

dp[0] = 1
for i, s in enumerate(S):
    dp_next = np.zeros(13, dtype=np.int32)

    now = i%2
    prev = (i+1)%2

    for j in range(13):
        if s != '?':
            state = (10*j+int(s))%13
            dp_next[state] += dp[j]
            dp_next[state] %= MOD
            continue

        for num in range(10):
            state = (10*j+num)%13
            dp_next[state] += dp[j]
            dp_next[state] %= MOD
    # print(dp_next)
    dp = dp_next
print(int(dp[5]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
p = 10**9+7
DP = [[0]*13 for i in range(n+1)]
DP[0][0] = 1
for i in range(1, n+1):
    for j in range(13):
        if S[i-1] == '?':
            DP[i][j] = sum([DP[i-1][(4*(j-k)) % 13] for k in range(10)]) % p
        else:
            k = int(S[i-1])
            DP[i][j] = DP[i-1][(4*(j-k)) % 13]
print(DP[n][5])

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
MOD = 10**9 + 7


def main():
    S = [s for s in input()[::-1]]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*pow(10, i, 13))+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*pow(10, i, 13))+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
MOD = 10**9 + 7


def main():
    S = input()[::-1]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*(10**i))+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*(10**i))+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    t=(10**(l-i-2))%13
    for j in range(13):
        if u!="?":
            k=(j+int(u)*t)%13
            dp[i+1][k]+=dp[i][j]
        
        else:
            for g in range(10):
                k=(j+g*t)%13
                dp[i+1][k]+=dp[i][j]
    
                
            
#print(dp)
print(dp[l-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    t=(10**(l-i-2))%13
    for j in range(13):
        if u!="?":
            k=(j+int(u)*t)%13
            dp[i+1][k]+=dp[i][j]
        
        else:
            for g in range(10):
                k=(j+g*t)%13
                dp[i+1][k]+=dp[i][j]
    for d in dp[i+1]:
        d%=mod
                
            
#print(dp)
print(dp[l-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    t=(10**(l-i-2))%13
    for j in range(13):
        if u!="?":
            k=(j+int(u)*t)%13
            dp[i+1][k]+=dp[i][j]%mod
        else:
            for g in range(10):
                k=(j+g*t)%13
                dp[i+1][k]+=dp[i][j]%mod
            
#print(dp)
print(dp[l-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    for j in range(13):
        if u!="?":
            k=(j+int(u)*(10**(l-i-2)))%13
            dp[i+1][k]+=(dp[i][j])%mod
        else:
            for g in range(10):
                k=(j+g*10**(l-i-2))%13
                dp[i+1][k]+=dp[i][j]%mod
            
#print(dp)
print(dp[l-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

s=input().rstrip()
l=len(s)
dp=[[0 for i in range(13)] for i in  range(l)]
#dp[0]=[1 for i in range(13)]
i=0
u=s[0]
if u!="?":
    k=(int(u)*10**(l-1))%13
    dp[0][k]+=1
else:
    for g in range(10):
        k=(g*10**(l-1))%13
        dp[0][k]+=1
#print(dp)
for i in range(l-1):
    u=s[i+1]
    for j in range(13):
        if u!="?":
            k=(j+int(u)*(10**(l-i-2)))%13
            dp[i+1][k]+=dp[i][j]
        else:
            for g in range(10):
                k=(j+g*10**(l-i-2))%13
                dp[i+1][k]+=dp[i][j]
            
#print(dp)
print(dp[l-1][5]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 10 ** 9 + 7


S = input().rstrip()
length = len(S)
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1  # 桁数

for i in range(length):
    x = S[-(i + 1)]
    if x == '?':
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j] % MOD
    else:  # 数字
        for j in range(13):
            dp[i + 1][(mul * int(x) + j) % 13] += dp[i][j] % MOD
    mul = mul * 10 % 13

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 10 ** 9 + 7


S = input().rstrip()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1  # 桁数

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == '?':
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:  # 数字
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7


def main():
  S = input()
  L = len(S)
  dp = [[0] *13 for _ in range(L+1)]
  dp[0][0] = 1
  mul = 1
  
  for i in range(L):
    x = S[-(i+1)]
    if x == '?':
      for k in range(10):
        for j in range(13):
          dp[i+1][(mul * k + j)%13] += dp[i][j]
          dp[i+1][(mul * k + j)%13] %= MOD
    else:
      k = int(x)
      for j in range(13):
        dp[i+1][(mul * k + j)%13] += dp[i][j]
        dp[i+1][(mul * k + j)%13] %= MOD
    mul = mul * 10 %13
  print(dp[L][5])
    
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    n = len(s)
    s = list(reversed(s))
    determined = 0    # 確定枠 (mod 13)
    # 2, 3, 5 と入っていたら s*10^2, t*10^3, u*10^5 をたすことができる (s,t,u=0~9) というようにデータの保存も可能
    # 一歩進めて mod を先に取ろう
    L = []
    for i in range(n):
        if s[i] != '?':
            determined += pow(10, i, 13) * int(s[i])
            determined %= 13
        else:
            L.append(pow(10, i, 13))
    # print(determined)
    # print(L)
    # elm in L に 0~9 をかけて (mod 13)、この余りを作れるような組み合わせを考えれば良い
    target_res = ((13+5) - determined) % 13
    m = len(L)
    if m == 0:
        print(1) if target_res == 0 else print(0)
    else:
        # dp[i][j] = L の i 番目 (0-ind) までの数を用いて (0~9 を自在に掛け合わせて) mod 13 で j にできるような組み合わせの数
        dp = [[0] * 13 for _ in range(m)]
        first_line = [(L[0] * x) % 13 for x in range(10)]
        for j in range(13):
            dp[0][j] = first_line.count(j)
        for i in range(1, m):
            for j in range(13):
                elm = L[i]
                for x in range(10):
                    tmp = (x * elm) % 13
                    j_prime = (j + 13 - tmp) % 13
                    dp[i][j] += dp[i-1][j_prime]
                    dp[i][j] %= mod
        print(dp[m-1][target_res])

    
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

mod = 10**9+7

#全ての余りを確認する
dp = [[0 for i in range(13)]for j in range(S)]

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

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

Submission status: Time Limit Exceeded

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

mod = 10**9+7

#全ての余りを確認する
dp = [[0 for i in range(13)]for j in range(S)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10 ** 9 + 7

# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]  # 後ろから一桁ずつみていく
    if x == "?":
        for k in range(10): # ?が0~9であった時、それぞれのケースについて調べる
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= mod
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

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

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
mod = 10**9+7
S = list(input())
n = len(S)
#桁dp
dp = [[0]*(13) for _ in range(n+1)]
if S[0] == '?':
    for i in range(10):
        dp[1][i] = 1
if S[0] != '?':
    dp[1][int(S[0])] = 1
for i in range(1,n):
    i+=1
    if S[i-1] == '?':
        for m in range(13):
            for j in range(10):
                dp[i][(10*m+j)%13] += dp[i-1][m]
                dp[i][(10*m+j)%13] %= mod
        continue
    if S[i-1] != '?':
        for m in range(13):
            dp[i][(10*m+int(S[i-1]))%13] += dp[i-1][m]
            dp[i][(10*m+int(S[i-1]))%13] %= mod
dp[n][5] %= mod
print(dp[n][5])

Submission status: Time Limit Exceeded

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

dp = [1] + [0] * 12
for c in s:
  tmp = dp[:]
  if c == '?':
    dp = [0] * 13
    for n in range(10):
      for i in range(13):
        index = (10 * i + n) % 13
        dp[index] = (dp[index] + tmp[i]) % mod
  else:
    n = int(c)
    for i in range(13):
      dp[(10 * i + n) % 13] = tmp[i]
print(dp[5])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

# 事前準備
import numpy as np
table = (np.arange(13)[:, None] * 10 + np.arange(10)) % 13
invtable = []
for idxs in table.T:
    argidxs = np.zeros(13, dtype=int)
    for i, val in enumerate(idxs):
        argidxs[val] = i
    invtable += [argidxs]
P = int(1e9 + 7)
prev = np.array([1] + [0] * 12)

# 本番
for ch in S:
    buf = np.array([0] * 13)
    for one in range(10):
        if ch != "?" and one != int(ch):
            continue
        idxs = invtable[one]
        buf += prev[idxs]
        buf %= P
    prev = buf

print(buf[5] % P)

Submission status: Time Limit Exceeded

Solution code:
S = input()

# 事前準備
import numpy as np
table = (np.arange(13)[:, None] * 10 + np.arange(10)) % 13
invtable = []
for idxs in table.T:
    argidxs = np.zeros(13, dtype=int)
    for i, val in enumerate(idxs):
        argidxs[val] = i
    invtable += [argidxs]
P = int(1e9 + 7)
prev = np.array([1] + [0] * 12)

# 本番
for ch in S:
    buf = np.array([0] * 13)
    for one in range(10):
        if ch != "?" and one != int(ch):
            continue
        idxs = invtable[one]
        buf += prev[idxs]
        buf %= P
    prev = buf

print(buf[5] % P)

Submission status: Time Limit Exceeded

Solution code:
S = input()
prev = [1] + [0] * 12

P = int(1e9 + 7)
for ch in S:
    buf = [0] * 13
    for one in range(10):
        if ch != "?" and one != int(ch):
            continue
        for deca, num in enumerate(prev):
            buf[(10 * deca + one) % 13] += num % P
    prev = buf
    #sys.exit()

print(buf[5] % P)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()
prev = np.zeros(13, dtype=int)
prev[0] = 1

P = int(1e9 + 7)
for ch in S:
    buf = np.zeros(13, dtype=int)
    for one in range(10):
        if ch != "?" and one != int(ch):
            continue
        for deca, num in enumerate(prev):
            buf[(10 * deca + one) % 13] += num % P
    prev = buf

print(buf[5] % P)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7
S=S[::-1]

dp=[ [ 0 for j in range(13) ] for i in range(N) ]

for i,x in enumerate(S):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[i][(x*pow(10,i,13))%13]=1
        else:
            for x in range(10):
                dp[i][(x*pow(10,i,13))%13]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                n=(x*pow(10,i,13)+j)%13
                dp[i][n]+=dp[i-1][j]
                dp[i][n]%=mod
        else:
            for j in range(13):
                for x in range(10):
                    n=(x*pow(10,i,13)+j)%13
                    dp[i][n]+=dp[i-1][j]
                    dp[i][n]%=mod
print dp[N-1][5]%mod

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7

dp=[ [ 0 for j in range(13) ] for i in range(N) ]

for i,x in enumerate(S[::-1]):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[i][(x*pow(10,i,13))%13]=1
        else:
            for x in range(10):
                dp[i][(x*pow(10,i,13))%13]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                n=(x*pow(10,i,13)+j)%13
                dp[i][n]+=dp[i-1][j]
                dp[i][n]%=mod
        else:
            for j in range(13):
                for x in range(10):
                    n=(x*pow(10,i,13)+j)%13
                    dp[i][n]+=dp[i-1][j]
                    dp[i][n]%=mod
print dp[N-1][5]%mod