Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

??2??5

Sample Output 1

768

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

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
import 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

for i in range(n-1,-1,-1):
    if s[i] == "?":
        for j in range(13):
            for k in range(10):
                tmp = k * pow(10,n-1-i,13) 
                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 * pow(10,n-1-i,13) 
            dp[i][(j+tmp)%13] += dp[i+1][j]
            dp[i][(j+tmp)%13] %= div



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

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 = (y + np.roll(x, d2))%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:
#!/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:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    S = list(str(input().strip()))
    n = len(S)

    dp = [[0] * 13 for _ in range(n)]
    s = S.pop()
    if s == '?':
        for i in range(10):
            dp[0][i] = 1
    else:
        s = int(s)
        dp[0][s] = 1

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

    return dp[n-1][5]


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

Submission status: Time Limit Exceeded

Solution code:
s = input()

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*(10**(l-1)) % 13] = 1
else:
    dp[0][int(s[0])*(10**(l-1)) % 13] = 1

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

print(dp[len(s)-1][5] % (10**9 + 7) )

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 = 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)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
amarilist = dict()
amarilist[0] = 1
for i in range(1,N):
    amarilist[i] = amarilist[i-1] * 10 % 13
#print(amarilist)
if S[0] == '?':
    for k in range(10):
        amari =  k * amarilist[N-1] % 13
        dp[0][amari] += 1
else:
    amari = int(S[0]) * amarilist[N-1]  % 13
    dp[0][amari] = 1
#print(dp)
for j in range(1,N):
    if S[j] == '?':
        for k in range(10):
            amari = k * amarilist[N-j-1]  % 13
            for i in range(13):
                if i >= amari:
                    dp[j][i] += dp[j - 1][i - amari]
                    dp[j][i] = dp[j][i] % sosu
                else:
                    dp[j][i] += dp[j - 1][i + 13 - amari]
                    dp[j][i] = dp[j][i] % sosu
    else:
        amari = int(S[j]) * amarilist[N-j-1] % 13
        for i in range(13):
            if i >= amari:
                dp[j][i] = dp[j-1][i-amari]
            else:
                dp[j][i] = dp[j-1][i + 13 - amari]
print(dp[N-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mini = s
maxi = s
for i in range(len(s)):
    if s[i] == "?":
        if i != 0 or i!= len(s) - 1:
            mini = mini[:i] + "0" + mini[i+1:]
            maxi = maxi[:i] + "9" + maxi[i+1:]
        elif i == 0:
            mini = "0" + mini[1:]
            maxi = "9" + maxi[1:]
        elif i == len(s) - 1:
            mini = mini[:len(s)-1] + "0"
            maxi = maxi[:len(s)-1] + "9"
        
    
mini = int(mini)
maxi = int(maxi)

count = 0
i = mini
while i <= maxi:
    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
        i += 13
    else:
        i += 1
print(count % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:


S = str(input())
b = len(S)
n = (10**b+7)//13
a = str("")
ans = int(0)

for i in range(n):
    a = str(int(5) + int(13*i))
    a =a.zfill(b)
#    print(str(a))
    ans += 1
    for j in range(b):
        if S[j]!=a[j] and S[j]!="?":
            ans -=1
            break


print(ans%1000000007)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10

ans = (dp[len(S)][5]) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def do():
    S = input()
    l = len(S)
    S = S[::-1]
    dp =[[0 for _ in range(13) ] for _ in range(l + 1)]
    kurai = 1
    MOD = (10 ** 9) + 7
    dp[0][0] = 1

    for keta,c in  enumerate(S):

        if c == "?":
            for j in range(0,10):
                temp = (j * kurai) % 13
                for i in range(13):
                    dp[keta + 1][(temp + i) % 13] += (dp[keta][i] %MOD)
                    dp[keta + 1][(temp + i) % 13] %= MOD
        else:
            temp = (int(c) * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] % MOD)
                dp[keta + 1][(temp + i) % 13] %= MOD
        kurai *= 10
        keta %= MOD
    print(dp[-1][5] % MOD)

if __name__ == "__main__":
    do()

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
    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:
S = list(input())[::-1]
Now = [0 for _ in range(13)]
Next = [0 for _ in range(13)]
for i in range(len(S)):
    Next = [0 for _ in range(13)]
    if i == 0:
        if S[i] != "?":
            Next[int(S[i])] = 1
        else:
            Next = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        if S[i] != "?":
            mod = (int(S[i])*10**i)%13
            for j in range(len(Now)):
                Next[(mod+j)%13] = (Next[(mod+j)%13] + Now[j])%(10**9+7)
        else:
            mod0 = (10**i)%13
            for j in range(10):
                mod = (mod0*j)%13
                for k in range(len(Now)):
                    Next[(mod+k)%13] = (Next[(mod+k)%13] + Now[k])%(10**9+7)
    Now = Next
print(Now[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

s = s[::-1]

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


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

print(dp[len(s)-1][5] % (10**9 + 7) )

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

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

    q_pos = []
    for i, s in enumerate(S):
        if s == '?':
            q_pos.append(i)

    maxnum = int(S.replace("?", "9"))
    minnum = int(S.replace("?", "0"))
    total_num = 10 ** len(q_pos)

    start = minnum // 13
    end = maxnum // 13 + 1

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

        new_dp = defaultdict(int)
        for snum in snums:
            for n, v in dp.items():
                mod = (snum + n) % 13
                new_dp[mod] += v
        
        new_dp = {n: v % BIGNUM for n, v in new_dp.items()}
        dp = new_dp

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
ans = [[0] * 13 for _ in range(len(S))]
MOD = 10 ** 9 + 7
if S[0] == "?":
    for i in range(10):
        ans[0][i] = 1
else:
    ans[0][int(S[0])] = 1

for i, s in enumerate(S):
    if i == 0:
        continue
    if s == "?":
        for n in range(10):
            for j in range(13):
                if ans[i - 1][j] == 0:
                    continue
                ans[i][(j + n * 10 ** i) % 13] += ans[i - 1][j]
                ans[i][(j + n * 10 ** i) % 13] %= MOD
    else:
        for j in range(13):
            ans[i][(j + int(s) * 10 ** i) % 13] = ans[i - 1][j]

print(ans[-1][5])

Submission status: Time Limit Exceeded

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

def readInts():
  return [int(s) for s in input().split(" ")]

MOD = 10 ** 9 + 7

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

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

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

for s in S:
  prev = dp.copy()
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[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)]
        for number in range(10):
            remain = (number * 10 ** i) % 13
            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]
        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 = roll(remain, total_number)
    for j in range(13):
        total_number[j] = total_number[j] % (10**9 + 7)
# print(total_number[6])
print(total_number[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] == '?':
            for k in range(10):
                dp[i][j] += (dp[i-1][(13 - ((k * (10 ** i) - j) % 13))% 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:
s = input()
mini = s
maxi = s
for i in range(len(s)):
    if s[i] == "?":
        if i != 0 or i!= len(s) - 1:
            mini = mini[:i] + "0" + mini[i+1:]
            maxi = maxi[:i] + "9" + maxi[i+1:]
        elif i == 0:
            mini = "0" + mini[1:]
            maxi = "9" + maxi[1:]
        elif i == len(s) - 1:
            mini = mini[:len(s)-1] + "0"
            maxi = maxi[:len(s)-1] + "9"
        
    
mini = int(mini)
maxi = int(maxi)

count = 0
for i in range(mini,maxi+1):
    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:
S = input()
T = []
mod = int(10**9+7)

for k in range(6):
    T.append([])
    r = 10**k
    for j in range(10):
        T[-1].append(j*r%13)

dp = [1]+[0]*12
k = (len(S)-1)%6
for s in S:
    dp_new = [0]*13
    if s=='?':
        tt = T[k]
        for r in range(10):
            m = tt[r]
            for i, dd in enumerate(dp):
                dp_new[(i+m)%13] += dd
    else:
        m = T[k][int(s)]
        for i in range(13):
            dp_new[(i+m)%13] = dp[i]
    dp = [d%mod for d in dp_new]
    k=(k+5)%6

print(dp[5]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9 + 7)

s = input()
digits = len(s)

cnt = 0
for i, c in enumerate(reversed(s)):
    if c == '?':
        continue
    n = int(c) * pow(10, i, 13) % 13
    cnt += n
# print(cnt)

before = [0] * 13
first_time = True
for i, c in enumerate(reversed(s)):
    if c != '?':
        continue
    if first_time:
        for j in range(10):
            n = j * pow(10, i, 13) % 13
            before[n] += 1
        first_time = False
        continue
    current = [0] * 13
    for j in range(10):
        n = j * pow(10, i, 13) % 13
        current[n] += 1
    after = [0] * 13
    for j in range(13):
        for k in range(13):
            after[j] += before[k] * current[(13 - k + j) % 13]
        after[j] %= MOD
    before = after

if first_time:
    if cnt % 13 == 5:
        print(1)
    else:
        print(0)
else:
    print(before[(5 - (cnt % 13)) % 13])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
amari = [0 for i in range(N)]
if S[0] == '?':
    for k in range(10):
        amari =  k * (10 ** (N-1) % 13) % 13
        dp[0][amari] += 1
else:
    amari = int(S[0]) * (10 ** (N-1) % 13) % 13
    dp[0][amari] = 1
#print(dp)
for j in range(1,N):
    if S[j] == '?':
        for k in range(10):
            amari = k * (10 ** (N-j-1) % 13) % 13
            for i in range(13):
                if i >= amari:
                    dp[j][i] += dp[j - 1][i - amari]
                    dp[j][i] = dp[j][i] % sosu
                else:
                    dp[j][i] += dp[j - 1][i + 13 - amari]
                    dp[j][i] = dp[j][i] % sosu
    else:
        amari = int(S[j]) * (10 ** (N-j-1) % 13) % 13
        for i in range(13):
            if i >= amari:
                dp[j][i] = dp[j-1][i-amari]
            else:
                dp[j][i] = dp[j-1][i + 13 - amari]
print(dp[N-1][5])

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    for i in range(1, len(S)):
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    if j >= kk:
                        dp[i][j] += dp[i-1][j - kk]
                    if j < kk:
                        dp[i][j] += dp[i-1][13 + j - kk]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                k = j
                if j < m:
                    k = j + 13
                dp[i][j] = dp[i-1][k-m]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    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:
import numpy as np

s = input()
buf = [0 for i in range(13)]
s = s[::-1]
n = len(s)
# print(s)

base = 10

if s[0] == "?":
    buf = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    buf[int(s[0])] = 1
# print(buf)
# print("############")
for i in range(1,n):
    base = base%13
    nbuf = [0 for j in range(13)]
    if s[i] == "?":
        ooo = [0 for j in range(13)]
        for j in range(10):
            temp = (base*j)%13
            ooo[temp] += 1
        # print(ooo)
        for j in range(13):
            for k in range(13):
                temp = (j+k)%13
                nbuf[temp]+= buf[k]*ooo[j]
                nbuf[temp] %= (10**9+7)
    else:
        for j in range(13):
            temp = j+int(s[i])*base
            temp %= 13
            nbuf[temp] += buf[j]
            nbuf[temp] %= (10 ** 9 + 7)
    base *= 10
    buf = nbuf
    # print(buf)
    # print("*********************")

# print(buf)
print(buf[5])

Submission status: Time Limit Exceeded

Solution code:
S=list(input())

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

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
print(DP[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S=list(input())

rS=list(reversed(S))

digit_n=(10**len(S)-5)//13

cnt=0
tryc=[]
for i in range(digit_n+1):
    trya=13*i+5
    tryb=[0]*len(S)
    tryc=list(reversed(list(str(trya))))
    for j in range(len(tryc)):
        tryb[j]+=int(tryc[j])
    for j in range(len(rS)):
        if rS[j]!="?":
            if int(rS[j])!=tryb[j]:
                break
        if j==len(rS)-1:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = [-1 if c == '?' else int(c) for c in list(input())]
    MOD = 10 ** 9 + 7
    n = len(s)
    dp = [[0] * 13 for _ in range(n)]

    if s[n-1] == -1:
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][s[n-1]] = 1
    for i in range(1, n):
        i10 = 10 ** i % 13
        c = s[n-i-1]
        for k in range(13):
            if c == -1:
                for j in range(10):
                    m = (i10 * j + k) % 13
                    dp[i][m] += dp[i-1][k]
                    dp[i][m] %= MOD
            else:
                m = (i10 * c + k) % 13
                dp[i][m] += dp[i-1][k]
                dp[i][m] %= MOD
    print(dp[n-1][5])


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9+7
s = list(input())[:-1]

s = s[::-1]

ls = len(s)

mod_13_list = [ (10**i) % 13 for i in range(6) ]

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

t = 1
for i in range(1,ls):
    r = mod_13_list[t]
    t = ( t + 1 ) % 6
    new_dp_list = [ 0 for i in range(13) ]
    if s[i] != "?":
        p = int(s[i])
        q = ( p * r ) % 13
        for j in range(13):
            new_dp_list[(j+q)%13] += dp_list[j]
    
    else:
        for k in range(10):
            q = (k * ( 10 ** i) ) % 13
            for j in range(13):
                new_dp_list[(j+q)%13] += dp_list[j]
    
    dp_list = [ i % mod for i in new_dp_list ]

print(dp_list[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
dp = []
for i in range(13):
    temp = [0] * len(s)
    dp.append(temp)
amari_list = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
for i in range(len(s)):
    amari_list.append([10 * amari_list[-1][i] for i in range(10)])
# j桁目がxのとき13で割ったあまり
def amari(x, j):
    if x != "?":
        x = int(x)
        return [amari_list[j][x]]
    else:
        return amari_list[j]
for i in amari(s[-1], 0):
    dp[i][0] = 1
for i in range(1, len(s)):
    for j in range(13):
        for k in amari(s[-i-1], i):
            dp[j][i] += dp[(j - k) % 13][i - 1]
            dp[j][i] %= mod
print(dp[5][len(s) - 1])

Submission status: Time Limit Exceeded

Solution code:

S = input()
l = len(S)
S = S[::-1]
dp =[[0 for _ in range(13) ] for _ in range(l + 1)]
amari = dict(zip( list(range(0,13)),[0] *13 ))
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta,c in  enumerate(S):

    if c == "?":
        for j in range(0,10):
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += dp[keta][i]
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += dp[keta][i]
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()
index = []
for i in range(len(s)):
    if s[i] == "?":
        index.append(i)
        
mini = s
for i in index:
    if i != 0 or i!= len(s) - 1:
        mini = mini[:i] + "0" + mini[i+1:]
    elif i == 0:
        mini = "0" + mini[1:]
    elif i == len(s) - 1:
        mini = mini[:len(s)-1] + "0"
mini = int(mini)

maxi = s
for i in index:
    if i != 0 or i!= len(s) - 1:
        maxi = maxi[:i] + "9" + maxi[i+1:]
    elif i == 0:
        maxi = "9" + maxi[1:]
    elif i == len(s) - 1:
        maxi = maxi[:len(s)-1] + "9"
maxi = int(maxi)

count = 0
for i in range(mini,maxi+1):
    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:
#  --*-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):
                    j2 = (j+d2)%13
                    y[j2] = (y[j2] + x[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()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
print(DP[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#N=list(map(int, input().split()))
S=input()
big=10**9+7

lis=[0]*13

if S[0]=="?":
	lis=[1]*10+[0]*3
else:
	lis[int(S[0])]=1
S=S[1:]

for i in S:
	newlis=[0]*13
	if i=="?":
		for j in range(10):#はてなの中身
			for k in range(13):#前のあまり
				newlis[(10*k+j)%13]+=lis[k]
	else:
		for k in range(13):
			newlis[(10*k+int(i))%13]+=lis[k]
	lis=newlis
print(lis[5]%big)

Submission status: Time Limit Exceeded

Solution code:
import math

S = input()
l = len(S)
S = S[::-1]
dp =[[0 for _ in range(13) ] for _ in range(l + 1)]
amari = dict(zip( list(range(0,13)),[0] *13 ))
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta,c in  enumerate(S):

    if c == "?":
        for j in range(0,10):
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += dp[keta][i]
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += dp[keta][i]
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] % MOD)

Submission status: Time Limit Exceeded

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

s = s[::-1]

ls = len(s)

mod_13_list = [ (10**i) % 13 for i in range(6) ]

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

t = 1
for i in range(1,ls):
    r = mod_13_list[t]
    t = ( t + 1 ) % 6
    new_dp_list = [ 0 for i in range(13) ]
    if s[i] != "?":
        p = int(s[i])
        q = ( p * r ) % 13
        for j in range(13):
            new_dp_list[(j+q)%13] += dp_list[j]
    
    else:
        for k in range(10):
            q = (k * ( 10 ** i) ) % 13
            for j in range(13):
                new_dp_list[(j+q)%13] += dp_list[j]
    
    dp_list = [ i % mod for i in new_dp_list ]

    
print(dp_list[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for j in range(10):
      for k in range(13):
        DP[i+1][k]+=DP[i][R[r][j][k]]
  else:
    for k in range(13):
      DP[i+1][k]+=DP[i][R[r][int(s[i])][k]]
print(DP[n][5]%(10**9+7))