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:
def main():
    S = input()

    mod = 10**9+7
    N = len(S)
    ans = 0

    memo = {}
    for i in range(1000):
        s = str(i).zfill(3)
        memo[s] = [0 for _ in [0]*13]
        memo[s][i%13] = 1

    def rep_Q_count(s):
        memo[s] = [0 for _ in [0]*13]
        for q in range(10):
            s2 = s.replace("?",str(q),1)
            for i,n in enumerate(memo[s2]):
                memo[s][i] += n

    for i in range(100):
        s = str(i).zfill(2)
        rep_Q_count(s+"?")
        rep_Q_count(s[0]+"?"+s[1])
        rep_Q_count("?"+s)
    for i in range(10):
        s = str(i)
        rep_Q_count(s+"??")
        rep_Q_count("?"+s+"?")
        rep_Q_count("??"+s)
    rep_Q_count("???")

    s0 = S[max(0,N-3):N].zfill(3)
    dp = memo[s0][:]
    for i in range(1,(N-1)//3+1):
        s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
        j = i%2
        tmp = memo[s]
        dp2 = [0]*13
        for k,n in enumerate(tmp):
            for l,m in enumerate(dp):
                dp2[(l+k*((-1)**j))%13] += n*m
        dp = dp2
        for i in range(13):
            dp[i] %= mod
    print(dp[5])
main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    mod = 10**9+7
    N = len(S)

    s = S[-1]
    dp = [0]*13
    if s=="?":
        dp[:10] = [1]*10
    else:
        dp[int(s)] = 1

    dig = 1
    for c,s in enumerate(S[:-1][::-1],1):
        dig = dig*10%13
        dp2 = [0]*13
        if s=="?":
            for i in range(10):
                for j,n in enumerate(dp):
                    dp2[(i*dig+j)%13] += n
        else:
            i = int(s)
            for j,n in enumerate(dp):
                dp2[(i*dig+j)%13] += n
        dp = [n%mod for n in dp2]
    print(dp[5])
main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
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)):
  c = -1
  if S[i] != '?':
    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

res = dp[len(S)][5]

print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10**9+7
N = len(S)

s = S[-1]
dp = [0]*13
if s=="?":
    dp[:10] = [1]*10
else:
    dp[int(s)] = 1

dig = 1
for c,s in enumerate(S[:-1][::-1],1):
    dig = dig*10%13
    dp2 = [0]*13
    if s=="?":
        for i in range(10):
            for j,n in enumerate(dp):
                dp2[(i*dig+j)%13] += n
    else:
        i = int(s)
        for j,n in enumerate(dp):
            dp2[(i*dig+j)%13] += n
    dp = [n%mod for n in dp2]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

num_mod = 10 ** 9 + 7
dp = [1] + [0]*12
for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
  for j in range(13):
    nextdp[j] %= num_mod
  dp = nextdp
  # print(dp)
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

num_mod = 10 ** 9 + 7
dp = [1] + [0]*12
for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
    for j in range(13):
      nextdp[j] %= num_mod
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
      nextdp[(j*10 + int(S[i]))%13] %= num_mod
  dp = nextdp
  # print(dp)
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10**9+7
N = len(S)

s = S[-1]
dp = [0]*13
if s=="?":
    dp[:10] = [1]*10
else:
    dp[int(s)] = 1

for c,s in enumerate(S[:-1][::-1],1):
    dp2 = [0]*13
    if s=="?":
        for i in range(10):
            for j,n in enumerate(dp):
                dp2[(i*(10**c)+j)%13] += n
    else:
        i = int(s)
        for j,n in enumerate(dp):
            dp2[(i*(10**c)+j)%13] += n
    dp = [n%mod for n in dp2]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

num_mod = 10 ** 9 + 7
dp = [1] + [0]*12
for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
        nextdp[(j*10 + k)%13] %= num_mod
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
      nextdp[(j*10 + int(S[i]))%13] %= num_mod
  dp = nextdp
  # print(dp)
print(dp[5])

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


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

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


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:
MOD = 10**9 + 7

s = input()
n = len(s)

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

dp[0][0] = 1
for i in range(n):
    c = s[i] 
    for dk in range(130): # digit_kisu, digit = dk % 10, kisu = dk // 10
        if not (c == -1 or c == dk % 10): continue
        dp[i+1][dk % 13] += dp[i][dk // 10]

    for kisu in range(13):
        dp[i+1][kisu] %= MOD

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

s = input()
n = len(s)

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

dp[0][0] = 1
for i in range(n):
    c = s[i] 
    for dk in range(130): # digit_kisu, digit = dk % 10, kisu = dk // 10
        if not (c == -1 or c == dk % 10): continue
        dp[i+1][dk % 13] += dp[i][dk // 10] % MOD

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

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):
    c = -1 if s[i] == '?' else int(s[i])
    for dk in range(130): # digit_kisu, digit = dk % 10, kisu = dk // 10
        if not (c == -1 or c == dk % 10): continue
        dp[i+1][dk % 13] += dp[i][dk // 10] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    for i in range(1, len(S)):
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    return


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
import numpy as np

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = np.zeros((N, 13))
    if S[N-1] != '?':
        dp[0, int(S[N-1])] = 1
    else:
        dp[0] = np.array([1,1,1,1,1,1,1,1,1,1,0,0,0])
    for i in range(1, len(S)):
        ii = N - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    dp[i, j] += dp[i-1, (13 + j - kk) % 13]
                    dp[i, j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                dp[i, j] = dp[i-1, (13+j-m)%13]
                dp[i, j] %= MOD
    print(int(dp[N-1, 5]))
    return


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
import numpy as np

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = np.zeros((N, 13))
    if S[N-1] != '?':
        dp[0, int(S[N-1])] = 1
    else:
        dp[0] = np.array([1,1,1,1,1,1,1,1,1,1,0,0,0])
    for i in range(1, len(S)):
        ii = N - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = (ll * 10 ** i) % 13
                    if j >= kk:
                        dp[i, j] += dp[i-1, j - kk]
                    if j < kk:
                        dp[i, j] += dp[i-1, 13 + j - kk]
                    dp[i, j] %= MOD
            else:
                x = int(S[ii])
                m = x * 10 ** i % 13
                k = j
                if j < m:
                    k = j + 13
                dp[i, j] = dp[i-1, k-m]
                dp[i, j] %= MOD
    print(int(dp[N-1, 5]))
    return


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:
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):
    c = -1 if s[i] == '?' else int(s[i])
    for digit in range(10):
        if not (c == -1 or c == digit): continue
        for kisu in range(13):
            dp[i+1][(kisu * 10 + digit) % 13] += dp[i][kisu]
    for kisu in range(13):
        dp[i+1][kisu] %= MOD

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
modn=10**9+7
qnum=S.count('?')
lenS=len(S)

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

for i in range(lenS):
    for j in range(13):
        if S[i]=='?': 
            for k in range(10):
                dp[i+1][(j*10+k)%13]+=dp[i][j]
                dp[i+1][(j*10+k)%13]%=modn
        else:
            dp[i+1][(j*10+int(S[i]))%13]+=dp[i][j]
            dp[i+1][(j*10+int(S[i]))%13]%=modn

print(dp[lenS][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]
#print(dp[0])
for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  #print(dp[i+1])
  dp.append(dpn)
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for s in reversed(S):
        nextdp = [0] * 13
        if s == '?':
            for i in range(10):
                for j in range(13):
                    nextdp[(i * digit + j) % 13] += dp[j]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(i * digit + j) % 13] %= mod
        else:
            k = int(s)
            for j in range(13):
                nextdp[(k * digit + j) % 13] += dp[j]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(k * digit + j) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        n = (d*e)%13
        r += dp[i][(j+13-n)%13]
      dp[i+1][j] = r%1000000007
  else:
    d = int(c)
    n = (d*e)%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  #print(dp[i+1])
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for d in range(10):
      n = (d*e)%13
      for j in range(13):
        dp[i+1][j] = (dp[i+1][j]+dp[i][(j+13-n)%13])%1000000007
  else:
    d = int(c)
    n = (d*e)%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  #print(dp[i+1])
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for s in reversed(S):
        nextdp = [0] * 13
        if s == '?':
            for i in range(10):
                for j in range(13):
                    nextdp[(i * digit + j) % 13] += dp[j]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(i * digit + j) % 13] %= mod
        else:
            k = int(s)
            for j in range(13):
                nextdp[(k * digit + j) % 13] += dp[j]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(k * digit + j) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  if c == "?":
    for d in range(10):
      n = (d*(10**((len(S)-i-1)%12)))%13
      for j in range(13):
        dp[i+1][j] = (dp[i+1][j]+dp[i][(j+13-n)%13])%1000000007
  else:
    d = int(c)
    n = (d*(10**((len(S)-i-1)%12)))%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  #print(dp[i+1])
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  if c == "?":
    for d in range(10):
      n = (d*(10**(len(S)-i-1)))%13
      for j in range(13):
        dp[i+1][j] += dp[i][(j+13-n)%13]
  else:
    n = (int(c)*(10**(len(S)-i-1)))%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  for j in range(13):
    dp[i+1][j] = dp[i+1][j]%1000000007
  #print(dp[i+1])
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = 13
# dp[k] -> 13で割った余りがKのパターン数
dp = [0] * N
dp[0] = 1

# 後ろから解くアルゴリズム
# 1?2?3   0 -> 3 -> ?3 -> 2?3 -> ...
mod = 10**9 + 7

mul = 1
for i in range(len(S))[::-1]:
    # 次の状態
    nextDP = [0] * N
    if S[i] == '?':
        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(S[i])
        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:

def main():
    S = list(input())

    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    # 上からj桁目までの数を13で割ったあまりがiであるものの個数

    for i, sk in enumerate(S):
        if i == 0:
            if sk == '?':
                for j in range(10):
                    dp[0][j] = 1
            else:
                s = int(sk)
                dp[0][s] = 1
            continue
        if sk == '?':
            for j in range(13):
                for l in range(10): # 上からi桁目に入れる数字
                    k = (10*j+l)%13
                    dp[i][k] += dp[i-1][j]
        else:
            s = int(sk)
            for j in range(13):
                k = (10*j+s)%13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] = dp[i][j] % 1000000007

    print(dp[-1][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

dp = [[0 for _ in range(13)] for _ in range(len(S))]
# 上からj桁目までの数を13で割ったあまりがiであるものの個数

for i, sk in enumerate(S):
    if i == 0:
        if sk == '?':
            for j in range(10):
                dp[0][j] = 1
        else:
            s = int(sk)
            dp[0][s] = 1
        continue
    if sk == '?':
        for j in range(13):
            for l in range(10): # 上からi桁目に入れる数字
                k = (10*j+l)%13
                dp[i][k] += dp[i-1][j]
    else:
        s = int(sk)
        for j in range(13):
            for l in range(10):
                k = (10*j+l)%13
                if l % 10 == s:
                    dp[i][k] += dp[i-1][j]
    for j in range(13):
        dp[i][j] = dp[i][j] % 1000000007

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  #resource.setrlimit(RLIMIT_STACK, (128*1024*1024,hard))

rem = [1,10,9,12,3,4]
s = input().strip()
sr = s[::-1]
n = len(s)
dp = [ [0]*13 for i in range(n) ]
if sr[0]=='?':
    for j in range(10):
        dp[0][j] = 1
else:
    j = int(sr[0])
    dp[0][j] = 1

for i in range(1,n):
    r = rem[i%6]
    if sr[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R
    else:
        j = int(sr[i])
        for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R

print(dp[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def f(s):
    k = len(s)
    md = 10 ** 9 + 7
    dp = np.zeros((k + 1, 13), dtype="i8")
    dp[0][0] = 1
    for i, c in enumerate(s[::-1]):
        if c == "?":
            for n in range(10):
                m = n * 10 ** i % 13
                dp[i + 1][:m] = (dp[i + 1][:m] + dp[i][13 - m:]) % md
                dp[i + 1][m:] = (dp[i + 1][m:] + dp[i][:13 - m]) % md
        else:
            m = int(c) * 10 ** i % 13
            dp[i + 1][:m] = (dp[i + 1][:m] + dp[i][13 - m:]) % md
            dp[i + 1][m:] = (dp[i + 1][m:] + dp[i][:13 - m]) % md
    print(dp[k][5])

s = input()
f(s)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
n = len(s)
s = '#' + s
MOD = 10**9+7
dp = [[0]*13 for _ in range(n+5)]
"""
dp[i][j] は i 桁目まで見たとき 13 で割ったあまりが j　となるようなものの個数
"""
dp[0][0] = 1
r = 1 
for i in range(1,n+1):
    for j in range(13):
        if s[i] != '?':
            dp[i][j] = dp[i-1][(j-r*int(s[i]))%13] % MOD
        if s[i] == '?':
            for k in range(10):
                dp[i][j] += dp[i-1][(j-r*k)%13]
            dp[i][j] %= MOD
    r = (r*10) % 13
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    dp = np.convolve(dp, add_all[i%6])
    dp[:12] += dp[13:25]
    dp = dp[:13] % MOD
  else:
    constant_term += add_single[i%6][int(s)]

    
dp = np.roll(dp, constant_term)
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
def f(s):
    k = len(s)
    md = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(k + 1)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, c in enumerate(s[::-1]):
        dpi1 = dp[i + 1]
        if c == "?":
            for n in range(10):
                m = n * 10 ** i % 13
                for j in range(13):
                    dpi1[j] = (dpi1[j] + dpi[j - m]) % md
        else:
            m = int(c) * 10 ** i % 13
            for j in range(13):
                dpi1[j] = (dpi1[j] + dpi[j - m]) % md
        dpi = dpi1
    print(dp[k][5])

s = input()
f(s)

Submission status: Time Limit Exceeded

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

S = str(input())

N = 13

dp =[0]*N
dp[0]=1

mul = 1
for i in reversed(range(0,len(S))):
    nextDP = [0]*N
    if S[i] == '?':
        # print('test')
        # print(mul)
        for k in range(10):
            for j in range(N):
                nextDP[(mul*k+j)%N] += dp[j]
                nextDP[(mul*k+j)%N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(mul*k+j)%N] += dp[j]
            nextDP[(mul*k+j)%N] %= MOD

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])
  
add_single = [[x * (10 ** i) % 13 for x in range(10)] for i in range(6)]

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

for i,s in enumerate(S[::-1]):
  if s == '?':
    dp = np.convolve(dp, add_all[i%6])
    dp[:12] += dp[13:25]
    dp = dp[:13] % MOD
  else:
    dp = np.roll(dp, add_single[i%6][int(s)])
  
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
s = input()
n = len(s)
fix = 0
free = []
for i in range(n):
    if s[n-i-1] != '?':
        fix += int(s[n-i-1])*10**i
    else:
        free.append(i)
fixmod = (5 - fix)%13

freemod = [[0]*13 for _ in range(len(free))]
for i, j in enumerate(free):
    for k in range(10):
        freemod[i][(k*10**j)%13] += 1
#print(freemod)
maxq = len(freemod)
dp = [[0]*13 for _ in range(maxq+1)]
dp[0][0] = 1
for i in range(maxq):
    for j in range(13):
        dp[i+1][j] = sum([dp[i][k]*freemod[i][(13+j-k)%13] 
                            for k in range(13)]) % mod
print(dp[maxq][fixmod])

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] == "?":
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+int(S[i]))%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w += DP[0][j]
        DP[0][j] = w

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    ep = [0]*13
    zero = [0]*13
    for c in S:
        ep[:] = zero
        for i in range(10):
            if c != "?" and int(c) != i:
                continue
            for j in range(13):
                ep[(10*j+i) % 13] += dp[j]
                ep[(10*j+i) % 13] %= MOD
        dp, ep = ep, dp

    print(dp[5])

    return


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:
def main():
    S = list(input())
    dp = [[0] * 13 for _ in range(10 ** 5 + 1)]
    dp[0][0] = 1
    n = len(S)
    for i in range(n):
        c = 0
        if S[i] == '?':
            c = -1
        else:
            c = int(S[i])
        for si in range(10):
            if c != -1 and c != si:
                continue
            for j in range(13):
                dp[i + 1][(j * 10 + si) % 13] += dp[i][j]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
    print(dp[n][5])


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    dpn = [0]*13
    keta = 1
    zero = 0
    # print(dp)
    for c in reversed(S):
        if c == "?":
            dpn = [0]*13
            for i in range(10):
                for j in range(13):
                    dpn[j] += dp[(j - i*keta) % 13]
                    dpn[j] %= MOD
            dp = dpn
        else:
            shift = (int(c)*keta) % 13
            dpn = [0]*13
            for i in range(13):
                dpn[i] = dp[(i-shift) % 13]
            # dpn = dp[13-shift:]+dp[:13-shift]
            dp = dpn

        # print(c, dp)
        keta *= 10
        keta %= 13

    print(dp[5])

    return


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:
s = list(input().rstrip())
n = len(s)
m = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input().rstrip())
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

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