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:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def split_33(N:str):
    A = []
    B = []
    for i in range(len(N)-3, -3, -6):
        s = max(0,i)
        A.append(N[s:i+3])
    for i in range(len(N)-6, -3, -6):
        s = max(0,i)
        B.append(N[s:i+3])
    return A,B

    

def solve(S: str):
    min_n = int(S.replace("?","0"))
    max_n = int(S.replace("?","9"))

    while min_n % 13 != 5:
        min_n += 1

    c = min_n

    n = 0
    while c <= max_n:
        c_str = str(c).zfill(len(S))


        for i,(a,b) in enumerate(zip(c_str,S)):
            if b != '?' and a != b:
                #if int(a) < int(b):
                #    if i < len(S) - 2 :
                #        next_c = int(c_str[0:i] + b + S[i+1:].replace("?","0"))
                #    else:
                #        next_c = int(c_str[0:i] + b)

                #    while next_c % 13 != 5:
                #        next_c += 1

                #    if next_c - c > 13:
                #        next_c = c
                #    else:
                #        c += 13
                #else:
                #    c += 13
                c += 13
                break
        else:
            n += 1
            c += 13

    print(n % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  f=(t[d]=='?')
  for i in range(k):
    for x in range(z if f else 1):
      r=pow(z,d,k)
      r*=int(x) if f else int(t[d])
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
import re
S = str(input())

S = S.replace('?','.')

MOD = 1000000007
count = 0
for i in range(10**(len(S))):
    match_result = re.match(S, str(i).zfill(len(S)))
    if match_result is None:
        continue
    if i % 13 == 5:
        count += 1

print(count%MOD)

Submission status: Time Limit Exceeded

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

def check(n):
  for i in range(N):
    if S[i] != "?":
      d = 10 ** (N - i - 1)
      c = (n // d) % 10
      if c != int(S[i]):
        return False
  return True

num_max = 0
for i in range(N):
  num_max *= 10
  if S[i] != "?":
    num_max += int(S[i])
  else:
    num_max += 9

ans = 0
num = 5
while num <= num_max:
  if check(num):
    ans += 1
  num += 13
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        for x in range(10):
            each_extras[cnt][x] = x * 10 ** i % 13
        cnt += 1

each_extras = np.array(each_extras)
# print(extra)
dp = np.array([[0 for i in range(13)] for j in range(cnt+1)])
dp[0][extra % 13] = 1
for i in range(cnt):
    for each in each_extras[i]:
        # for j in range(13):
            # dp[i+1][(j + each) % 13] += dp[i][j] % mod
        # print(each)
        dp[i+1] += np.roll(dp[i],each) % mod

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

c = {}
for i, j in enumerate(S):
    if j != "?":
        c[i] = j

T = [s if s != "?" else "9" for s in S]
T = int(''.join(T))

ans = 0
for i in range(T // 13 + 1):
    f = False
    s = '{0:0>{1}}'.format(i * 13 + 5, len(S))
    for k, v in c.items():
        if s[k] != v:
            f = True
            break
    if f is not True:
        ans += 1
print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


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

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            #dig = 10**i
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   # dp[i+1][j] += dp[i][(k*dig+j) % 13]
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            #dig = 10**i
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                #dp[i+1][j] = dp[i][(int(S[i])*dig+j) % 13]
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
m = int(1e9 + 7)
s = input()[::-1]
a = []
val = 0
p = 1
for c in s:
    if c == '?':
        a.append(p)
    else:
        val += (p * int(c)) % 13
        val %= 13
    p = (p * 10) % 13
val = (5 - val) % 13
dp = [0] * 13
dp[0] = 1
for x in a:
    new_dp = [0] * 13
    for i in range(13):
        if dp[i] == 0: continue
        for j in range(10):
            k = (i + j * x) % 13
            new_dp[k] += dp[i]
            new_dp[k] %= m
    dp = new_dp
print(dp[val])

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
from collections import defaultdict
O=defaultdict(int)
O[5]=1
mod=10**9+7
for i in range(N):
    On=defaultdict(int)
    for o in O.keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    On[x//10]+=O[o]
        else:
            for j in range(10):
                x=13*j+o
                On[x//10]=(On[x//10]+O[o])%mod
    O=On
print(O[0])

Submission status: Time Limit Exceeded

Solution code:
import copy
S = input()
s = len(S)
MOD = 10**9+7
D = [0]*13
S = S[::-1]
for i in range(s):
    if i==0:
        if S[i]=="?":
            for j in range(10):
                D[j]+=1
        else:
            D[int(S[i])]+=1
    else:
        P = copy.copy(D)
        if S[i]=="?":
            p = 10**i
            for j in range(1,10):
                q = (j*p)%13
                for k in range(13):
                    D[(k+q)%13] += P[k]
            continue
        else:
            p = int(S[i])*(10**i)
            D = P[13-p%13:]+P[:13-p%13]
print(D[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

import numpy as np

MOD = int(10**9 + 7)

def main():
    S = input()
    d = 1
    e = 0
    x = np.zeros(13, dtype='int64')
    x[0] = 1

    for s in reversed(S):
        if s == '?':
            y = np.zeros(13, dtype='int64')

            for i in range(10):
                d2 = d*i%13
                y +=  np.roll(x, d2)

            x = y%MOD

        else:
            e += d*int(s)
            e %= 13

        d = d*10%13
        
    print(x[(5-e)%13])





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    s=input()
    l=[]
    for i in range(len(s)-1,-1,-1):
        if s[i] in '0123456789':l.append(int(s[i]))
        else: l.append(-1)
    dp=[0]*13
    if l[0]==-1:
        for i in range(10):dp[i]=1
    else: dp[l[0]]=1
    for i in range(1,len(s)):
        if l[i] in range(10):
            n=l[i]*10**i%13
            dp=dp[13-n:]+dp[:13-n]
        if l[i]==-1:
            tdp=[0]*13
            for j in range(10):
                n=j*10**i%13
                for k in range(13):
                    tdp[(k+n)%13]=(tdp[(k+n)%13]+dp[k])%(10**9+7)
            for j in range(13):dp[j]=tdp[j]
    print(dp[5])
sol()

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = []
x = 5
flag = True
count = 0
idx = []

while flag:
    if x < 10**(len(s) - 1):
        x = str(x)
        o = '0' * (len(s)  - len(x))
        b = o + str(x)
        ans.extend([b])
    elif x < 10**len(s):
        ans.extend([str(x)])
    else:
        flag = False
    x = int(x)
    x += 13

for i in range(len(s)):
    if s[i] != '?':
        idx.extend([i])

for a in ans:
    cnt = 0
    for i in idx:
        if a[i] != s[i]:
            cnt += 1
    if cnt == 0:
        count += 1
print(count % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
ress = [[(10 ** i * j) % 13 for j in range(10)] for i in range(6)]

mod = 10 ** 9 + 7

keta = 0
res = 0
state = [1] + [0] * 12
for s in reversed(input()):
    if s == "?":
        new_state = [0] * 13
        for i in range(13):
            for r in ress[keta % 6]:
                new_state[i] += state[(i - r) % 13]
            new_state[i] %= mod
        state = new_state
    else:
        res += ress[keta % 6][int(s)]
    keta += 1

res = (5 - res) % 13

print(state[res] % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import defaultdict, deque
import math
from math import factorial
import fractions
import re

BIGNUM = 10 ** 9 + 7

MOD13 = {}
for i in range(13):
    for j in range(13):
        MOD13[(i, j)] = (i + j) % 13

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

    dp = {0: 1}
    for i in range(len(S)):
        s = S[-(i+1)]
        if s == "?":
            snums = [(k * 10 ** i) % 13 for k in range(10)]
        else:
            snums = [(int(s) * 10 ** i) % 13]

        new_dp = defaultdict(int)
        for snum in snums:
            for n, v in dp.items():
                mod = MOD13[(snum, n)]
                new_dp[mod] += v

        dp = new_dp

    if not 5 in dp:
        dp[5] = 0
    print(dp[5] % BIGNUM)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0
for i in range(10**(len(s))):
    if i % 13 == 5:
        flag = True
        i_str = str(i)
        if len(i_str) < len(s):
            i_str = "0" * (len(s) - len(i_str)) + i_str
        for j in range(len(s)):
            if s[j] == "?" or i_str[j] == s[j]:
                continue
            else:
                flag = False
                break
        if flag == True:
            count += 1
print(count % (10**9 + 7))

Submission status: Time Limit Exceeded

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

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = {i: 0 for i in range(13)}
  if s[-1] == '?':
    for i in range(10):
      sd[i] = 1
  else:
    sd[int(s[-1])] = 1
  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    tmpd = {r: 0 for r in range(13)}
    if _s != '?':
      rem = int(_s) * pow(10, i) % 13
      for j in range(13):
        tmpd[(j+rem)%13] = sd[j]
    else:
      for k in range(10):
        rem = k * pow(10, i) % 13
        for j in range(13):
          tmpd[(j+rem)%13] += sd[j]
          tmpd[(j+rem)%13] %= MOD
    sd = tmpd
  print(sd[5])


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

dp[0][0] = (1,1)
k = 1

for s in S:
  if ('?' == s):
    L = list(range(10))
  else:
    L = [int(s)]

  for l in L:
    for i in range(13):
      if (dp[k-1][i][1] == 1):
        tmp = (i * 10) + l
        m = tmp % 13
        c = (tmp // 13)
        dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod, 1)
  k += 1
print(dp[k-1][5][0])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    d = 0
    k = 10 ** (i+1)
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import math
s = input()
n = len(s)
div = 1000000000 + 7

#i文字以降で13で割った余りがj...dp[i][j]

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


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



print(dp[0][5] % div)

Submission status: Time Limit Exceeded

Solution code:
MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = {i: 0 for i in range(13)}
  if s[-1] == '?':
    for i in range(10):
      sd[i] = 1
  else:
    sd[int(s[-1])] = 1
  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    tmpd = {r: 0 for r in range(13)}
    if _s != '?':
      rem = int(_s) * pow(10, i) % 13
      for j in range(13):
        tmpd[(j+rem)%13] = sd[j]
    else:
      for k in range(10):
        rem = k * pow(10, i) % 13
        for j in range(13):
          tmpd[(j+rem)%13] += sd[j]
          tmpd[(j+rem)%13] %= MOD
    sd = tmpd
  print(sd[5])


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:


# 10のp乗の桁のmod 13
def coefficient(p):
    a = p % 6
    if a == 0:
        return 1
    if a == 1:
        return 10
    if a == 2:
        return 9
    if a == 3:
        return 12
    if a == 4:
        return 3
    if a == 5:
        return 4


def submit():
    s = input()
    clist = [c for c in s]
    n = len(clist)
    ansmod = 10 ** 9 + 7

    # dp[x][y] : 上位x桁まで見たときに、y mod 13になるパターン数
    dp = [
        [0 for _ in range(13)] for _ in range(n + 1)
    ]

    dp[0][0] = 1

    for i, c in enumerate(clist):
        if c == '?':
            for x in range(10):
                for y in range(13):
                    dig_mod = y
                    dig_mod += coefficient(n - i - 1) * x
                    dig_mod %= 13
                    dp[i + 1][dig_mod] += dp[i][y]
                    dp[i + 1][dig_mod] %= ansmod
        else:
            x = int(c)
            for y in range(13):
                dig_mod = y
                dig_mod += coefficient(n - i - 1) * x
                dig_mod %= 13
                dp[i + 1][dig_mod] += dp[i][y]
                dp[i + 1][dig_mod] %= ansmod

    print(dp[n][5] % ansmod)


if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

Solution code:
# def roll(roll_number, roll_list):
#     len_list = len(roll_list)
#     ans_list = [0 for _ in range(len_list)]
#     for ii, n in enumerate(roll_list):
#         inde = (ii + roll_number) % len_list
#         ans_list[inde] = n
#     return ans_list


sentence = input()
len_sentence = len(sentence)
total_number = [0 for _ in range(13)]
sentence = sentence[::-1]
# for i in range(len_sentence):
#     sentence_index = len_sentence - 1 - i  # 後ろから
#     number_str = sentence[sentence_index]
for i, number_str in enumerate(sentence):
    if number_str == '?':
        total_number_list = [0 for _ in range(13)]
        remain_list = []
        for number in range(10):
            remain = (number * 10 ** i) % 13
            remain_list.append(remain)
            # if i == 0:
            #     tmp_number = [0 for _ in range(13)]
            #     tmp_number[remain] = 1
            # else:
            #     tmp_number = roll(remain, total_number)
            # for j in range(13):
            #     total_number_list[j] += tmp_number[j]
            if i == 0:
                total_number_list[remain] = 1
            else:
                for j in range(13):
                    total_number_list[(j+remain)%13] += total_number[j]
        total_number = total_number_list
        for j in range(13):
            total_number[j] = total_number[j] % (10 ** 9 + 7)
    else:
        number = int(number_str)
        remain = (number * 10**i) % 13
        if i == 0:
            total_number[remain] = 1
        else:
            total_number_list = [0 for _ in range(13)]
            for j in range(13):
                total_number_list[(j + remain) % 13] += total_number[j]
            total_number = total_number_list
            # total_number = roll(remain, total_number)
    # for j in range(13):
    #     total_number[j] = total_number[j] % (10**9 + 7)
print(total_number[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for _ in range(13)] for _ in range(len(S))]

big = (10 ** 9) + 7
S = S[::-1]
for i in range(13):
    if S[0] == '?':
        if i < 10:
            dp[0][i] = 1
    else:
        if int(S[0]) == i:
            dp[0][i] = 1
for i in range(1, len(S)):
    for j in range(13):
        if S[i] == '?':
            dp[i][j] = dp[i-1][j]
            a = (10 ** i) % 13
            dp[i][j] += (dp[i-1][(j-a)%13]
                         + dp[i-1][(j-2*a)%13]
                         + dp[i-1][(j-3*a)%13]
                         + dp[i-1][(j-4*a)%13]
                         + dp[i-1][(j-5*a)%13]
                         + dp[i-1][(j-6*a)%13]
                         + dp[i-1][(j-7*a)%13]
                         + dp[i-1][(j-8*a)%13]
                         + dp[i-1][(j-9*a)%13]) % big
        else:
            a = int(S[i])
            dp[i][j] += (dp[i-1][(13 - ((a * (10 ** i) - j) % 13)) % 13]) % big

print(dp[len(S)-1][5] % big)

Submission status: Time Limit Exceeded

Solution code:
import copy
S = input()
s = len(S)
MOD = 10**9+7
D = [0]*13
S = S[::-1]
for i in range(s):
    if i==0:
        if S[i]=="?":
            for j in range(10):
                D[j]+=1
        else:
            D[int(S[i])]+=1
    else:
        P = copy.copy(D)
        if S[i]=="?":
            p = 10**i
            for j in range(1,10):
                R = P[13-(j*p)%13:]+P[:13-(j*p)%13]
                for k in range(13):
                    D[k]+=R[k]
            continue
        else:
            p = int(S[i])*(10**i)
            D = P[13-p%13:]+P[:13-p%13]
print(D[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        for x in range(10):
            each_extras[cnt][x] = x * 10 ** i % 13
        cnt += 1

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for each in each_extras[i]:
        for j in range(13):
            dp[i+1][(j + each) % 13] += dp[i][j] % mod

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
s_base = int(s.replace('?', '0'))
digit = reversed(list(s))
sumd = 0
s10 = 4 # Before 1
hatena = []
for i, x in enumerate(digit):
    s10 = (10 * s10) % 13
    if x == '?':
        hatena.append(s10)
    else:
        sumd += int(x) * s10
        sumd %= 13

# sum( hatena[i] * x ) を満たすxの組み合わせを求める
mod = 10**9 + 7

dp = [[0] * 13 for _ in range(len(hatena) + 2)]
# dp[i][x] hatena[:i]の和を13で割った余りがxである整数の数
dp[0][0] = 1

for i in range(len(hatena)):
    for x in range(13):
        for num in range(10):
            j = (x + num*hatena[i]) % 13
            dp[i+1][j] += dp[i][x]
            dp[i+1][j] %= mod

print(dp[len(hatena)][(5-sumd)%13])
"""
print(hatena)
print(sumd)
print(dp)
"""

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

MOD = int(10**9 + 7)

def main():
    S = input()
    d = 1
    e = 0
    x = [0]*13
    x[0] = 1

    for s in reversed(S):
        if s == '?':
            y = [0]*13
            for i in range(10):
                d2 = d*i%13
                for j in range(13):
                    y[(j+d2)%13] += x[j]

            for j in range(13):
                y[j] %= MOD


            x = y

        else:
            e += d*int(s)
            e %= 13

        d = d*10%13
        
    print(x[(5-e)%13])





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm]
print(mem[len(S) - 1][5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(N):
    pp = dp.copy()
    dp = [0 for _ in range(13)]
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys

for S in sys.stdin:
    break
S = S.strip()
le = len(S)

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[-1] == "?" else [int(x == int(S[-1])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[-i-1] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[-i-1])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import re
s=input()
m=10**9+7
mn=int(s.replace('?','0'))
mx=int(s.replace('?','9'))
r=re.compile('^'+s.replace('?','.')+'$')
ans=0
for i in range(mn,mn+13):
    if i%13==5:
        mn=i
        break
for i in range(mn,mx+1,13):
    if i%13==5:
        t=str(i).zfill(len(s))
        if re.match(r,t):
            ans+=1
print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = []
x = 5
flag = True
count = 0
idx = []

while flag:
    if x < 10**(len(s) - 1):
        x = str(x)
        o = '0' * (len(s)  - len(x))
        b = o + str(x)
        ans.append(b)
    elif x < 10**len(s):
        ans.append(str(x))
    else:
        flag = False
    x = int(x)
    x += 13

for i in range(len(s)):
    if s[i] != '?':
        idx.append(i)

for a in ans:
    cnt = 0
    for i in idx:
        if a[i] != s[i]:
            cnt += 1
    if cnt == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
s = input()
n = len(s)
div = 1000000000 + 7

#i文字以降で13で割った余りがj...dp[i][j]

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


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



print(dp[0][5]%div)

Submission status: Time Limit Exceeded

Solution code:
s = input()

s = s[::-1]

dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]

l = len(s)


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

m = 1
MOD = 10**9 +7

for i in range(1,len(s)):
    m = m*10 % 13

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

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=[]
for i in range(len(s)-1,-1,-1):
    if s[i] in '0123456789':l.append(int(s[i]))
    else: l.append(-1)
dp=[0]*13
if l[0]==-1:
    for i in range(10):dp[i]=1
else: dp[l[0]]=1
for i in range(1,len(s)):
    if l[i] in range(10):
        n=l[i]*10**i%13
        dp=dp[13-n:]+dp[:13-n]
    if l[i]==-1:
        tdp=[0]*13
        for j in range(10):
            n=j*10**i%13
            for k in range(13):
                tdp[(k+n)%13]=(tdp[(k+n)%13]+dp[k])%(10**9+7)
        for j in range(13):dp[j]=tdp[j]
print(dp[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))

S.reverse()

extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        for x in range(10):
            each_extras[cnt][x] = x * 10 ** i % 13
        cnt += 1

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for each in each_extras[i]:
        for j in range(13):
            dp[i+1][(j + each) % 13] += dp[i][j] % mod

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a = [0] * 13
n = [0] * 13

def calc(d, num):
#    shift = (num * (10 ** d))%13
    shift = num
    for _ in range(d):
        shift *= 10
        shift %= 13
    if d==0:
        n[shift] = 1
    else:
        for i in range(13):
            n[(i+shift)%13] += a[i]
    

for d, s in enumerate(S):
    if s=='?':
        for i in range(10):
            calc(d, i)
    else:
        calc(d, int(s[0]))
    a, n = n, a
    for i in range(13):
        a[i] %= 1000000007
        n[i] = 0

print(a[5])

Submission status: Time Limit Exceeded

Solution code:
def roll(roll_number, roll_list):
    len_list = len(roll_list)
    ans_list = [0 for _ in range(len_list)]
    for ii, n in enumerate(roll_list):
        inde = (ii + roll_number) % len_list
        ans_list[inde] = n
    return ans_list


sentence = input()
len_sentence = len(sentence)
total_number = [0 for _ in range(13)]
for i in range(len_sentence):
    sentence_index = len_sentence - 1 - i  # 後ろから
    number_str = sentence[sentence_index]
    if number_str == '?':
        total_number_list = [0 for _ in range(13)]
        remain_list = []
        for number in range(10):
            remain = (number * 10 ** i) % 13
            remain_list.append(remain)
            # if i == 0:
            #     tmp_number = [0 for _ in range(13)]
            #     tmp_number[remain] = 1
            # else:
            #     tmp_number = roll(remain, total_number)
            # for j in range(13):
            #     total_number_list[j] += tmp_number[j]
            if i == 0:
                total_number_list[remain] = 1
            else:
                for j in range(13):
                    total_number_list[(j+remain)%13] += total_number[j]
        total_number = total_number_list
    else:
        number = int(number_str)
        remain = (number * 10**i) % 13
        if i == 0:
            total_number[remain] = 1
        else:
            total_number_list = [0 for _ in range(13)]
            for j in range(13):
                total_number_list[(j + remain) % 13] += total_number[j]
            total_number = total_number_list
            # total_number = roll(remain, total_number)
    for j in range(13):
        total_number[j] = total_number[j] % (10**9 + 7)
print(total_number[5])