Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

??2??5

Sample Output 1

768

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

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

Submission status: Time Limit Exceeded

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] = (l2[t] + l1[k]) % MOD
        l1 = l2
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]
n = len(s)
mod = 10**9+7
#dp[i][j] 下からi番目まで見た時の余りをjとする
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
digit = -1
for i in range(n):
  digit += 1
  if s[i] != "?":
    x = 10**digit
    for j in range(13):
      dp[i+1][j] = dp[i][(j-int(s[i])*x)%13]
  else:
    for j in range(13):
      flag = 0
      for k in range(10):
        x = k*(10**digit)
        flag += dp[i][(j-x)%13] 
      dp[i+1][j] = flag%mod
print(dp[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]
n = len(s)
mod = 10**9+7
#dp[i][j] 下からi番目まで見た時の余りをjとする
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
digit = -1
for i in range(n):
  digit += 1
  if s[i] != "?":
    x = 10**digit
    for j in range(13):
      dp[i+1][j] = dp[i][(j-int(s[i])*x)%13] % mod
  else:
    for j in range(13):
      flag = 0
      for k in range(10):
        x = k*(10**digit)
        flag += dp[i][(j-x)%13] 
      dp[i+1][j] = flag%mod
print(dp[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]
n = len(s)
mod = 10**9+7
#dp[i][j] 下からi番目まで見た時の余りをjとする
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
digit = -1
for i in range(n):
  digit += 1
  if s[i] != "?":
    x = 10**digit
    for j in range(13):
      dp[i+1][j] = dp[i][(j-int(s[i])*x)%13] % mod
  else:
    for j in range(13):
      flag = 0
      for k in range(10):
        x = k*(10**digit)%13
        flag += dp[i][(j-x)%13] 
      dp[i+1][j] = flag%mod
print(dp[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]
n = len(s)
mod = 10**9+7
#dp[i][j] 下からi番目まで見た時の余りをjとする
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
digit = -1
for i in range(n):
  digit += 1
  if s[i] != "?":
    x = 10**digit
    for j in range(13):
      dp[i+1][j] = dp[i][(j-int(s[i])*x)%13] % mod
  else:
    for j in range(13):
      flag = 0
      for k in range(10):
        x = k*(10**digit)%13
        flag += dp[i][(j-x)%13] % mod
      dp[i+1][j] = flag
print(dp[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    s=readline().strip()
    n=len(s)

    dp=np.zeros(13,dtype=np.int64)
    tmp1=np.arange(10,dtype=np.int64)
    keta=10
    for i in range(n-1,-1,-1):
        if i==n-1:
            if s[i]=="?":
                dp[0:10]=1
            else:
                dp[int(s[i])]=1
        else:
            if s[i]=="?":
                tmp2=(keta*tmp1)%13
            else:
                tmp2=(keta*int(s[i]))%13
            nex=np.zeros(13,dtype=np.int64)
            for j in range(13):
                nex[(tmp2+j)%13]+=dp[j]
            nex%=mod
            dp=nex
            keta*=10
            keta%=13

    print(dp[5])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    s=readline().strip()
    n=len(s)

    dp=np.zeros((n,13),dtype=np.int64)
    tmp1=np.array(range(10),dtype=np.int64)%13
    keta=10
    for i in range(n-1,-1,-1):
        if i==n-1:
            if s[i]=="?":
                dp[i,0:10]=1
            else:
                dp[i][int(s[i])]=1
        else:
            if s[i]=="?":
                tmp2=(keta*tmp1)%13
            else:
                tmp2=(keta*int(s[i]))%13
            for j in range(13):
                dp[i,(tmp2+j)%13]+=dp[i+1,j]
            dp[i]%=mod
            keta*=10
            keta%=13

    print(dp[0][5])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    s=readline().strip()
    n=len(s)

    dp=np.zeros((n,13),dtype=np.int64)
    tmp1=np.array(range(10),dtype=np.int64)%13
    keta=10
    for i in range(n-1,-1,-1):
        if i==n-1:
            if s[i]=="?":
                dp[i,0:10]=1
            else:
                dp[i][int(s[i])]=1
        else:
            if s[i]=="?":
                tmp2=(keta*tmp1)%13
            else:
                tmp2=(keta*int(s[i]))%13
            for j in range(13):
                dp[i][(tmp2+j)%13]+=dp[i+1][j]
            dp[i]%=mod
            keta*=10
            keta%=13

    print(dp[0][5])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
a = list(range(13))
b = []
for i in a:
    num = int(str(i) + '0') % 13
    l = []
    for j in range(13):
        l.append((num+j)%13)
    b.append(l)

s = input()
MOD = 10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s))]
if s[0] == '?':
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][int(s[0])] += 1

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

Submission status: Time Limit Exceeded

Solution code:
#!python3

import numpy as np

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = np.zeros(13, dtype=int)
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = np.zeros(13, dtype=int)
        for j in range(10):
            x = w[i - 1] * j % 13
            l2 += np.roll(l1, x)
        l2 %= MOD
        l1 = l2
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import numpy as np

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = np.zeros(13, dtype=int)
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = np.zeros(13, dtype=int)
        for j in range(10):
            x = w[i - 1] * j % 13
            l2 += np.roll(l1, x)
            l2 %= MOD
        l1 = l2
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import numpy as np

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    dp = np.zeros((n + 1, 13), dtype=int)
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(10):
            x = w[i - 1] * j % 13
            dp[i] += np.roll(dp[i - 1], x)
            dp[i] %= MOD
    
    ans = dp[-1][m]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    for i in range(n):
        c=0
        if(s[i]=="?"):c=-1
        else:c = int(s[i])

        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            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
    res = dp[n][5]

    print(res)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
def SMI(): return input().split()
def SLI(): return list(input())
 
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
 
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
 
def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD
 
        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)
 
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        # s = S[-(i + 1)]
        # s = S[i]
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul *= 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul *= 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for ques in range(10):
                k = (ques * mul) % 13
                for j in range(13):
                    dp[i+1][(j+k)%13] += dp[i][j]
        else:
            k = (int(S[i]) * mul) % 13
            for j in range(13):
                dp[i+1][(j+k)%13] += dp[i][j]

        mul *= 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for ques in range(10):
                k = (ques * mul) % 13
                for j in range(13):
                    dp[i+1][(j+k)%13] += dp[i][j]
        else:
            k = (int(S[i]) * mul) % 13
            for j in range(13):
                dp[i+1][(j+k)%13] += dp[i][j]

        mul *= 10
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

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

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

    mul = 1
    for i in range(len(S)):
        next_dp = [0] * 13
        if S[i] == '?':
            for k in range(10):
                for j in range(13):
                    jj = ((k * mul) + j) % 13
                    next_dp[jj] += dp[j]
                    next_dp[jj] %= MOD
        else:
            num = int(S[i])
            for j in range(13):
                jj = ((num * mul) + j) % 13
                next_dp[jj] += dp[j]
                next_dp[jj] %= MOD

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

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

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

    mul = 1
    for i in range(len(S)):
        next_dp = [0] * 13
        if S[i] == '?':
            for k in range(10):
                for j in range(13):
                    jj = ((k * mul) + j) % 13
                    next_dp[jj] += dp[j]
                    next_dp[jj] %= MOD
        else:
            num = int(S[i])
            for j in range(13):
                jj = ((num * mul) + j) % 13
                next_dp[jj] += dp[j]
                next_dp[jj] %= MOD

        mul *= 10
        dp = next_dp

    print(dp[5])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def solve():

    S = ['0'] + list(reversed(input()))
    N = len(S) - 1
    dp = [[-1 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1

    for i in range(1, N + 1):
        if S[i] == '?':
            for j in range(13):
                if dp[i - 1][j] != -1:
                    for k in range(10):
                        n = k * (10 ** (i - 1))
                        r = n % 13
                        jj = (j + r) % 13
                        if dp[i][jj] == -1:
                            dp[i][jj] = dp[i - 1][j]
                        else:
                            dp[i][jj] = (dp[i][jj] + dp[i - 1][j]) % mod

        else:
            for j in range(13):
                if dp[i - 1][j] != -1:
                    n = int(S[i]) * (10 ** (i - 1))
                    r = n % 13
                    jj = (j + r) % 13
                    dp[i][jj] = dp[i - 1][j]

    ans = dp[N][5] if dp[N][5] != -1 else 0
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def solve():

    S = ['0'] + list(reversed(input()))
    N = len(S) - 1
    dp = np.full((N + 1, 13), -1, dtype='i8')
    dp[0][0] = 1

    for i in range(1, N + 1):
        if S[i] == '?':
            for j in range(13):
                if dp[i - 1][j] != -1:
                    for k in range(10):
                        n = k * (10 ** (i - 1))
                        r = n % 13
                        jj = (j + r) % 13
                        if dp[i][jj] == -1:
                            dp[i][jj] = dp[i - 1][j]
                        else:
                            dp[i][jj] = (dp[i][jj] + dp[i - 1][j]) % mod

        else:
            for j in range(13):
                if dp[i - 1][j] != -1:
                    n = int(S[i]) * (10 ** (i - 1))
                    r = n % 13
                    jj = (j + r) % 13
                    dp[i][jj] = dp[i - 1][j]

    ans = dp[N][5] if dp[N][5] != -1 else 0
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

for i in range(n):
    digit = n-1-i
    x = s[digit]
    X = []
    if x != '?':
        X.append(int(x)*pow(10, i, 13) % 13)
    else:
        for num in range(10):
            X.append(num*pow(10, i, 13) % 13)
    for j in range(13):
        for x in X:
            dp[i+1][(j+x) % 13] += dp[i][j]
            dp[i+1][(j+x) % 13] %= MOD

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
class Mod13DPTable:
    MOD = 10**9 + 7
    def __init__(self, length):
        self.mod13 = [{j:0 for j in range(13)} for i in range(length)]
        self.MOD = 10**7 + 7
    def set_start(self, units_digit):
        if units_digit == '?':
            for i in range(10):
                self.mod13[0][i] = 1
        else:
            self.mod13[0][int(units_digit)] = 1
    def get_table(self, digit):
        return self.mod13[digit]
    def update(self, num, digit):
        for k, v in self.mod13[digit-1].items():
            remain = ((num * 10**digit) + k) % 13
            self.mod13[digit][remain] = (self.mod13[digit][remain] + v) % Mod13DPTable.MOD
            
def main():
    MOD = 10**9 + 7
    S = input()
    mod13dp = Mod13DPTable(len(S))
    mod13dp.set_start(S[-1])
    for i, m in enumerate(reversed(list(S[:-1]))):
        i += 1
        if m == '?':
            for j in range(10):
                mod13dp.update(j, i)
        else:
            mod13dp.update(int(m), i)
    print(mod13dp.get_table(-1)[5])
main()

Submission status: Time Limit Exceeded

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

dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for k in range(10):
            for j in range(13):
                p=(k+10*j)%13
                dp[i+1][p]+=dp[i][j]
                dp[i+1][p]%=mod

    else:

        for j in range(13):
            p=(int(s[i])+10*j)%13
            dp[i+1][p]+=dp[i][j]
            dp[i+1][p]%=mod


print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

s = input()
n = 13

mod=10**9+7

dp=[0] * n
dp[0] =1

mul=1

for i in range(len(s)-1,-1,-1):

    nextDP = [0] * n

    c=s[i]

    if c =='?':
        for k in range(10):
            for j in range(n):
                nextDP[(k*mul+j)%n] += dp[j]

    else:
        k=int(s[i])
        for j in range(n):
            nextDP[(k*mul+j)%n] += dp[j]

    mul*=10
    dp=nextDP

print(dp[5]%mod%mod)

Submission status: Time Limit Exceeded

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

    else:
        for j in range(13):
            p=(s[i]+10*j)%13
            dp[i+1][p]+=dp[i][j]
            dp[i+1][p]%=mod
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * 10 ** i % mod
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * 10 ** i % mod
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
            tmp[(k + d) % mod] %= p
    dic = tmp
print(dic[5] % p)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    s.reverse()
    n = len(s)

    p10 = [0] * n
    p10[0] = 1
    for i in range(1, n):
        p10[i] = 10 * p10[i - 1]

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

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

    print(dp[5] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    s.reverse()
    n = len(s)

    p10 = [0] * n
    p10[0] = 1
    for i in range(1, n):
        p10[i] = 10 * p10[i - 1]

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

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

    print(dp[5] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    s.reverse()
    n = len(s)

    p10 = [0] * n
    p10[0] = 1
    for i in range(1, n):
        p10[i] = 10 * p10[i - 1]

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

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

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

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

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

dp[0][0] = 1

for i in range(N):
  if S[i] == '?':
    c = -1
  else:
    c = int(S[i])

  for j in range(10):
    if c != -1 and c != j:
      continue
    for k in range(13):
      dp[i+1][(k*10+j)%13] += dp[i][k]
      
  for j in range(13):
    dp[i+1][j] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

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

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s=list(input())
n=len(s)
dp=np.zeros((n+1,13),np.int64)
mod=pow(10,9)+7
if s[-1]=='?':
  dp[1][:10]=1
else:
  dp[1][int(s[-1])]=1
for i in range(2,n+1):
  if s[-i]=='?':
    for j in range(10):
      a=(j*pow(10,i-1,13))%13
      if a==0:
        dp[i]+=dp[i-1]
      else:
        dp[i][a:]+=dp[i-1][:-a]
        dp[i][:a]+=dp[i-1][-a:]
  else:
    j=int(s[-i])
    a=(j*pow(10,i-1,13))%13
    if a==0:
      dp[i]+=dp[i-1]
    else:
      dp[i][a:]+=dp[i-1][:-a]
      dp[i][:a]+=dp[i-1][-a:]
  dp[i]%=mod
print(dp[n][5])
#print(dp)