Problem:


Score : 400 points

Problem Statement

Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.

Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.

Since the answer can be enormous, print the count modulo 10^9+7.

Constraints

S is a string consisting of digits (0, ..., 9) and ?.

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of integers satisfying the condition, modulo 10^9+7.

Sample Input 1

??2??5

Sample Output 1

768

For example, 482305, 002865, and 972665 satisfy the condition.

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

We may not be able to produce an integer satisfying the condition.

Sample Input 4

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=10**9+7
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    flag = 1 if s[i]=='?' else 0
    for a in range(10):#i+1桁目の数字(0-9)
        if flag==1 or s[i]==str(a):
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    for j in range(13):
        dp[i+1][j]%=10**9+7
print(dp[n][5])

Submission status: Time Limit Exceeded

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

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

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

p = 13
dp = [0] * p
dp[0] = 1
mod = 10 ** 9 + 7

mul = 1
for s in S[::-1]:
  nextDp = [0] * p

  if s == "?":
    for i in range(10):
      for j in range(p):
        nextDp[(i * mul + j) % p] += dp[j]
  else:
    num = int(s)
    for j in range(p):
      nextDp[(num * mul + j) % p] += dp[j]

  dp = nextDp
  mul *= 10

print(dp[5] % mod)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc135/tasks/abc135_d

# む ず す ぎ に き あ く ん 笑

# 全探索すると最悪O(10^100000)となり宇宙が崩壊するので桁の独立性について考えてみる。
# まず文字列Sについて式を書き換える。下からi桁目の数字をSi、len(S)=n (桁数)とすると、
# S=S0 + S1*10 + S2*100 + S3*1000 ... となる。これは(mod 13)において
# S≡S0 + S1*10 + S2*9   + S3*12 ... (mod 13)であり、Si=='?' の中でS≡5となる通りの数を求めれば良い。という問題になる。
# 以上により、i番目の項までの余りはi-1番目の項までの余りを足して法を取り直すことで得られることがわかる。
# 具体的には桁DPなるテクニックで、dp[i][j] (n,13) ... i番目の項まで足したときに13で割った余りがjである通りの数 を更新していけば良い。

MOD = 10**9 + 7
S = input()[::-1]
n = len(S)

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

for i, s in enumerate(S):
    mul = pow(10, i, 13)
    if s != '?':
        shift = (int(s) * mul) % 13
        for j in range(13):
            dp[i + 1][(j + shift) % 13] = dp[i][j]
    else:
        for candi in range(10):
            shift = (candi * mul) % 13
            for j in range(13):
                dp[i + 1][(j + shift) % 13] += dp[i][j] % MOD
print(dp[-1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
MOD=10**9+7

dp=[[0]*13 for _ in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    c=S[i-1]
    if c=='?':
        for k in range(10):
            for n in range(13):
                nn=(n*10+k)%13
                dp[i][nn]+=dp[i-1][n]
                dp[i][nn]%=MOD
    else:
        for n in range(13):
            nn=(n*10+int(c))%13
            dp[i][nn]+=dp[i-1][n]
            dp[i][nn]%=MOD
print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  S = input()
  MOD = int(1e9+7)
  N = len(S)

  dp = np.zeros((N, 13))
  amari = 1
  if S[N-1] != '?':
    dp[0, int(S[N-1])] = 1
  else:
    for j in range(10):
      dp[0,j] = 1

  for i in range(1,N):
    amari = amari * 10 % 13
    idx = N-i-1
    if S[idx] != '?':
      shift = int(S[idx]) * amari % 13
      for j in range(13):
        XX = (j+shift)%13
        dp[i, XX] = dp[i-1, j]
    else:
      for k in range(10):
        shift = k * amari % 13
        for j in range(13):
          XX = (j+shift)%13
          dp[i, XX] = (dp[i, XX] + dp[i-1, j]) % MOD

  print(int(dp[N-1, 5]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  S = input()
  MOD = int(1e9+7)
  N = len(S)

  dp = np.zeros((N, 13))
  amari = 1
  for i in range(N):
    amari = amari * 10 % 13 if i > 0 else 1
    idx = N-i-1
    if i == 0:
      if S[idx] != '?':
        dp[i, int(S[idx])] = 1
      else:
        for j in range(10):
          dp[i][j] = 1
    else:
      if S[idx] != '?':
        shift = int(S[idx]) * amari % 13
        for j in range(13):
          XX = (j+shift)%13
          dp[i, XX] = dp[i-1, j]
      else:
        for k in range(10):
          shift = k * amari % 13
          for j in range(13):
            XX = (j+shift)%13
            dp[i, XX] = (dp[i, XX] + dp[i-1, j]) % MOD

  print(int(dp[N-1, 5]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  S = input()
  MOD = int(1e9+7)
  N = len(S)

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

  for i in range(N):
    idx = N-i-1
    if i == 0:
      if S[idx] != '?':
        dp[i, int(S[idx])] = 1
      else:
        for j in range(10):
          dp[i][j] = 1
    else:
      amari = (10 ** i) % 13
      if S[idx] != '?':
        shift = int(S[idx]) * amari % 13
        for j in range(13):
          XX = (j+shift)%13
          dp[i, XX] = dp[i-1, j]
      else:
        for k in range(10):
          shift = k * amari % 13
          for j in range(13):
            XX = (j+shift)%13
            dp[i, XX] = (dp[i, XX] + dp[i-1, j]) % MOD

  print(int(dp[N-1, 5]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  S = input()
  MOD = int(1e9+7)
  N = len(S)

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

  for i in range(N):
    idx = N-i-1
    if i == 0:
      if S[idx] != '?':
        dp[i][int(S[idx])] = 1
      else:
        for j in range(10):
          dp[i][j] = 1
    else:
      amari = (10 ** i) % 13
      if S[idx] != '?':
        shift = int(S[idx]) * amari % 13
        for j in range(13):
          if j+shift < 13:
            dp[i][j+shift] = dp[i-1][j]
          else:
            dp[i][j+shift-13] = dp[i-1][j]
      else:
        for k in range(10):
          shift = k * amari % 13
          for j in range(13):
            if j+shift < 13:
              dp[i][j+shift] = (dp[i][j+shift] + dp[i-1][j]) % MOD
            else:
              dp[i][j+shift-13] = (dp[i][j+shift-13] + dp[i-1][j]) % MOD

  print(dp[N-1][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

def main():
  s = input().rstrip()
  n = len(s)
  mod = 10**9+7
  dp = np.zeros((n+1, 13), dtype=np.int64)
  dp[0, 0] = 1
  j = np.arange(13)
  for i in range(n):
    if s[i] != "?":
      t = int(s[i])
      dp[i+1, (10*j+t)%13] += dp[i, j]
      dp[i+1, (10*j+t)%13] %= mod
    else:
      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])
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
n = len(s)
mod = 10**9+7
dp = np.zeros((n+1, 13), dtype=np.int64)
dp[0, 0] = 1
j = np.arange(13)
for i in range(n):
  if s[i] != "?":
    t = int(s[i])
    dp[i+1, (10*j+t)%13] += dp[i, j]
    dp[i+1, (10*j+t)%13] %= mod
  else:
    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()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
for i in range(n):
  if s[i] != "?":
    t = int(s[i])
    for j in range(13):
      dp[i+1][d[(j, t)]] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][d[(j, k)]] += dp[i][j]
print(dp[n][5]%mod)

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    S = input()
    u = [1] + [0] * 12
    v = [0] * 13
    m = 1
    shift = 0
    for s in reversed(S):
        if s == '?':
            for j in range(13):
                v[j] = sum(u[(j - (m * i) % 13) % 13] for i in range(10)) % MOD
            u, v = v, u
        else:
            shift = (shift + m * int(s)) % 13
        m = m * 10 % 13
    return u[(5 - shift) % 13]

print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    i = 0
    for v in reversed(S):
        if v == '?':
            k = 0
            for j in range(13):
                for k in range(13):
                    if l[i][j]:
                        kk = (j+k) % 13
                        n[kk] += c[k]
                        n[kk] %= mod
            c = n
            n = [0] * 13
        else:
            r += (l2[i][int(v)])
            r %= 13
        i += 1
        i %= 6
    r = (5 - r) % 13
    print(c[r] % mod)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = [0] * 13
        d2 = [0] * 10
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = [0] * 13
    c[0] = 1
    n = [0] * 13
    for i, v in enumerate(reversed(S)):
        if v == '?':
            for j in range(13):
                for k in range(13):
                    n[(j + k) % 13] += c[k] * l[i % 6][j]
            c = n
            n = [0] * 13
        else:
            r += (l2[i % 6][int(v)])
    r = (5 - r) % 13
    print(c[r] % mod)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = {j:0 for j in range(13)}
        d2 = {j:0 for j in range(10)}
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = {j:0 for j in range(13)}
    c[0] = 1
    n = {j:0 for j in range(13)}
    for i, v in enumerate(reversed(S)):
        if v == '?':
            for j in range(13):
                for k in range(13):
                    n[(j + k) % 13] += c[k] * l[i % 6][j]
            c = n
            n = {j:0 for j in range(13)}
        else:
            r += (l2[i % 6][int(v)])
    r = (5 - r) % 13
    print(c[r] % mod)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    l = []
    l2 = []
    mod = (10 ** 9) + 7
    for i in range(6):
        d = {j:0 for j in range(13)}
        d2 = {j:0 for j in range(10)}
        for j in range(0, 10):
            t = (j *(10 ** i)) % 13
            d[t] += 1
            d2[j] = t
        l.append(d)
        l2.append(d2)
    r = 0
    c = {j:0 for j in range(13)}
    c[0] = 1
    n = {j:0 for j in range(13)}
    for i, v in enumerate(reversed(S)):
        if v == '?':
            for j in range(13):
                for k in range(13):
                    n[(j + k) % 13] += c[k] * l[i % 6][j]
            c = n
            n = {j:0 for j in range(13)}
        else:
            r += (l2[i % 6][int(v)]) % 13
    r = (5 - r) % 13
    print(c[r] % mod)
main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
S = input()
N = len(S)

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

dp = [[0] * 13 for _ in range(N + 1)]
if S[-1] == '?':
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[-1])] = 1

for i in range(2, N + 1):
    m = (10 ** (i - 1)) % 13
    for j in range(13):
        if S[-i] == '?':
            for k in range(10):
                d = k * m % 13
                dp[i][j] += dp[i - 1][(13 + j - d) % 13]
        else:
            d = int(S[-i]) * m
            dp[i][j] += dp[i - 1][(13 + j - d) % 13]
        dp[i][j] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
S = input()
N = len(S)

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

dp = [[0] * 13 for _ in range(N + 1)]
if S[-1] == '?':
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[-1])] = 1

for i in range(2, N + 1):
    if S[-i] == '?':
        for k in range(10):
            d = k * (10 ** (i - 1)) % 13
            for j in range(13):
                dp[i][j] += dp[i - 1][(13 + j - d) % 13]
                dp[i][j] %= MOD
    else:
        d = int(S[-i]) * (10 ** (i - 1)) % 13
        for j in range(13):
            dp[i][j] += dp[i - 1][(13 + j - d) % 13]
            dp[i][j] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()
dp = np.zeros((len(S)+1,13)).astype('int')
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    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] %= int(10**9 + 7)
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    S = input()
    d = 1
    dp = [0] * 13
    dp[0] = 1
    dp_n = [None] * 13
    for s in reversed(S):
        for i in range(13):
            dp[i] %= N1097
            dp_n[i] = 0
        if s == '?':
            for s in range(10):
                diff = (s*d) % 13
                for i in range(13):
                    dp_n[(i+diff)%13] += dp[i]
        else:
            s = int(s)
            diff = (s*d) % 13
            for i in range(13):
                dp_n[(i+diff)%13] += dp[i]
        dp_n, dp = dp, dp_n
        d = (10 * d) % 13
    print(dp[5] % N1097)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(input())
    S.reverse()
    N = len(S)
    mod = 10**9+7
    dp = [[0 for r in range(13)] for n in range(N+1)]
    dp[0][0] = 1
    lookup = [[0 for d in range(10)] for n in range(N)]
    for n in range(N):
        for d in range(10):
            lookup[n][d] = d*pow(10, n, 13) % 13
    for n in range(1, N+1):
        if S[n-1] == '?':
            for d in range(10):
                for r in range(13):
                    dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
        else:
            for r in range(13):
                dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
    print(dp[-1][5] % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
revS = S[::-1]
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if revS[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(revS[0]) % MOD1] += 1

for i in range(1, N):
    if revS[i] == '?':
        for k in range(10):
            for j in range(MOD1):
                tmp_j = (k * 10 ** i % MOD1 + j) % MOD1
                dp[i][tmp_j] += dp[i - 1][j]
    else:
        for j in range(MOD1):
            tmp_j = (int(revS[i]) * 10 ** i % MOD1 + j) % MOD1
            dp[i][tmp_j] += dp[i - 1][j]

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

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
R = []
digit = 1
while True:
  r = [i*digit % 13 for i in range(10)]
  if r in R:
    break
  else:
    R.append(r)
  
  digit = digit*10 % 13


nr = len(R)
dp = [[1] + [0]*12] + [[0]*13 for i in range(N)]
for i, s in enumerate(S):
  if s == '?':
    _R = R[i%nr]
    for j in range(13):
      for r in _R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*10**i % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
revS = S[::-1]
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if revS[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(revS[0]) % MOD1] += 1

for i in range(1, N):
    if revS[i] == '?':
        for k in range(10):
            for j in range(MOD1):
                tmp_j = (k * 10 ** i % MOD1 + j) % MOD1
                dp[i][tmp_j] += dp[i - 1][j]
                dp[i][tmp_j] %= MOD2
    else:
        for j in range(MOD1):
            tmp_j = (int(revS[i]) * 10 ** i % MOD1 + j) % MOD1
            dp[i][tmp_j] += dp[i - 1][j]
            dp[i][tmp_j] %= MOD2

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
revS = S[::-1]
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if revS[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(revS[0]) % MOD1] += 1

for i in range(1, N):
    if revS[i] == '?':
        for k in range(10):
            for j in range(MOD1):
                dp[i][(k * 10 ** i + j) % MOD1] += dp[i - 1][j]
                dp[i][(k * 10 ** i + j) % MOD1] %= MOD2

    else:
        for j in range(MOD1):
            dp[i][(int(revS[i]) * 10 ** i + j) % MOD1] += dp[i - 1][j]
            dp[i][(int(revS[i]) * 10 ** i + j) % MOD1] %= MOD2

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
K = 13
MOD = 10**9 + 7

dp = [0] * K
dp[0] = 1

for s in S:
    newDp = [0] * K
    if s == '?':
        for i in range(10):
            for j in range(K):
                newDp[(j * 10 + i) % K] += dp[j]
    else:
        i = int(s)
        for j in range(K):
            newDp[(j * 10 + i) % K] += dp[j]
    dp = newDp

print(dp[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()
K = 13
MOD = 10**9 + 7

dp = [0] * K
dp[0] = 1

for s in S:
    newDp = [0] * K
    if s == '?':
        for i in range(10):
            for j in range(K):
                newDp[(j * 10 + i) % K] += dp[j]
    else:
        i = int(s)
        for j in range(K):
            newDp[(j * 10 + i) % K] += dp[j]
    dp = newDp
    for i in range(K):
        dp[i] %= MOD

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0]*13 for _ in range(len(s))]
if s[0]=='?':
  dp[0]=[1]*10+[0]*3
else:
  dp[0][int(s[0])]+=1

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0]*13 for _ in range(len(s))]
if s[0]=='?':
  dp[0]=[1]*10+[0]*3
else:
  dp[0][int(s[0])]+=1

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
MOD = 10 ** 9 + 7

# dp[i][j] := i文字目までみた時に13で割ってj余るような数の通り数
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()

mod=13
mod2=10**9+7
def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return (K*x)%mod

dp = np.zeros((10**5+1,13),dtype="int")
S=S[::-1]
if S[0]=="?":
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[0])] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

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] %= 10**9 + 7
    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] %= 10**9 + 7
    mul = mul * 10 % 13

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+pow(10, n-1, 13)*d) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+pow(10, n-1, 13)*int(S[n-1])) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S.reverse()
N = len(S)
mod = 10 ** 9 + 7
ans = [0 for r in range(13)]
if S[0] == '?':
    ans = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    ans[int(S[0])] = 1
for n in range(1, N):
    if S[n] == '?':
        ans = [sum([ans[(r-(d*pow(10, n, 13) % 13)) % 13]
                    for d in range(10)]) % mod for r in range(13)]
    else:
        ans = [ans[(r-(int(S[n])*pow(10, n, 13) % 13)) % 13]
               for r in range(13)]
print(ans[5])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S.reverse()
N = len(S)
mod = 10 ** 9 + 7
ans = [0 for r in range(13)]
if S[0] == '?':
    ans = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    ans[int(S[0])] = 1
for n in range(1, N):
    ans_new = []
    if S[n] == '?':
        for r in range(13):
            count = 0
            for d in range(10):
                r1 = d * (10 ** n) % 13
                r0 = (r - r1) % 13
                count += ans[r0] % mod
            ans_new.append(count % mod)
    else:
        for r in range(13):
            d = int(S[n])
            r1 = d * (10 ** n) % 13
            r0 = (r - r1) % 13
            ans_new.append(ans[r0] % mod)
    ans = ans_new
print(ans[5])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S.reverse()
N = len(S)
mod = 10 ** 9 + 7
ans = [[0 for r in range(13)] for n in range(N)]
if S[0] == '?':
    ans[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
    ans[0][int(S[0])] = 1
for n in range(1, N):
    if S[n] == '?':
        ans[n] = [sum([ans[n-1][(r-(d*(10**n) % 13)) % 13]
                       for d in range(10)]) % mod for r in range(13)]
        # for r in range(13):
        #     count = 0
        #     for d in range(10):
        #         r1 = d * (10 ** n) % 13
        #         r0 = (r - r1) % 13
        #         count += ans[n - 1][r0] % mod
        #     ans[n][r] = count % mod
    else:
        ans[n] = [ans[n-1][(r-(int(S[n])*(10**n) % 13)) % 13]
                  for r in range(13)]
        # for r in range(13):
        #     d = int(S[n])
        #     r1 = d * (10 ** n) % 13
        #     r0 = (r - r1) % 13
        #     ans[n][r] = ans[n-1][r0] % mod
print(ans[N-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7

ans = [[0 for r in range(13)] for n in range(N)]
if S[0] == '?':
    for r in range(10):
        ans[0][r] = 1
else:
    ans[0][int(S[0])] = 1
for n in range(1, N):
    if S[n] == '?':
        for r in range(13):
            count = 0
            for d in range(10):
                r1 = d * (10 ** n) % 13
                r0 = (r - r1) % 13
                count += ans[n - 1][r0]
            ans[n][r] = count % mod
    else:
        for r in range(13):
            d = int(S[n])
            r1 = d * (10 ** n) % 13
            r0 = (r - r1) % 13
            ans[n][r] = ans[n-1][r0] % mod
print(ans[N-1][5])

Submission status: Time Limit Exceeded

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

N = len(S)
# dp = [[0 for _ in range(13)] for _ in range(N + 1)]
# dp[N][0] = 1 # i = N - 1のケースでうまくいくための処置

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] += dp[1 - r][j]
                if dp[r][(j + w * k) % 13] >= p:
                    dp[r][(j + w * k) % 13] -= p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

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

print(dp[r][5])

Submission status: Time Limit Exceeded

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

N = len(S)
# dp = [[0 for _ in range(13)] for _ in range(N + 1)]
# dp[N][0] = 1 # i = N - 1のケースでうまくいくための処置

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] = (dp[r][(j + w * k) % 13] + dp[1 - r][j]) % p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

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

print(dp[r][5])

Submission status: Time Limit Exceeded

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

N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[N][0] = 1 # i = N - 1のケースでうまくいくための処置

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み

    if S[i] is not '?':
        k = int(S[i])
        for j in range(13):
            dp[i][(j + w * k) % 13] = dp[i + 1][j]
    else:
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[i][(j + w * k) % 13] = (dp[i][(j + w * k) % 13] + dp[i + 1][j]) % p

print(dp[0][5])