Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

??2??5

Sample Output 1

768

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

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
N=len(S)

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

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

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def rem():
  mod=10**9+7
  s=input()
  dp=np.zeros((len(s)+1,13),dtype=int)
  dp[0][0]=1
  r=[i%13 for i in range(130)]

  for i in range(len(s)):
    if s[i]=='?':
      for j in range(13):
        for k in range(10):
          dp[i+1][r[j*10+k]]+=dp[i][j]
    else:
      t = int(s[i])
      for j in range(13):
        dp[i+1][r[j*10+t]] += dp[i][j]

    for k in range(13):
      dp[i+1][k] %= mod

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

rem()

Submission status: Time Limit Exceeded

Solution code:
def rem():
  mod=10**9+7
  s=input()
  dp=[[0]*13 for _ in range(len(s)+1)]
  dp[0][0]=1
  r=[i%13 for i in range(130)]

  for i in range(len(s)):
    if s[i]=='?':
      for j in range(13):
        for k in range(10):
          dp[i+1][r[j*10+k]]+=dp[i][j]
    else:
      t = int(s[i])
      for j in range(13):
        dp[i+1][r[j*10+t]] += dp[i][j]

    for k in range(13):
      dp[i+1][k] %= mod

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

rem()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(len(s)):
  if s[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i+1][r[j*10+k]]+=dp[i][j]
  else:
    t = int(s[i])
    for j in range(13):
      dp[i+1][r[j*10+t]] += dp[i][j]

  for k in range(13):
    dp[i+1][k] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
s=input()
dp=[[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0]=1
for i in range(1,len(s)+1):
  r=[0 for _ in range(13)]
  if s[-i]=='?':
    for j in range(10):
      t=j*(10**(i-1))
      r[t%13]=1
    for k in range(13):
      for l in range(13):
        dp[i][(k+l)%13]+=dp[i-1][k]*r[l]
  else:
    t=int(s[-i])*(10**(i-1))
    r[t%13]=1
    for k in range(13):
      for l in range(13):
        dp[i][(k+l)%13]+=dp[i-1][k]*r[l]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np 

MOD = 10 ** 9 + 7

s = sys.stdin.readline().rstrip()
l = len(s)

def main():
    dp = np.zeros(13, dtype=np.int64); dp[0] = 1
    for d in s:
        prev = dp.copy()
        dp = np.zeros(13, dtype=np.int64)
        if d != '?':
            d = int(d)
            np.add.at(dp, (np.arange(13)*10+d)%13, prev)
        else:
            np.add.at(dp, (np.arange(13)*10+np.arange(10)[:, None])%13, prev)
        dp %= MOD
    return dp[5]
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np 

MOD = 10 ** 9 + 7

s = sys.stdin.readline().rstrip()
l = len(s)

def main():
    dp = np.zeros(13, dtype=np.int64); dp[0] = 1
    for d in s:
        prev = dp.copy()
        dp = np.zeros(13, dtype=np.int64)
        if d != '?':
            d = int(d)
            np.add.at(dp, (np.arange(13)*10+d)%13, prev)
        else:
            for k in range(10):
                np.add.at(dp, (np.arange(13)*10+k)%13, prev)
        dp %= MOD
    return dp[5]
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 10 ** 9 + 7

s = sys.stdin.readline().rstrip()
l = len(s)

def main():
    dp = [[0] * 13 for _ in range(l+1)]
    dp[0][0] = 1
    for i in range(l):
        d = s[i]
        if d != '?':
            d = int(d)
            for j in range(13):
                dp[i+1][(j*10+d)%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] %= MOD
    
    return dp[l][5]
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
Sinfo=''
for i in range(0,N):
    if S[i]=='?':
        Sinfo+='0'
    else:
        Sinfo+=S[i]
first=int(Sinfo)%13
count=0
hatenadata=[]
for i in range(0,N):
    if S[i]=='?':
        count+=1
        hatenadata.append(i)

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-k*10**((digit-1)%6))%13] for k in range(0,10))%(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
Sinfo=''
for i in range(0,N):
    if S[i]=='?':
        Sinfo+='0'
    else:
        Sinfo+=S[i]
first=int(Sinfo)%13
count=0
hatenadata=[]
for i in range(0,N):
    if S[i]=='?':
        count+=1
        hatenadata.append(i)

r=[[(i*10**(j-1))%13 for i in range(0,10)] for j in range(1,7)]

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-r[(digit-1)%6][k])%13] for k in range(0,10))%(10**9+7)


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

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
Sinfo=''
for i in range(0,N):
    if S[i]=='?':
        Sinfo+='0'
    else:
        Sinfo+=S[i]
first=int(Sinfo)%13
count=0
hatenadata=[]
for i in range(0,N):
    if S[i]=='?':
        count+=1
        hatenadata.append(i)

r=[[(i*10**(j-1))%13 for i in range(0,10)] for j in range(1,7)]

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-r[(digit-1)%6][k])%13] for k in range(0,10))


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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

def main():
    s = SI()
    n = len(s)
    dp = [[0] * 13 for _ in range(n + 1)]
    # dp[i][m]...iケタ目までみたときに、余りがmになる数の個数
    dp[0][0] = mint(1)
    e10 = 1
    for i, c in enumerate(s[::-1]):
        for m in range(13):
            pre = dp[i][m]
            if pre == 0: continue
            if c == "?":
                for d in range(10):
                    nm = (m + d * e10) % 13
                    dp[i + 1][nm] += pre
            else:
                nm = (m + int(c) * e10) % 13
                dp[i + 1][nm] += pre
        e10 = e10 * 10 % 13
    print(dp[n][5])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

def main():
    s = SI()
    n = len(s)
    dp = [[0] * 13 for _ in range(n + 1)]
    # dp[i][m]...iケタ目までみたときに、余りがmになる数の個数
    dp[0][0] = mint(1)
    e10 = 1
    for i, c in enumerate(s[::-1]):
        for m in range(13):
            pre = dp[i][m]
            if pre == 0: continue
            if c == "?":
                for d in range(10):
                    nm = (m + d * e10) % 13
                    dp[i + 1][nm] += pre
            else:
                nm = (m + int(c) * e10) % 13
                dp[i + 1][nm] += pre
        e10 = e10 * 10
    print(dp[n][5])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7
 
def input():
    return sys.stdin.readline()[:-1]
 
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5+10)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        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 *= 10 % 13
    print(dp[l][5]%MOD)
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    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[l][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*(13) for _ in range(len(S)+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    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 *= 10 % 13
print(dp[l][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(len(S)+5)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        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 *= 10 % 13
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(len(S)+5)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        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 *= 10 % 13
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5+10)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        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 *= 10 % 13
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5+10)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        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 *= 10
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

mod = 10**9+7
s = readline().rstrip().decode('utf-8')

dp = [0]*13 #あまりが0~12の13通りとなる場合の数
dp[0] = 1
dig = 1 #今見てる桁数
for i in range(len(s)-1,-1,-1): #小さい方の桁から見ていく
    c = s[i]
    next_dp = [0]*13 #逐次更新してはいけないので、次の桁の数についてjを回して入れていく
    if c == "?": #?なら0~10の10通り全てについてあたる必要がある
        for d in range(10):
            for j in range(13):
                next_dp[(d*dig + j)%13] += dp[j]
                next_dp[(d*dig + j)%13] %= mod

    
    else:
        d = int(c)
        for j in range(13):
            next_dp[(d*dig + j)%13] += dp[j]
            next_dp[(d*dig + j)%13] %= mod


    dig *= 10
    dp = next_dp

print(dp[5]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
s=s[::-1]

n=len(s)
modlist=[[0 for i in range(13)]for _ in range(n+1)]

#13で割ったあまりの判定方法
if s[0]!="?":
    modlist[0][int(s[0])]=1
elif s[0]=="?":
    for  i in range(10):
        modlist[0][i]=1
for i in range(1,n):
    if s[i]!="?":
        add=(int(s[i])*(10**(i)))%13
        for  j in range(13):
            modlist[i][j]+=modlist[i-1][(j-add)%13]
            modlist[i][j]%(10**9+7)
            

    else:
        for nums in range(10):
                add=nums*(10**i)%13
                for  j in range(13):
                    modlist[i][j]+=modlist[i-1][(j-add)%13]
                    modlist[i][j]=modlist[i][j]%(10**9+7)

print(modlist[-2][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
dp = np.zeros(13, dtype=int)
dp[0] = 1
m = 1
for ind, i in enumerate(reversed(s)):
    tmp = np.zeros(13, dtype=int)
    for j in range(10):
        if i!='?' and int(i)!=j:
            continue
        tmp += np.roll(dp, j*m%13)
    dp = tmp%(10**9+7)
    m = 10*m%13
print(dp[5])

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
mul = 1

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

    mul = mul*10%13

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

Submission status: Time Limit Exceeded

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

def main():
    s = str(input())
    l = len(s)
    dp = np.zeros((2,13),dtype=int)
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for st in s:
        for j in range(13):
            if st != "?":
                num = int(st)
                dp[use][(j*10+num)%13] = dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for st in s:
        for j in range(13):
            if st != "?":
                num = int(st)
                dp[use][(j*10+num)%13] = dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[use][(j*10+num)%13] += dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[use][(j*10+num)%13] += dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
        for j in range(13):
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(l+1)]
    MOD = 10**9+7
    dp[0][0] = 1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[i+1][(j*10+num)%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[-1][5])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]

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

for ind, i in enumerate(s):
    m = 10**ind%13
    tmp = [0]*13
    for j in range(10):
        if i!='?' and int(i)!=j:
            continue
        for k in range(13):
            tmp[k] += dp[(k-j*m%13)%13]
    dp = tmp
print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3
#print(l)
for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  #print(l)
print(l[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = int(1e+9) + 7
A = [(10*i)%13 for i in range(13)]
B = [0 for i in range(13)]
B[0] = 1
for i in range(len(S)):
  LN = [0 for i in range(13)]
  if S[i] == '?':
    for _ in range(10):
      for j in A:
        LN[(j+_)%13] += B[j]
        LN[(j+_)%13] %= mod
  else:
    d = int(S[i])
    for j in A:
      LN[(j+d)%13] += B[j]
      LN[(j+d)%13] %= mod
  if i != len(S) - 1:
    for _ in range(13):
      B[A[_]] = LN[_]
  else:
    for _ in range(13):
      B[_] = LN[_]
print(B[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = int(1e+9) + 7
A = [(10*i)%13 for i in range(13)]
B = [0 for i in range(13)]
B[0] = 1
for i in range(len(S)):
  LN = [0 for i in range(13)]
  if S[i] == '?':
    for _ in range(10):
      for j in range(13):
        LN[(A[j]+_)%13] += B[A[j]]
        LN[(A[j]+_)%13] %= mod
  else:
    d = int(S[i])
    for j in range(13):
      LN[(A[j]+d)%13] += B[A[j]]
      LN[(A[j]+d)%13] %= mod
  if i != len(S) - 1:
    for _ in range(13):
      B[A[_]] = LN[_]
  else:
    for _ in range(13):
      B[_] = LN[_]
print(B[5])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[-1]] + [0]*3

for i, s in enumerate(S[-2::-1]):
  if s == "?":
    l = [(sum([l[(k-j*10**(i+1))%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[(k-int(s)*10**(i+1))%13] for k in range(13)]
  #print(l)
print(l[5])

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)]  for i in range(10) }
d["?"] = [1] * 10 
l = d[S[-1]] + [0]*3

for i, s in enumerate(S[-2::-1]):
  if s == "?":
    l = [(sum([l[(k-j*10**(i+1))%13] * d[s][j] for j in range(10)])) for k in range(13)]
    l = [j%N for j in l]
  else:
    l = [l[(k-int(s)*10**(i+1))%13] for k in range(13)]
  #print(l)
print(l[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] + [0]*3 for i in range(10) }
d["?"] = [1] * 10 + [0]*3
l = d[S[-1]] + [0]*3

for i, s in enumerate(S[-2::-1]):
  l = [(sum([l[(k-j*10**(i+1))%13] * d[s][j] for j in range(13)]))%N for k in range(13)]
  #print(l)
print(l[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = list(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):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j]#i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
            
print(dp[n][5]%mod)