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:
from functools import lru_cache
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve((amari + (i * pow(10, (lens - 1 - keta), 13))) % 13, keta + 1)
                x %= MOD
            return x
        else:
            return solve((amari + (int(S[keta]) * pow(10, (lens - 1 - keta), 13))) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve(amari + (i * pow(10, (lens - 1 - keta), 13)) % 13, keta + 1)
                x %= MOD
            return x
        else:
            return solve(amari + (int(S[keta]) * pow(10, (lens - 1 - keta), 13)) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve((amari + (i * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1)
                x %= MOD
            return x
        else:
            return solve((amari + (int(S[keta]) * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)

@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1 % MOD
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve((amari + (i * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1)
            return x % MOD
        else:
            return solve((amari + (int(S[keta]) * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)

Submission status: Time Limit Exceeded

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

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

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

        else:
            k = int(digit)
            d = (j+k*pow(10,i,13)%13)%13
            dp[d][i+1] += dp[j][i]
            dp[d][i+1] %= m
print(dp[5][N])

Submission status: Time Limit Exceeded

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

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

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

        else:
            k = int(digit)
            d = (j+k*pow(10,i,13)%13)%13
            dp[i+1][d] += dp[i][j]
            dp[i+1][d] %= m
print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
def func(cnt, cn):
    tmp = [0] * 13
    for i in range(13):
        nn = (cn + i) % 13
        tmp[nn] = cnt[i]
    return tmp


MOD = 10**9+7

s = list(input())
s.reverse()

cnt = [0]*13
cnt[0] = 1
t = 1
for ci in range(len(s)):
    t %= 13 
    if s[ci] != '?':
        cn = int(s[ci]) * t % 13
        cnt = func(cnt, cn)
    else:
        tmp = [0]*13
        add = [0]*13
        for cj in range(10):
            cn = cj * t % 13
            add = func(cnt, cn)
            for _ in range(13):
                tmp[_] += add[_]
                tmp[_] %= MOD
        cnt = tmp
    t *= 10
print(cnt[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def func(cnt, cn):
    tmp = np.zeros(13, dtype=np.int64)
    tmp[cn:13] = cnt[0:13-cn]
    tmp[0:cn] = cnt[13-cn:13]
    return tmp


MOD = 10**9+7

s = list(input())
s.reverse()

cnt = np.zeros(13, dtype=np.int64)
cnt[0] = 1
t = 1
for ci in range(len(s)):
    t %= 13 
    if s[ci] != '?':
        cn = int(s[ci]) * t % 13
        cnt = func(cnt, cn)
    else:
        tmp = np.zeros(13, dtype=np.int64)
        for cj in range(10):
            cn = cj * t % 13
            tmp += func(cnt, cn)
            tmp %= MOD
        cnt = tmp
    t *= 10
print(cnt[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def func(cnt, cn):
    tmp = [0] * 13
    for i in range(13):
        nn = (cn + i) % 13
        tmp[nn] = cnt[i]
    return tmp


MOD = 10**9+7

s = list(input())
s.reverse()

cnt = np.zeros(13, dtype=np.int64)
cnt[0] = 1
t = 1
for ci in range(len(s)):
    t %= 13 
    if s[ci] != '?':
        cn = int(s[ci]) * t % 13
        cnt = func(cnt, cn)
    else:
        tmp = np.zeros(13, dtype=np.int64)
        for cj in range(10):
            cn = cj * t % 13
            tmp += func(cnt, cn)
            tmp %= MOD
        cnt = tmp
    t *= 10
print(cnt[5])

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == "?":
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            d = int(D)
            for j in range(Q):
                dp[i + 1][(10 * j + d) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        base = pow(10, N - 1 - i, Q)
        D = S[i]
        if D == "?":
            for d in range(10):
                n = d * base
                for j in range(Q):
                    next_j = (j + n) % Q
                    dp[i + 1][next_j] += dp[i][j]
                    dp[i + 1][next_j] %= P
        else:
            n = int(D) * base
            for j in range(Q):
                next_j = (j + n) % Q
                dp[i + 1][(j + n) % Q] += dp[i][j]
                dp[i + 1][(j + n) % Q] %= P

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
p = 10 ** 9 + 7
dp = np.zeros((len(s)+1, 13), dtype=np.int64)
dp[0][0] = 1
for cnt, i in enumerate(reversed(s)):
	if i == "?":
		for f in range(10):
			k = pow(10, cnt, 13)*f%13
			for j in range(13):
				dp[cnt+1][(j+k)%13] = (dp[cnt+1][(j+k)%13] + dp[cnt][j])%p
	else:
		targ = int(i)
		k = pow(10, cnt, 13)*targ%13
		for j in range(13):
			dp[cnt+1][(j+k)%13] = (dp[cnt+1][(j+k)%13] + dp[cnt][j])%p
#print(dp)
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

MOD = pow(10, 9) + 7

n = len(s)
s.reverse()

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

#r = list(range(10))

#init
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[0])
    dp[0][q] = 1

r = 1

for i in range(1, n):
    r = r * 10 % 13
    # for l in range(10):
    #     r[l] = r[l] * 10 % 13

    #print(r)

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

MOD = pow(10, 9) + 7

n = len(s)
s.reverse()

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

#r = list(range(10))

#init
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[0])
    dp[0][q] = 1

for i in range(1, n):
    r = pow(10, i, 13) % 13
    # for l in range(10):
    #     r[l] = r[l] * 10 % 13

    #print(r)

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

MOD = pow(10, 9) + 7

n = len(s)
s.reverse()

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

#r = list(range(10))

#init
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[0])
    dp[0][q] = 1

for i in range(1, n):

    # for l in range(10):
    #     r[l] = r[l] * 10 % 13

    #print(r)

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

MOD = pow(10, 9) + 7

n = len(s)
s.reverse()

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

r = list(range(10))
#print(s)
#init
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[0])
    dp[0][q] = 1

for i in range(1, n):

    for l in range(10):
        r[l] = r[l] * 10 % 13

    #print(r)

    if s[i] == "?":
        for j in range(10):
            q = r[j]
            for k in range(13):
                dp[i][k] += dp[i-1][k-q]
    
    else:
        q = r[int(s[i])]
        #print(q)
        for k in range(13):
            dp[i][k] += dp[i-1][k-q]
    #print(dp[i])

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
L = len(S)
M = 13
MOD = 10**9 + 7
dp = [[0]*M for _ in range(L+1)]
dp[0][0]=1
for i in range(L):
    if S[i] == "?":
        for j in range(M):
            for k in range(10):
                s = k*pow(10, L-1-i, 13)
                dp[i+1][(j+s)%13] += dp[i][j]
                dp[i + 1][(j + s) % 13] %= MOD
    else:
        s = int(S[i])
        s *= pow(10, L - 1 - i, 13)
        for j in range(M):
            dp[i+1][(j+s)%13] += dp[i][j]
            dp[i + 1][(j + s) % 13] %= MOD

print(dp[L][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    s = list(input())

    s.reverse()

    devval = pow(10, 9) + 7

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

    # 初期値設定
    if s[0] == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s[0]) % 13] += 1

    # DP
    for i in range(1, len(s)):
        for j in range(10):
            if s[i] != "?" and s[i] != str(j):
                continue

            aaa = j * pow(10, i) % 13  # 100/13の余りな 200/13の余りなど

            # 前DPの値を今DPに加算
            for k in range(13):
                dp[i][(aaa + k) % 13] = (dp[i][(aaa + k) % 13] + dp[i - 1][k] % devval) % devval

    # 余り5の要素数が答え
    print(dp[len(s) - 1][5])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """??2??5"""
        output = """768"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """?44"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """7?4"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"""
        output = """153716888"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """?"""
        output = """1"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

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

Submission status: Time Limit Exceeded

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


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

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

  print(dp[len(S)][5] % 1_000_000_007)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


def main():
    mod = 10**9+7
    S = input()[::-1]
    amari = 1
    dp = np.zeros((len(S), 13),dtype='int64')
    if S[0] == '?':
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    for i in range(1, len(S)):
        amari = 10*amari % 13
        if S[i] == '?':
            for j in range(13):
                for si in range(10):
                    dp[i][(j+amari*si) % 13] += dp[i-1][j]
                    dp[i][(j+amari*si) % 13] %= mod

        else:
            for j in range(13):
                dp[i][(j+amari*int(S[i])) % 13] = dp[i-1][j]
    
    print(dp[len(S)-1][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

print(dp[5]%mod)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        keta = pow(10, l - i - 1)
        base = keta % 13

        if si == "?":
            for k in range(10):
                tmp = base * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = base * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        keta = pow(10, l - i - 1)
        if si == "?":
            for k in range(10):
                tmp = keta * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = keta * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10**9 + 7
s = input()
count = np.zeros(13, dtype = int)
count[0] = 1
for i in range(len(s)):
    new = np.zeros(13, dtype = int)
    for m in range(13):
        new[(m * 10) % 13] = count[m]
    count = new
    if s[i] != "?":
        div = int(s[i])
        count = np.concatenate([count[-div:], count[:-div]], 0)
    else:
        new = np.copy(count)
        for div in range(1, 10):
            new += np.concatenate([count[-div:], count[:-div]], 0)
        count = new
    count %= MOD
print(count[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10**9 + 7
s = input()
count = np.zeros(13, dtype = int)
count[0] = 1
for i in range(len(s)):
    new = np.zeros(13, dtype = int)
    for m in range(13):
        new[(m * 10) % 13] = count[m]
    count = np.copy(new)
    if s[i] != "?":
        div = int(s[i])
        count = np.concatenate([count[-div:], count[:-div]], 0)
    else:
        new = np.copy(count)
        for div in range(1, 10):
            new += np.concatenate([count[-div:], count[:-div]], 0)
        count = np.copy(new)
    count %= MOD
print(count[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10**9 + 7
s = input()
count = np.zeros(13, dtype = int)
count[0] = 1
for i in range(1, len(s) + 1):
    if s[-i] != "?":
        div = (int(s[-i]) * 10 ** (i - 1)) % 13
        count = np.concatenate([count[-div:], count[:-div]], 0)
    else:
        new = np.copy(count)
        for j in range(1, 10):
            div = (j * (10 ** (i - 1))) % 13
            new += np.concatenate([count[-div:], count[:-div]], 0)
        count = np.copy(new)
    count %= MOD
print(count[5])

Submission status: Time Limit Exceeded

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

S=list(input().rstrip('\n'))
N=len(S)

kake10 = [0,10,7,4,1,11,8,5,2,12,9,6,3]
now = {0:1,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
for i in range(N):
  now = {kake10[x]:now[x] for x in range(13)}
  if S[i]=='?':
    now2 = {}
    for x in range(13):
      now2[x] = sum(now[(x+y)%13] for y in range(4,14))
    now = now2
  else:
    a = int(S[i])
    now = {(x+a)%13:now[x] for x in range(13)}
print(now[5]%((10**9)+7))

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://kato-robotics.hatenablog.com/entry/2019/07/28/204812

S = input()

MOD = 10 ** 9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    s=input()
    return s

def printTbl(tbl):
    for l in tbl:
        print(l)

def main(s):
    MOD=10**9+7

    Rtbl=[]
    for _ in range(10):
        Rtbl.append([0]*13)
    for i in range(1,10):
        for j in range(13):
            Rtbl[i][j]=(Rtbl[i-1][j]+j)%13
    #printTbl(Rtbl)

    n=len(s)
    p0=0
    q=[]
    for i in range(n):
        if s[i]!='?':
            p0=(p0*10+int(s[i]))%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
        else:
            p0=(p0*10)%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
            q.append(1)
    #print(p0,q)

    nq=len(q)
    if nq==0:
        if p0==5:
            return 1
        else:
            return 0

    Ptbl=[]
    for _ in range(13):
        Ptbl.append([0]*nq)
    q0=q[0]
    for i in range(10):
        Ptbl[(Rtbl[i][q0]+p0)%13][0]+=1
    for j in range(1,nq):
        qj=q[j]
        for n in range(10):
            for i in range(13):
                if Ptbl[i][j-1]>0:
                    ii=(i+Rtbl[n][qj])%13
                    Ptbl[ii][j]=(Ptbl[ii][j]+Ptbl[i][j-1])%MOD
    #printTbl(Ptbl)
    return Ptbl[5][nq-1]

def main2(s):
    MOD=10**9+7
    dp=[]
    n=len(s)
    for _ in range(13):
        dp.append([0]*(n+1))
    dp[0][0]=1
    for i in range(n):
        c=s[i]
        for j in range(13):
            for k in range(10):
                if c!='?' and c!=str(k):
                   continue
                jj=(j*10+k)%13
                dp[jj][i+1]=(dp[jj][i+1]+dp[j][i])%MOD
    return dp[5][n]

if __name__=='__main__':
    s=readinput()
    ans=main2(s)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def readinput():
    s=input()
    return s

def printTbl(tbl):
    for l in tbl:
        print(l)

def main(s):
    MOD=10**9+7

    Rtbl=[]
    for _ in range(10):
        Rtbl.append([0]*13)
    for i in range(1,10):
        for j in range(13):
            Rtbl[i][j]=(Rtbl[i-1][j]+j)%13
    #printTbl(Rtbl)

    n=len(s)
    p0=0
    q=[]
    for i in range(n):
        if s[i]!='?':
            p0=(p0*10+int(s[i]))%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
        else:
            p0=(p0*10)%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
            q.append(1)
    #print(p0,q)

    nq=len(q)
    if nq==0:
        if p0==5:
            return 1
        else:
            return 0

    Ptbl=[]
    for _ in range(13):
        Ptbl.append([0]*nq)
    q0=q[0]
    for i in range(10):
        Ptbl[(Rtbl[i][q0]+p0)%13][0]+=1
    for j in range(1,nq):
        qj=q[j]
        for n in range(10):
            for i in range(13):
                if Ptbl[i][j-1]>0:
                    ii=(i+Rtbl[n][qj])%13
                    Ptbl[ii][j]=(Ptbl[ii][j]+Ptbl[i][j-1])%MOD
    #printTbl(Ptbl)
    return Ptbl[5][nq-1]

if __name__=='__main__':
    s=readinput()
    ans=main(s)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, 13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y

    else:
        X = int(X)
        X = (X * pow(10, i-1, 13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, mod=13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y

    else:
        X = int(X)
        X = (X * pow(10, i-1, mod=13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]
n = len(s)
mod = 10**9 + 7

t = [[0 for j in range(13)] for i in range(n)]
for i,x in enumerate(s):
    if i == 0:
        if x == "?":
            for j in range(0,10):
                t[i][j] += 1
        else:
            t[i][int(x)] += 1
    else:
        if x == "?":
            for k in range(13):
                for j in range(10):
                    b = (k + j*pow(10, i ,13))%13
                    t[i][b] += t[i-1][k]
                    t[i][b] %= mod
        else:
            for k in range(0,13):
                b = (k + int(x)*pow(10, i ,13))%13
                t[i][b] += t[i-1][k]
                t[i][b] %= mod
print(t[-1][5]%mod)

Submission status: Time Limit Exceeded

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