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:
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[0 for _ in range(13)]

DP[0]=1
m = 10**9+7
mul = 1
for i in range(len(s)):
    dig = s[i]
    nextDP = [0 for _ in range(13)]
    if dig == '?':
        for j in range(10):
            for k in range(13):
                nextDP[(k+mul*j)%13] += DP[k]
                
    else:
        j = int(dig)
        for k in range(13):
            nextDP[(k+mul*j)%13] += DP[k]

    mul *= 10
    DP = nextDP

print(DP[5]%m)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(len(S)):
    cdp = [0] * 13
    tmpS = 0
    if S[i] == '?':
        tmpS = -1
    else:
        tmpS = int(S[i])
    for j in range(10):
        if tmpS != -1 and tmpS != j: continue
        for k in range(13):
            cdp[(k * 10 + j) % 13] += dp[k]
            cdp[(k * 10 + j) % 13] %= MOD

    dp = cdp[:]
print(dp[5])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

S = input()[::-1]

arr = []
for i, x in enumerate(S):
	if x in digits:
		n = pow(10, i, 13)*int(x)%13
		arr.append(n)
	else:
		arr.append(pow(10, i, 13))

dp = [[0]*13 for _ in range(len(S)+1)]
#dp[i][j] : i桁目までで13で割って余る可能性の数
dp[0][0] = 1

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

	else:
		for j in range(13):
			dp[i][j] += dp[i-1][(j-int(x))%13]
			dp[i][j] %= mod


print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def f(i,k):
  for j in range(13):
    dp[i+1][(j*10+k)%13]+=dp[i][j]
    dp[i+1][(j*10+k)%13]%=mod
  
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*13 for i in range(10**5+1)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  
print(dp[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
def f(i,k):
  for j in range(13):
    dp[i+1][(k*mul+j)%13]+=dp[i][j]
    dp[i+1][(k*mul+j)%13]%=mod
  
mod=10**9+7
s=input()[::-1]
dp=[[0]*13 for i in range(10**5)]
dp[0][0]=mul=1

for i in range(len(s)):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  mul*=10
  
print(dp[len(s)][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import copy

def f(k,nextdp):
  for j in range(13):
    nextdp[(k*mul+j)%13]+=dp[j]
    nextdp[(k*mul+j)%13]%=mod
  return nextdp

mod=10**9+7
s=input()[::-1]
dp=[0]*13
dp[0]=mul=1

for i in range(len(s)):
  nextdp=[0]*13
  if s[i]=='?':
    for k in range(10):
      nextdp=f(k,nextdp)
  else:
    k=int(s[i])
    nextdp=f(k,nextdp)
  mul*=10
  dp=copy.copy(nextdp)
  
print(dp[5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=list(S())[::-1]
  n=len(s)
  dp=[[0]*13 for _ in range(n+1)]

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

  return dp[n][5]%mod

# main()
print(main())

Submission status: Time Limit Exceeded

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

conv = {}
for i in range(13):
  conv[i] = (i * 10) % 13

S = readline().rstrip()
N = len(S)
DIV = 10 ** 9 + 7

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

x0 = S[0]
if x0 == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(x0)] = 1
  
for i in range(1, N):
  x = S[i]
  if x == "?":
    for j in range(13):
      for k in range(10):
        dp[i][(conv[j] + k) % 13] += dp[i - 1][j]
        dp[i][(conv[j] + k) % 13] %= DIV
  else:
    for j in range(13):
      dp[i][(conv[j] + int(x)) % 13] += dp[i - 1][j]
      dp[i][(conv[j] + int(x)) % 13] %= DIV

print(dp[-1][5])

Submission status: Time Limit Exceeded

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

for i, s in enumerate(S[::-1], start=1):
    p10 = pow(10, i - 1, 13)
    if s != '?':
        for k in range(13):
            dp[i][(int(s) * p10 + k) % 13] += dp[i - 1][k]
            dp[i][(int(s) * p10 + k) % 13] %= MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i][(j * p10 + k) % 13] += dp[i - 1][k]
                dp[i][(j * p10 + k) % 13] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1

    for i,s in enumerate(s[::-1],start = 1):
        p10 = pow(10,i-1,13)
        if s!= "?":
            for k in range(13):
                dp[i][(int(s)*p10 + k)%13] += dp[i-1][k]
                dp[i][(int(s)*p10 + k)%13] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    dp[i][(j*p10 + k)%13] += dp[i-1][k]
                    dp[i][(j*p10 + k)%13] %= MOD
    print(dp[n][5] % MOD)



if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
MOD = 10 ** 9 + 7

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

for s in S:
    # 4 == pow(10, -1, 13)
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        new_dp = np.zeros(13, dtype=int)
        for i in range(13):
            new_dp[np.arange(i, i + 10) % 13] += dp[i]
            new_dp %= MOD
        dp = new_dp
    else:
        dp = np.roll(dp, int(s))
print(dp[5])

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
P = 13
qs = [0]*13
tmp = 1
rest = 0
for i, s in enumerate(S):
    if s == '?':
        qs[tmp] += 1
    else:
        rest = (rest + int(s) * tmp) % P
    tmp = (tmp * 10) % P

dp = [0] * 13
dp[rest] = 1
for i, cnt in enumerate(qs):
    for _ in range(cnt):
        dp_new = [0]*13
        for j in range(10):
            tmp = (i * j) % P
            for k in range(P):
                dp_new[(k + tmp) % P] += dp[k]
        dp = dp_new
print(dp[5]%int(1e9+7))

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9 + 7
mul = 1
# n桁目の?は10^nを13で割った余り(mul)と掛け合わせて足される

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

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

Submission status: Time Limit Exceeded

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

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

    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(10 * j+k) % 13] += dp[i][j]
                dp[i+1][(10 * j+k) % 13] %= mod


print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*pow(10,i,13)%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*pow(10,i,13)%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*pow(10,i)%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*pow(10,i)%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-19 17:18
# @url:https://atcoder.jp/contests/abc135/tasks/abc135_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 # 每位的权重10的幂次
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    temp=(t+j)%13
                    dp[i][temp]=dp[i-1][j]
            else:
                for j in range(10):
                    # t=p*j%13
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]+=dp[i-1][k]
        p=(p%13*10%13)%13
    # print (dp)
    print (dp[len(S)-1][5]%mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left
S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1
mod = 10**9 + 7

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:
import bisect, collections, copy, heapq, itertools, math, string, sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

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

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

    # for i in dp:
    #     print(i)
    print(dp[-1][5])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7

S = input()
# 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):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    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] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

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

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

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

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

    # for i in dp:
    #     print(i)
    print(dp[-1][5])

if __name__ == '__main__':
    resolve()

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):
    for j in range(13):
        if s[i] == '?':
            for x in range(10):
                dp[i+1][(10*j+x)%13] += dp[i][j]
                dp[i+1][(10*j+x)%13] %= mod
        else:
            x = int(s[i])
            dp[i+1][(10*j+x)%13] += dp[i][j]
            dp[i+1][(10*j+x)%13] %= mod

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
P = 10**9+7
Q = 13

dp = [0 for _ in range(Q)]
dp_pre = [0 for _ in range(Q)]

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

for i in range(1, len(S)):
    for k in range(Q):
        dp_pre[k] = dp[k]
        dp[k] = 0

    if S[i] == '?':
        for j in range(10): # 数字
            for k in range(Q): # 前の配列
                q = (j+10*k)%Q
                dp[q] += dp_pre[k]
    else:
        for k in range(Q):
            q = (int(S[i])+10*k)%Q
            dp[q] += dp_pre[k]

    for k in range(Q):
        dp[k] = dp[k] % P

ans = dp[5] % P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
P = 10**9+7
Q = 13
dp = [[0 for _ in range(Q)] for _ in range(len(S))]

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

for i in range(1, len(S)):
    if S[i] == '?':
        for j in range(10): # 数字
            for k in range(Q): # 前の配列
                q = (j+10*k)%Q
                dp[i][q] += dp[i-1][k]
    else:
        for k in range(Q):
            q = (int(S[i])+10*k)%Q
            dp[i][q] += dp[i-1][k]

    for k in range(Q):
        dp[i][k] = dp[i][k] % P

ans = dp[len(S)-1][5] % P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
P = 10**9+7
Q = 13
dp = [[0 for _ in range(Q)] for _ in range(len(S))]

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

for i in range(1, len(S)):
    if S[i] == '?':
        for j in range(10): # 数字
            for k in range(Q): # 前の配列
                q = (j+10*k)%Q
                dp[i][q] += dp[i-1][k]
    else:
        for k in range(Q):
            q = (int(S[i])+10*k)%Q
            dp[i][q] += dp[i-1][k]

ans = dp[len(S)-1][5] % P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
dp = [[0 for _ in range(13)] for _ in range(len(S))]
P = 10**9+7
S.reverse()
if S[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i in range(1, len(S)):
    if S[i] == '?':
        for j in range(10): # 数字
            p = (j*10**i)%13
            for k in range(13): # 前の配列
                q = (p+k)%13
                dp[i][q] += dp[i-1][k]
    else:
        p = (int(S[i])*10**i)%13
        for k in range(13):
            q = (p+k)%13
            dp[i][q] += dp[i-1][k]

ans = dp[len(S)-1][5] % P
print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 10 ** 9 + 7
S = input()

l = len(S)

dp = np.zeros((l + 1, 13))

# dp = [[0 for i in range(13)] for j in range(l+1)]

dp[0][0] = 1

for i, num in enumerate(S):

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

    else:
        k = int(num)
        for j in range(13):
            dp[i+1][((j * 10) + k) % 13] += dp[i][j]

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

print(int(dp[l][5]))

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

S = input()

l = len(S)
dp = [[0 for i in range(13)] for j in range(l+1)]

dp[0][0] = 1

for i, num in enumerate(S):

    if num == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][((j * 10) + k) % 13] += dp[i][j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(num)
        for j in range(13):
            dp[i+1][((j * 10) + k) % 13] += dp[i][j]
            # nextdp[((j * 10) + k) % 13] %= mod

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

print(dp[l][5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

    for i in range(13):
        dp[i] = nextdp[i] % mod

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

    for i in range(13):
        dp[i] = nextdp[i] % mod


print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            nextdp[((j * 10) + k) % 13] %= mod

    dp = nextdp


print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys

mod = 10**9 + 7
S = sys.stdin.readline().strip()

S = S[::-1]
ls = len(S)
dp = [0] * 13
dp[0] = 1
for i in range(ls):
    ndp = [0] * 13
    # print("S", S[i])
    for j in range(13):
        if dp[j] == 0:
            continue
        digit = pow(10, i, 13)
        if S[i] == "?":
            for k in range(10):
                r = k * digit + j
                r %= 13
                ndp[r] += dp[j]
                ndp[r] %= mod

        else:
            n = int(S[i])
            r = n * digit + j
            r %= 13
            ndp[r] += dp[j]
            ndp[r] %= mod

    # print(ndp)
    dp = ndp

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys

mod = 10**9 + 7
S = sys.stdin.readline().strip()

S = S[::-1]
ls = len(S)
dp = [0] * 13
dp[0] = 1
for i in range(ls):
    ndp = [0] * 13
    # print("S", S[i])
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
                r = k * pow(10, i, 13) + j
                r %= 13
                ndp[r] += dp[j]
                ndp[r] %= mod

        else:
            n = int(S[i])
            r = n * pow(10, i, 13) + j
            r %= 13
            ndp[r] += dp[j]
            ndp[r] %= mod

    # print(ndp)
    dp = ndp

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
# dp[i][j]:上からi桁目で13で割った余りがjの場合の数
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
    for j in range(13):
        if s[i] == "?":
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
        else:
            k = int(s[i])-0
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[n][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

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

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

print(dp[-1][5])

Submission status: Time Limit Exceeded

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

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

for i, x in enumerate(s):
    # 1, 10, 100, 1000...の剰余を順に計算し、各桁までの剰余を計算
    if i == 0:
        tmp = 1
    else:
        tmp = tmp * 10 % 13
    if x != "?":
        move = int(x) * tmp
        if i == 0:
            dp[i][move] = 1
        else:
            for j in range(13):
                dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                dp[i][j] %= MOD
    else:
        for coef in range(10):
            move = coef * tmp
            if i == 0:
                dp[i][move] = 1
            else:
                for j in range(13):
                    dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                    dp[i][j] %= MOD

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()

mod=10**9+7

ans=[[0]*13 for _ in range(len(s))]

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

#print(ans)

ten=1
for ii in range(1,len(s)):
    ten=(ten*10)%13

    i=len(s)-ii-1
    
    if s[i]!="?":
        tmp=(int(s[i])*ten)%13
        for j in range(13):
            ans[i][(tmp+j)%13]+=(ans[i+1][j])%mod
    else:
        for k in range(10):
            tmp=(k*ten)%13
            for j in range(13):
                ans[i][(tmp+j)%13]+=(ans[i+1][j])%mod

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