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 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 * r ) % 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()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13



    for j in range(10):

        for k in range(13):

            if s[i]== "?" or j == int(s[i]):
                nlis[ (k + (j * keta)) % 13] += lis[k]

    keta *= 10
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    mod = 10 ** 9 + 7
    s = list(input())
    n = len(s)
    s.reverse()

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

    mul = 1
    for i, c in enumerate(s):
        for j in range(10):
            if (c.isdigit() and int(c) == j) or c == '?':
                m = (j * mul) % 13
                for k in range(13):
                    dp[i + 1][(m + k) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] = dp[i + 1][k] % mod
        mul *= 10
    print(dp[n][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

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

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
MOD = 10**9+7
dp = [0,]*13
dp[0] = 1
for i, s in enumerate(S):
    nx = [0,]*13
    p = (10**i)%13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
'''
各桁ごとの*10**桁の13の余りの合計を考える
?000(mod13)=1000(mod13)*?(mod13)と考えられる
（前から）後ろの桁からDPをして?にぶつかるたびにたす
1?2?3を例とすると
0->3->?3->2?3->?2?3->1?2?3でDP
'''

S = input()
N = len(S)
mod = 13
dp = [0 for i in range(13)]
dp[0] = 1

for i in range(N):
        #print(S[-i-1])
        dpi = [0 for j in range(13)]
        if S[-i-1] == "?":
                m = 10 ** i
                for k in range(10):
                        p = (k*m)%13
                        for l in range(13):
                             dpi[(p+l)%13]+=dp[l]

        else:
                k = int(S[-i-1])
                m = 10 ** i
                p = (k*m)%13
                for l in range(13):
                        dpi[(p+l)%13]+=dp[l]

        dp = dpi
        #print(dp)

ans = int(dp[5])
ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b
d=[0 for _ in range(13)]
p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1
    c=rev[num+1:]
    for i,v in enumerate(c):
        #print(i+num+1)
        if v=="?":
            tmp=10**(i+num+1)%13
            t_d=[0 for _ in range(13)]
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d)
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
    print(d[cal]%mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    r_0 = int(s[-1]) % 13
    dp[0][r_0] += 1
else:
    for k in range(10):
        r_0 = k % 13
        dp[0][r_0] += 1

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys

s= sys.stdin.readline().strip()
#
MOD=10**9+7
#
base = 1
dp= [ 0 for i in range(13) ]
dp[0] = 1
tmp= [ 0 for i in range(13) ]
for i,c in enumerate(reversed(s)):
    tmp  = dp.copy()
    #
    if c=="?":
        for b in [ base*i for i in range(1,10) ]:
            for m,num in enumerate(tmp):
                if num==0: continue
                idx= (m+b)%13
                dp[idx]= dp[idx]+num
        #
        for i in range(13): dp[i] %= MOD
    else:
        b= base*int(c)
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    base = base*10
#
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

# 下からi桁(1-indexed)まで使ったときの、13で割ったときあまりがjになるパターン
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    r_now = [1, 10, 9, 12, 3, 4][i%6]
    if s == "?":
        for d in range(10):
            for r_before, count in enumerate(dp[i]):
                j = (r_now*d+r_before)%13
                dp[i+1][j] = (dp[i+1][j]+count)%(10**9+7)
    else:
        d = int(s)
        for r_before, count in enumerate(dp[i]):
            j = (r_now*d+r_before)%13
            dp[i+1][j] = (dp[i+1][j]+count)%(10**9+7)
    # for dp_i in dp:
    #     print(dp_i)
    # print("")

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

# 下からi桁(1-indexed)まで使ったときの、13で割ったときあまりがjになるパターン
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    r_now = [1, 10, 9, 12, 3, 4][i%6]
    if s == "?":
        for d in range(10):
            for r_before, count in enumerate(dp[i]):
                j = (r_now*d+r_before)%13
                dp[i+1][j] = (dp[i+1][j]+count)%(10**9+7)
    else:
        d = int(s)
        for r_before, count in enumerate(dp[i]):
            j = (r_now*d+r_before)%13
            dp[i+1][j] += (dp[i+1][j]+count)%(10**9+7)
    # for dp_i in dp:
    #     print(dp_i)
    # print("")

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for j in range(10):
      for i in range(13):
        a[(i*10+j)%13] += p[i]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  for i in range(13):
    p[i] = a[i]%1000000007
print(p[5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
# S="".join(["1" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (t,(j*tt+i)%13)
                dp[k] = (dp[k]+dp[(t-1,i)])%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (t,(s*tt+i)%13)
            dp[k] = (dp[(t-1,i)] + dp[k])%MOD

print(dp[(t,5)])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    r_0 = int(s[-1]) % 13
    dp[0][r_0] += 1
else:
    for k in range(10):
        r_0 = k % 13
        dp[0][r_0] += 1

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

# 下からi桁(1-indexed)まで使ったときの、13で割ったときあまりがjになるパターン
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1]):
    r_now = [1, 10, 9, 12, 3, 4][i%6]
    if s == "?":
        for d in range(10):
            for r_before, count in enumerate(dp[i]):
                j = (r_now*d+r_before)%13
                dp[i+1][j] += count 
    else:
        d = int(s)
        for r_before, count in enumerate(dp[i]):
            j = (r_now*d+r_before)%13
            dp[i+1][j] += count
    # for dp_i in dp:
    #     print(dp_i)
    # print("")

print(dp[len(S)][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
               DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
mod = 10**9+7

dp = np.zeros((len(s)+1, 13))
dp[0][0] = 1

for i in range(len(s)):
  c = -1 if s[i] == '?' else 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(int(dp[len(s)][5]))

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
M = 13
DP = [0] * M
DP[0] = 1

mul = 1
for i in range(len(S) - 1, -1, -1):
    s = S[i]
    newDP = [0] * M
    if s == '?':
        for k in range(10):
            for j in range(M):
                newDP[(mul * k + j) % M] += DP[j]
    else:
        k = int(s)
        for j in range(M):
            newDP[(mul * k + j) % M] += DP[j]
    DP = [x % MOD for x in newDP]
    mul *= 10

print(DP[5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
# S="".join(["1" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (t,(j*tt+i)%13)
                dp[k] += dp[(t-1,i)]
                dp[k] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (t,(s*tt+i)%13)
            dp[k] += dp[(t-1,i)]
            dp[k] %= MOD

print(dp[(t,5)])

Submission status: Time Limit Exceeded

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    # 5-1292 で一周
    mod = 10 ** 9 + 7
    s = list(input())
    n = len(s)
    s.reverse()

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

    for i, c in enumerate(s):
        for j in range(10):
            if (c.isdigit() and int(c) == j) or c == '?':
                m = (j * 10 ** i) % 13
                for k in range(13):
                    dp[i + 1][(m + k) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] = dp[i + 1][k] % mod

    print(dp[n][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import sys


# fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = input()[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = 10 ** (i - 1) % 13
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

dp[0][0] = 1
for i in range(N):
    for j in range(13):
        if S[i] != "?":
            dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
        else:
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:

S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13

    if s[i] == "?":

        for j in range(10):

            for k in range(13):

                nlis[ (k + (j * keta)) % 13] += lis[k]

    else:

        now = int(s[i])

        for k in range(13):

            nlis[ (k + (now * keta)) % 13 ] += lis[k]
            

    #print (nlis)
    keta *= 10
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
s = input()
p = [0]*13
p[0] = 1

for si in range(len(s)):
  a = [0]*13
  if s[si] == '?':
    for j in range(10):
      for i in range(13):
        a[(i*10+j)%13] += p[i]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  for i in range(13):
    p[i] = a[i]%1000000007
print(p[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    DP[1], DP[0] = DP[0], DP[1]
    for j in range(13):
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
               DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)

Submission status: Time Limit Exceeded

Solution code:
S=input()
# S="".join(["1" for _ in range(10**4)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    tt = 10**t
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (t,(j*tt+i)%13)
                dp[k] += dp[(t-1,i)]
                dp[k] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (t,(s*tt+i)%13)
            dp[k] += dp[(t-1,i)]
            dp[k] %= MOD

print(dp[(t,5)])

Submission status: Time Limit Exceeded

Solution code:
# S=input()
S="".join(["1" for _ in range(10**4)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    tt = 10**t
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (t,(j*tt+i)%13)
                dp[k] += dp[(t-1,i)]
                dp[k] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (t,(s*tt+i)%13)
            dp[k] += dp[(t-1,i)]
            dp[k] %= MOD

print(dp[(t,5)])

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:

S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13

    if s[i] == "?":

        for j in range(10):

            for k in range(13):

                nlis[ (k + (j * keta)) % 13] += lis[k]

    else:

        now = int(s[i])

        for k in range(13):

            nlis[ (k + (now * keta)) % 13 ] += lis[k]

    #print (nlis)
    keta *= 10
    for j in range(13):
        lis[j] = nlis[j]

#print (lis)
print (lis[5] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
S=input()
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                dp[(t,(j*10**t+i)%13)] += dp[(t-1,i)]
                dp[(t,(j*10**t+i)%13)] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            dp[(t,(s*10**t+i)%13)] += dp[(t-1,i)]
            dp[(t,(s*10**t+i)%13)] %= MOD


print(dp[(t,5)])

Submission status: Time Limit Exceeded

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

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

print(dp[N][5] % MOD)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
dp = np.zeros((100005, 13))
N = len(S)

dp[0][0] = 1
for i in range(N):
    c = -1
    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 = int(dp[N][5])

print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()
g = 10 ** 9 + 7
x = 1
DP = [None for _ in range(2)]
DP[0] = [0] * 13
DP[0][0] = 1
for i in range(len(S)):
    DP[1] = DP[0].copy()
    DP[0] = [0] * 13
    for j in range(13):
        if S[i] == "?":
                for k in range(10):
                    DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for j in range(13)]for i in range(10**5+1)]
dp[0][0] = 1
for i in range(len(S)):
    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] %= 10**9+7
    
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
MOD = 10**9+7
dp = [0,]*13
next_dp = [0,]*13
dp[0] = 1
for i, s in enumerate(reversed(S)):
    for j, d in enumerate(dp):
        if s == '?':
            for k in range(10):
                next_dp[(j+k*(10**i))%13] += d
        else:
            next_dp[(j+int(s)*(10**i))%13] += d
    for j, d in enumerate(next_dp):
        next_dp[j] = d % MOD
    dp = next_dp
    next_dp = [0,]*13
print(dp[5])

Submission status: Time Limit Exceeded

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

mul = 1
for i in range(len(S)):
  c = S[len(S) - i - 1]
  nextDP = [0 for _ in range(N)]

  if c == "?":
    for k in range(10):
      for j in range(N):
        nextDP[(k * mul + j) % N] += dp[j]
        nextDP[(k * mul + j) % N] %= MOD
  else:
    k = int(c)
    for j in range(N):
      nextDP[(k * mul + j) % N] += dp[j]
      nextDP[(k * mul + j) % N] %= MOD

  mul *= 10
  mul %= N
  dp = nextDP
print(dp[5])

Submission status: Time Limit Exceeded

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

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b

p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
d={i:0 for i in range(13)}
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1

    for i,v in enumerate(rev[num+1:]):
        #print(i+num+1)
        if v=="?":
            tmp=10**(i+num+1)%13
            t_d={i:0 for i in range(13)}
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d.values())
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
    #print(d)
    print(d[cal]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7
 
debug = True
debug = False
 
def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [0 for j in range(13)]
    dp2 = [0 for j in range(13)]
 
    for i, c in enumerate(S):
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[j] = 1
            else:
                dp[int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp2[k] = (dp2[k] + dp[(k-amari)%13]) % MOD
            else:
                for k in range(13):
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp2[k] = (dp2[k] + dp[(k-amari) % 13]) % MOD
 
            dp = dp2
            dp2 = [0 for j in range(13)]
 
    dprint(dp)
    print(dp[5])
solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys

s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ (b*i)%13 for i in range(10) ] )
#
dp= [ 0 for i in range(13) ]
dp[0] = 1
for i,c in enumerate(reversed(s)):
    tmp  = dp.copy()
    #
    if c=="?":
        bset = mmap[i%6][1:]
        for m in range(13):
            num= tmp[m]
            if num==0: continue
            for b in bset:
                idx= (m+b)%13
                dp[idx]= ( dp[idx] + num ) % MOD
    else:
        b= mmap[i%6][int(c)]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
#
print(dp[5])

Submission status: Time Limit Exceeded

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

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b

p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
d={i:0 for i in range(13)}
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1

    for i,v in enumerate(rev[num+1:]):
        #print(i+num+1)
        if v=="?":
            tmp=10**(i+num+1)%13
            t_d={i:0 for i in range(13)}
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d.values())
            for j in range(13):
                d[j]=t_d[j]
            #print(t_d)
    #print(d)
    print(d[cal]%mod)

Submission status: Time Limit Exceeded

Solution code:
s =str(input())
t = [[]for i in range(6)]
for i in range(6):
    for j in range(10):
        t[i].append((j*(10**i))%13)

t1 = []
for j in range((len(s))):
    t1 += [[0 for i in range(13)]]

p = (len(s) - 1) % 6
if s[0] == "?":
        for  i in range(10):
                t1[0][t[p][i]] = 1
else:
        t1[0][t[p][int(s[0])]] = 1

for i in range(len(s)-1):
        p = (p - 1) % 6
        if s[i+1] == "?":
                for j in range(13):
                        for k in range(10):
                                t1[i+1][(j+t[p][k])%13] += t1[i][j]
        else:
                for j in range(13):
                        t1[i+1][(j+t[p][int(s[i+1])])%13] += t1[i][j]

print((t1[-1][5])%(10 ** 9 + 7))

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
    tdp=[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]
        else:
            if i%6==0:ll=  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
            elif i%6==1:ll=[0, 1, 2, 4, 5, 7, 8, 10, 11, 12]
            elif i%6==2:ll=[0, 1, 2, 3, 5, 6, 7, 9, 10, 11]
            elif i%6==3:ll=[0, 4, 5, 6, 7, 8, 9, 10, 11, 12]
            elif i%6==4:ll=[0, 1, 2, 3, 5, 6, 8, 9, 11, 12]
            elif i%6==5:ll=[0, 2, 3, 4, 6, 7, 8, 10, 11, 12]
            for j in range(13):tdp[j]=sum(dp[(j-k)%13] for k in ll)
            for j in range(13):dp[j]=tdp[j]%(10**9+7)
    print(dp[5])
sol()

Submission status: Time Limit Exceeded

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

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

for s in S:
  prev = [x % MOD for x in dp]
  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]
  
print(dp[5] % MOD)