Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

??2??5

Sample Output 1

768

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

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

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


MOD = 1000000007  # type: int
# def cmb(n, r):
#     return (factorial(n) // (factorial(r) * factorial(n - r))%MOD)

def solve(S: str):
    S = S[::-1]
    dp = [[0] * 13 for _ in range(len(S))]
    # dp[LENGTH][MOD]

    s = S[0]
    if s == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s)] = 1
    for l in range(1, len(S)):
        s = S[l]
        pow_l = pow(10, l, 13)
        if s == "?":
            for m in range(13):
                for i in range(10):
                    dp[l][(m + pow_l * i) % 13] += dp[l-1][m]% MOD
        else:
            i = int(s)
            for m in range(13):
                dp[l][(m + pow_l * i) % 13] += dp[l-1][m] % MOD

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

    return


# Generated by 1.1.6 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:
#!/usr/bin/env python3
import sys
from math import factorial


MOD = 1000000007  # type: int
def cmb(n, r):
    return (factorial(n) // (factorial(r) * factorial(n - r))%MOD)

def solve(S: str):
    S = S[::-1]
    dp = [[0] * 13 for _ in range(len(S))]
    s = S[0]
    if s == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s)] = 1
    # dp[LENGTH][MOD]
    for l in range(1, len(S)):
        s = S[l]
        if s == "?":
            for m in range(13):
                for i in range(10):
                    dp[l][(m + pow(10, l, 13) * i) % 13] += dp[l-1][m]% MOD
        else:
            i = int(s)
            for m in range(13):
                dp[l][(m + pow(10, l, 13) * i) % 13] += dp[l-1][m] % MOD

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

    return


# Generated by 1.1.6 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 sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
n = len(s)

class ModInt:
    def __init__(self, n=0, mod=mod):
        self.mod = mod
        self.n = n % self.mod
    
    def value(self):
        return self.n
    
    def __add__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n + rhs.n, self.mod)
        return self.__class__(self.n + rhs, self.mod)
    
    __radd__ = __add__
    
    def __sub__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n - rhs.n, self.mod)
        return self.__class__(self.n - rhs, self.mod)
    
    def __rsub__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n - self.n, self.mod)
        return self.__class__(lhs - self.n, self.mod)

    def __mul__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n * rhs.n, self.mod)
        return self.__class__(self.n * rhs, self.mod)
    
    __rmul__ = __mul__

    def __floordiv__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n // rhs.n, self.mod)
        return self.__class__(self.n // rhs, self.mod)
    
    def __rfloordiv__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n // self.n, self.mod)
        return self.__class__(lhs // self.n, self.mod)

    def __iadd__(self, rhs):
        if isinstance(rhs, ModInt):
            self.n += rhs.n
        else:
            self.n += rhs
        if self.n >= self.mod:
            self.n -= self.mod
        
        return self
    
    def __isub__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        if self.n < rhs_n:
            self.n += self.mod
        self.n -= rhs_n
        return self
    
    def __imul__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        self.n = self.n * rhs_n % self.mod
        return self
    
    def __ifloordiv__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        exp = self.mod - 2
        while exp:
            if exp % 2:
                self *= rhs_n
            
            rhs_n *= rhs_n
            rhs_n %= self.mod
            exp //= 2
        
        return self
    
    def __pow__(self, exp):
        exp_n = exp.n if isinstance(exp, ModInt) else exp
        if exp_n == 0:
            return self.__class__(1, self.mod)
        if exp_n % 2 == 0:
            t = self.__pow__(exp_n // 2)
            return t * t
        return self * self.__pow__(exp_n - 1)
    
    def __str__(self):
        return str(self.n)

dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if s[i] != '?':
            dig = int(s[i])
            t = ModInt(10, mod=13)
            t = t ** (n - i - 1)
            t *= dig
            t += j
            ni = i + 1
            nj = t.value()
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
        else:
            for k in range(10):
                dig = k
                t = ModInt(10, mod=13)
                t = t ** (n - i - 1)
                t *= dig
                t += j
                ni = i + 1
                nj = t.value()
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

    Ss = input()

    N = len(Ss)

    dp = [0] * 13
    dp[0] = 1
    for d, Sd in enumerate(Ss):
        dp2 = [0] * 13
        for mod13 in range(13):
            if Sd != '?':
                x = int(Sd)
                mod13n = (10*mod13 + x) % 13
                dp2[mod13n] += dp[mod13]
                dp2[mod13n] %= MOD
            else:
                for x in range(10):
                    mod13n = (10*mod13 + x) % 13
                    dp2[mod13n] += dp[mod13]
                    dp2[mod13n] %= MOD
        dp = dp2

    print(dp[5])


solve()

Submission status: Time Limit Exceeded

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

if S[0] == "?":
    for i in range(10):
        dp[i][0] = 1
else:
    dp[int(S[0])][0] = 1
        
for i in range(1, N):
    if S[i] == "?":
        for s in range(10):
            for x in range(13):
                dp[(x*10 + s)%13][i] += dp[x][i-1]
    else:
        for x in range(13):
            dp[(x*10 + int(S[i]))%13][i] += dp[x][i-1] 
    for t in range(13):
        dp[t][i] = dp[t][i]%mod
print(dp[5][N-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
pow_10_i_13 = [pow(10, i, 13) for i in range(6)]

s = input()

dp = [0] * 13
dp[0] = 1
for i, c in enumerate(reversed(s)):
    if c == '?':
        tmp = [0] * 13
        for j in range(10):
            shift = j * pow_10_i_13[i % 6] % 13
            for k in range(13):
                tmp[k] += dp[k-shift]
                tmp[k] %= MOD
        dp = tmp
    else:
        shift = int(c) * pow_10_i_13[i % 6] % 13
        dp = dp[-shift:] + dp[:-shift]

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
                dp[i + 1][(10 * k + j) % 13] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    if S[-1] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(S[-1])] = 1

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

    print(dp[-1][5])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    S = input()
    MOD = 10 ** 9 + 7
    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][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x)
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul = mul * 10 % 13
    print(dp[len(S)][5])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
work_lists = [[0] * 13 for i in range(6)]
for i in range(6):
    for x in range(10):
        work_lists[i][(x * (10 ** i)) % 13] = 1
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = work_lists[i % 6]
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) % K for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** (i % 6))) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = next_li
print(li[5])

Submission status: Time Limit Exceeded

Solution code:
K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = [0] * 13
        next_li = [0] * 13
        for x in range(10):
            work_li[x * (10 ** i) % 13] = 1
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** i)) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = [j % K for j in next_li]
print(li[5])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
num = len(s)
dp = [[0] * 13 for i in range(num+1)]
dp[0][0] = 1
mod = 13
ansmod = 10 ** 9 + 7

for i in range(num):
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(k * 10 +j)%mod] += dp[i][k]
    else:
        for k in range(13):
            dp[i+1][(k * 10 + (int(s[i])))%mod] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= ansmod
  #    print(dp)
print(dp[num][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l+1)]
dp[0][0] = 1
p = 1
for i in range(l):
  if(S[i] != '?'):
    n = int(S[i])
    for j in range(13):
      dp[i+1][(j*10+n)%13] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] += dp[i][j]
  for j in range(13):
    dp[i+1][j] = dp[i+1][j]%MOD
  p = (p*10)%MOD    
print(dp[l][5])

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
s=input()
r=range
dp=[[0]*13,[0]*13]
dp[0][0]=1
t=0
for c in s:
  for i in r(13):
    if c=='?':
      for j in r(10):
        dp[t^1][(i*10+j)%13]+=dp[t][i]
    else:
      dp[t^1][(i*10+int(c))%13]+=dp[t][i]
  dp[t]=[0]*13
  t^=1
  for i in r(13): dp[t][i]%=M
print(dp[len(s)%2][5])

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
keta=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        if dp[i][mod]==0:
            continue

        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*keta + mod) % 13
            dp[i+1][nmod] += dp[i][mod]
    keta*=10
    keta%=13

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

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        if dp[i][mod]==0:
            continue

        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*(pow(10,i,13)) + mod) % 13
            dp[i+1][nmod] += dp[i][mod]

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

Submission status: Time Limit Exceeded

Solution code:
s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*(pow(10,i,13)) + mod) % 13
            dp[i+1][nmod] += dp[i][mod]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = str(input())

mod = 10**9+7

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

nextdps = np.zeros((10,13))

m = 1
p = 1
for c in s[::-1]:
  predp = dp[p-1]
  if c == '?':
    for i in range(0, 10):
      idx = 13 - i*m%13
      nextdps[i][:13-idx] = predp[idx:]
      nextdps[i][13-idx:] = predp[:idx]
    dp[p] = nextdps.sum(axis=0)
  else:
    i = int(c)
    idx = 13 - i*m%13
    dp[p][:13-idx] = predp[idx:]
    dp[p][13-idx:] = predp[:idx]
  dp[p] %= mod
  m *= 10
  m %= 13
  p+=1
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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



if __name__ == "__main__":
    main()

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

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = str(input())

mod = 10**9+7

dp = np.zeros(13)
dp[0] = 1

nextdps = np.zeros((10,13))

m = 1
for c in s[::-1]:
  predp = dp.copy()
  if c == '?':
    for i in range(0, 10):
      idx = 13 - i*m%13
      nextdps[i][:13-idx] = predp[idx:]
      nextdps[i][13-idx:] = predp[:idx]
    dp = nextdps.sum(axis=0)
  else:
    i = int(c)
    idx = 13 - i*m%13
    dp[:13-idx] = predp[idx:]
    dp[13-idx:] = predp[:idx]
  dp %= mod
  m *= 10
  m %= 13
print(int(dp[5]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = str(input())

mod = 10**9+7

dp = np.zeros(13)
dp[0] = 1

m = 1
for c in s[::-1]:
  if c == '?':
    nextdps = []
    for i in range(10):
      idx = 13 - i*m%13
      nextdps.append(dp[idx:].tolist() + dp[:idx].tolist())
    dp = np.sum(nextdps, axis=0)
  else:
    i = int(c)
    idx = 13 - i*m%13
    dp = dp[idx:].tolist() + dp[:idx].tolist()
    dp = np.array(dp)
  dp %= mod
  m *= 10
  m %= 13
print(int(dp[5]))

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

mod = 10**9+7

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

idx_mat = []
for i in range(10):
  i_list = []
  for j in range(13):
    j_list = []
    for m in range(13):
      j_list.append((i*m + j)%13)
    i_list.append(j_list)
  idx_mat.append(i_list)

m = 1
for c in s[::-1]:
  nextdp = [0]*13
  if c == '?':
    for i in range(10):
      for j in range(13):
        nextdp[idx_mat[i][j][m]] += dp[j]
        nextdp[idx_mat[i][j][m]] %= mod
  else:
    i = int(c)
    for j in range(13):
      nextdp[idx_mat[i][j][m]] += dp[j]
      nextdp[idx_mat[i][j][m]] %= mod
  dp = nextdp.copy()
  m *= 10
  m %= 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())

mod = 10**9+7

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

m = 1
for c in s[::-1]:
  nextdp = [0]*13
  if c == '?':
    for i in range(10):
      for j in range(13):
        nextdp[(i*m + j)%13] += dp[j]
        nextdp[(i*m + j)%13] %= mod
  else:
    i = int(c)
    for j in range(13):
      nextdp[(i*m + j)%13] += dp[j]
      nextdp[(i*m + j)%13] %= mod
  dp = nextdp.copy()
  m *= 10
  m %= 13
print(dp[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]=dp[i+1][(10*k+j)%13]+dp[i][k]
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]=dp[i+1][(10*k+a)%13]+dp[i][k]
print(dp[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
MOD=10**9+7
dp=[0]*13
dp[0]=1
for i in range(1,len(S)+1):
    ans=[0]*13
    if S[-i]=="?":
        for j in range(10):
            a=(j*10**(i-1))%13
            for k in range(13):
                ans[(k+a)%13]=ans[(k+a)%13]+dp[k]
    else:
        a=int(S[-i])
        a=(a*10**(i-1))%13
        for k in range(13):
            ans[(k+a)%13]=ans[(k+a)%13]+dp[k]
    dp=ans.copy()
print(ans[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
flag=0
ans=0
for i in range(1,len(S)+1):
    if S[-i]=="?":
        for j in range(10):
            a=(j*10**(i-1))%13
            for k in range(13):
                dp[i][(k+a)%13]=dp[i][(k+a)%13]+dp[i-1][k]
    else:
        a=int(S[-i])
        a=(a*10**(i-1))%13
        for k in range(13):
            dp[i][(k+a)%13]=dp[i][(k+a)%13]+dp[i-1][k]
print(dp[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
flag=0
ans=0
for i in range(1,len(S)+1):
    if S[-i]=="?":
        for j in range(10):
            a=(j*10**(i-1))%13
            for k in range(13):
                dp[i][(k+a)%13]+=dp[i-1][k]
    else:
        a=int(S[-i])
        a=(a*10**(i-1))%13
        for k in range(13):
            dp[i][(k+a)%13]+=dp[i-1][k]
print(dp[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
amari = np.array([[i] for i in range(10)])
p = 10**9 + 7
s =  str(input())
n = len(s)
ans = np.zeros(13, dtype = np.int64)
ans[0] = 1
for i in reversed(s):
  dp = np.zeros(13, dtype = np.int64)
  if i == '?':
    for j in range(13):
      dp[(j + amari)%13] += ans[j]
  else:
    for j in range(13):
      dp[(j + amari[int(i)])%13] += ans[j]
  dp %= p
  ans = dp
  amari = amari*10 %13
print(ans[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
amari = np.array([[i] for i in range(10)])
p = 10**9 + 7
s =  str(input())
n = len(s)
dp = np.zeros((n+1, 13))
dp[0, 0] = 1
for i in range(n):
  if s[n-1-i] == '?':
    for j in range(13):
      dp[i+1][(j + amari)%13] += dp[i][j]
  else:
    for j in range(13):
      dp[i+1][(j + amari[int(s[n-1-i])])%13] += dp[i][j]
  dp[i + 1, :] %= p
  amari = amari*10 %13
print(int(dp[n, 5]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
MOD = 10**9 + 7
S = sys.stdin.readline().rstrip()
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1

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

print (dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1

def add_dp(i,j):
    for k in range(13):
        l = (k * 10 + j) % 13
        dp[i][l] += dp[i-1][k]

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

print (dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
  s=input()
  l=len(s)
  mod = 10**9+7
  dp=[[0]*13 for _ in range(l+1)]
  dp[0][0]=1 #初期値設定
  for i in range(l):
    if s[i]!="?":
      for k in range(13):
        dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
    else:
      for j in range(10):
        for k in range(13):
          dp[i+1][(k*10+j)%13]+=dp[i][k]%mod

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
  if s[i]=='?': #?のときは各値(0～9)について更新する
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13): #整数のときはその値について更新する
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod) #最後まで更新を行ったときのあまりが5となる数の個数が答え

Submission status: Time Limit Exceeded

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

dp[0][0]=1 #初期値設定
for i in range(l):
  if s[i]!="?":
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
  else:
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]
        
print(dp[-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:


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

dp[0][0]=1 #初期値設定
for i in range(l):
  if s[i]!="?":
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
  else:
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]
        
print(dp[-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7
S=S[::-1]

dp=defaultdict(lambda: 0)

for i,x in enumerate(S):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[(i,(x*pow(10,i,13))%13)]=1
        else:
            for x in range(10):
                dp[(i,(x*pow(10,i,13))%13)]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                n=(x*pow(10,i,13)+j)%13
                dp[(i,n)]+=dp[(i-1,j)]
                dp[(i,n)]%=mod
        else:
            for j in range(13):
                for x in range(10):
                    n=(x*pow(10,i,13)+j)%13
                    dp[(i,n)]+=dp[(i-1,j)]%mod
                    dp[(i,n)]%=mod
print dp[(N-1,5)]%mod

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7
S=S[::-1]

dp=defaultdict(lambda: 0)

for i,x in enumerate(S):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[(i,(x*pow(10,i,13))%13)]=1
        else:
            for x in range(10):
                dp[(i,(x*pow(10,i,13))%13)]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                n=(x*pow(10,i,13)+j)%13
                dp[(i,n)]+=dp[(i-1,j)]
                dp[(i,n)]%=mod
        else:
            for j in range(13):
                for x in range(10):
                    n=(x*pow(10,i,13)+j)%13
                    dp[(i,n)]+=dp[(i-1,j)]
                    dp[(i,n)]%=mod
print dp[(N-1,5)]%mod

Submission status: Time Limit Exceeded

Solution code:
S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
s=t.copy()
t[0]=1
jkmap=[]
for j in range(10):
  jkmap.append([])
  for k in range(13):
    jkmap[j].append((10*k+j)%13)
for i in range(n):
  if S[i]=='?':
    tcopy=s.copy()
    for j in range(10):
      for k in range(13):
        tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    t=tcopy.copy()
  else:
    j=int(S[i])
    tcopy=s.copy()
    for k in range(13):
      tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    t=tcopy.copy()
print(t[5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
s=t.copy()
t[0]=1
for i in range(n):
  if S[i]=='?':
    tcopy=s.copy()
    for j in range(10):
      for k in range(13):
        tcopy[(10*k+j)%13]=(tcopy[(10*k+j)%13]+t[k])%(10**9+7)
    t=tcopy.copy()
  else:
    j=int(S[i])
    tcopy=s.copy()
    for k in range(13):
      tcopy[(10*k+j)%13]=(tcopy[(10*k+j)%13]+t[k])%(10**9+7)
    t=tcopy.copy()
print(t[5])