Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

??2??5

Sample Output 1

768

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

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
S = input()
N, MOD, k = 13, 10 ** 9 + 7, 1
dp = [0 for _ in range(N)]
dp[0] = 1
for s in reversed(S):
  dp2 = [0 for _ in range(N)]
  if s == "?":
    for d in range(10):  # 0 ~ 9
      for n in range(N):
        index = (d * k + n) % N
        dp2[index] += dp[n]
        dp2[index] %= MOD 
  else:
    d = int(s)
    for n in range(N):
      index = (d * k + n) % N
      dp2[index] += dp[n]
      dp2[index] %= MOD 
  dp = dp2
  k *= 10 % N
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
mod = 10**9+7
p = list(input())

# アルゴリズム
dp = np.array([0] * 13)
dp[0] = 1
for i in reversed(range(len(p))):
    new_dp = np.array([0] * 13)
    if p[i] == "?":
        for j in range(10):
            for k in range(13):
                new_dp[(k + j * 10 ** (len(p) - i - 1)) % 13] += dp[k]
                new_dp %= mod
    else:
        for j in range(13):
            new_dp[(j + int(p[i]) * 10 ** (len(p) - i - 1)) % 13] += dp[j]
            new_dp %= mod
    dp = copy.copy(new_dp)

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N, MOD = 13, 10 ** 9 + 7
dp = [0 for _ in range(N)]
dp[0] = 1
for i, s in enumerate(reversed(S)):
  dp2 = [0 for _ in range(N)]
  if s == "?":
    for d in range(10):  # 0 ~ 9
      for n in range(N):
        index = (d * (10 ** i) + n) % N
        dp2[index] += dp[n]
        dp2[index] %= MOD 
  else:
    d = int(s)
    for n in range(N):
      index = (d * (10 ** i) + n) % N
      dp2[index] += dp[n]
      dp2[index] %= MOD 
  dp = dp2
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
remain=[1,0,0,0,0,0,0,0,0,0,0,0,0]

#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()


##漸化式を用意
ind=[1,-3,-4,-1,3,4]
def rec(ls,num,dig):
  val_ls=[0]*13
  if num!="?":
    for i in range(13):
      val_ls[i]=val_ls[i]+ls[(i-ind[dig]*int(num))%13]%M
  else:
    for i in range(13):
      for j in range(10):
        val_ls[i]=val_ls[i]+ls[(i-ind[dig]*j)%13]
        val_ls[i]=val_ls[i]%M
  return val_ls

##漸化式をremainに適用
for k in range(len(lst)):
  remain=rec(remain,lst[k],k%6)
  
print(remain[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
smax = ''
smin = ''
for i in range(len(s)):
    if s[i] == '?':
        smax += '9'
        smin += '0'
    else:
        smax += s[i]
        smin += s[i]

n = int(smin) + (5-int(smin)%13)

count = 0
while n <= int(smax):
    p = str(n).zfill(len(s))
    tf = True
    for i in range(len(s)):
        if s[i] != '?':
            if s[i] != p[i]:
                tf = False
                break
    if tf is True:
        count = (count+1) % (10**9 + 7)
    n += 13

print(count)

Submission status: Time Limit Exceeded

Solution code:

S = input()
dp = [[0 for i in range(15)] for j in range(100005)]
mod = 1000000007

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
smax = ''
smin = ''
for i in range(len(s)):
    if s[i] == '?':
        smax += '9'
        smin += '0'
    else:
        smax += s[i]
        smin += s[i]

n = int(smin) + (5-int(smin)%13)
#print(n)
count = 0
while n <= int(smax):
    p = str(n).zfill(len(s))
    tf = True
    for i in range(len(s)):
        if s[i] != '?':
            if s[i] != p[i]:
                tf = False
                break
    if tf is True:
        count = (count+1) % (10**9 + 7)
    n += 13

print(count)

Submission status: Time Limit Exceeded

Solution code:
def modification(n):
    if n<=12:
        return n
    else:
        return n-13


def main():
    s = list(input())
    s = s[::-1]

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

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

        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%15==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

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

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(N)]
if S[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1
for i in range(1, N):
    if S[i] == '?':
        for s in range(0, 10):
            for j in range(0, 13):
                for k in range(0, 13):
                    if (10 * k + s) % 13 == j:
                        dp[i][j] += dp[i - 1][k]
    else:
        s = int(S[i])
        for j in range(0, 13):
            for k in range(0, 13):
                if (10 * k + s) % 13 == j:
                    dp[i][j] += dp[i-1][k]

    for j in range(13):
        dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if i%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if i%5==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][((j*10)%13+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][((j*10)%13+s[i])%13]+=dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):

  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][((j*10)%13+k)%13]+=dp[i][j]%MOD
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][((j*10)%13+s[i])%13]+=dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [[0 for x in range(13)] for c in range(n)]
dp[0][0] = 1

for i, x in enumerate(s):
    for j in range(10):
        if (x == -1) or (x == j):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    dp[i+1] = [k % MOD for k in dp[i+1]]

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

s = input()
n = len(s) + 1

dp = [[0 for x in range(13)] for c in range(n)]
dp[0][0] = 1

for i, x in enumerate(s):
    if x == '?':
        x = -1
    else:
        x = int(x)

    for j in range(10):
        if (x == -1) or (x == j):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    dp[i+1] = [k % MOD for k in dp[i+1]]

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

Submission status: Time Limit Exceeded

Solution code:
s = [x for x in input()]

q_pos = [i if x == '?' else None for i, x in enumerate(s)]
q_pos = [x for x in q_pos if x is not None]

q_size = len(q_pos)
ans = 0
for i in range(10 ** q_size):
    r = [x for x in str(i).zfill(q_size)]
    for i_q, r_q in zip(q_pos, r):
        s[i_q] = r_q
    if (int(''.join(s)) - 5) % 13 == 0:
        ans += 1

print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
# ? だったら -1
S = [int(x) if x != "?" else -1 for x in input()]

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

# i文字目, 13で割った余りがj

for i in range(len(S)):
    #
    if S[i] == -1:
        # 0 ~ 9の数字が入ることを考える
        for n in range(10):
            # 余りは0 ~ 12 が入る
            for j in range(13):
                dp[i+1][(j*10+n) % 13] += dp[i][j]
    else:
        n = S[i]
        for j in range(13):
            dp[i+1][(j*10+n) % 13] += dp[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
#print(S)
dp = [[0 for _ in range(13)] for _ in range(len(S))]
temp = 0

while dp[len(S) - 1][5] == 0:
  #print(dp)
  if temp == len(S):
    break
  for i in range(13):
    if temp == 0:
      #print(temp, i, S[temp])
      if S[temp] == "?":
        if i <= 9:
          dp[temp][i] = 1
      elif int(S[temp]) == i:
        dp[temp][i] = 1
      continue
    if S[temp] == "?":
      for j in range(13):
        if not i in {(j * 10 + k) % 13 for k in range(10)}:
          continue
        #print(temp, i, j, S[temp])
        dp[temp][i] += dp[temp - 1][j]
    else:
      j = 0
      for k in range(13):
        if (k * 10 + int(S[temp])) % 13 == i:
          j = k
          break
      dp[temp][i] += dp[temp - 1][j]
    dp[temp][i] %= 10 ** 9 + 7
  temp += 1
#print(dp)
print(dp[len(S) - 1][5])

Submission status: Time Limit Exceeded

Solution code:
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, s in enumerate(S):
    c = -1 if s == "?" else int(s)

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

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

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
# import sys
# input = sys.stdin.readline
s = [int(x) if x!="?" else -1 for x in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*n
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i,j):
	if j-a*data[i]%A>=0:
		re = j-a*data[i]%A
	else:
		re = j-a*data[i]%A+13
	return re

for i in range(n):
	for j in range(A+1):
		if s[i]!=-1:
			dp[i+1][j]=dp[i][benri(s[i],i,j)]

		else:
			for c in range(10):
				dp[i+1][j]+=dp[i][benri(c,i,j)]

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

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

S=input()

dp=[]
for i in range(len(S)):
  dp.append([0]*13)
#print(dp)

if S[-1]=="?":
  for j in range(10):
    dp[-1][j]=1
else:
  sj=int(S[-1])
  dp[-1][sj]=1
  
pow_mod=1
for i in range(1,len(S)):
  pow_mod*=10
  pow_mod%=13
  if S[-i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[-i-1][(k+j*pow_mod)%13]+=dp[-i][k]
        dp[-i-1][(k+j*pow_mod)%13]%=mod
  else:
    sj=int(S[-i-1])
    for k in range(13):
      dp[-i-1][(k+sj*pow_mod)%13]+=dp[-i][k]
      dp[-i-1][(k+sj*pow_mod)%13]%=mod
    
#print(dp)
print(dp[0][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()]

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

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j*10+d) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j*10+d) % 13] += dp[i][j]

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

    # print(dp)

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()][::-1]

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

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j+d*10**i) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

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

    # print(dp)

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

Submission status: Time Limit Exceeded

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

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

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

    for d in c:
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

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

    # print(dp)

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

Submission status: Time Limit Exceeded

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

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

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

    for d in c:
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

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

    # print(dp)

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

Submission status: Time Limit Exceeded

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

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

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

    for d in c:
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

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

    # print(dp)

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

Submission status: Time Limit Exceeded

Solution code:
N = input()
M = len(N)
count = 0


for i in range(5,10**M,13):
    rets = str(i).zfill(M)
    for j in range(M):
        if N[j] == "?" or N[j] == rets[j]:
            if j == M-1:
                count += 1
        else:
            break

        
print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
s = input()
count = 0
a = []

for i in range(len(s)):
    if s[i]!='?':
        count = ((10**(len(s)-i-1)*int(s[i]))%13+count)%13
    else:
        a.append(i)

b =[[0]*13 for i in range(len(a)+1) ]
b[0][count] = 1

for i in range(len(a)):
    
    c = []
    c.append(0)
    c.append((10**(len(s)-a[i]-1)%13))
    c.append((c[1]*2)%13)
    c.append((c[1]*3)%13)
    c.append((c[1]*4)%13)
    c.append((c[1]*5)%13)
    c.append((c[1]*6)%13)
    c.append((c[1]*7)%13)
    c.append((c[1]*8)%13)
    c.append((c[1]*9)%13)
    for j in range(len(c)):
             for k in range(13):
                 b[i+1][(c[j]+k)%13] = int((b[i+1][(c[j]+k)%13] + b[i][k])%(10**9+7))
    
print(b[len(a)][5])

Submission status: Time Limit Exceeded

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

total = 1
for i in range(len(S)):
    s = S[i]
    if s == '?':
        for j in range(13):
            dp[i+1][j] = total-dp[i][4-int((j+2)/3)]-dp[i][8-int((j+1)/3)]-dp[i][12-int(j/3)]
        total *= 10
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s))%13] += dp[i][j]
print(dp[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp,mod = [[0]*13 for i in range(len(s)+1)],10**9+7
dp[0][0],x = 1,[0,4,8,12,3,7,11,2,6,10,1,5,9]
for i in range(len(s)):
    if s[i]=="?":
        for k in range(10):
            for j in range(13): dp[i+1][j] = (dp[i+1][j]+dp[i][x[j-k]])%mod
    else:
        for j in range(13): dp[i+1][j] = dp[i][x[j-int(s[i])]]
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
ds = "0123456789"

def calc(s, r, rs):
    if len(s) == 0:
        return 1 if r == 5 else 0
    elif r == 0 and s in rs:
        return rs[s]
    else:
        c = 0

        if s[0] == "?":
            for d in ds:
                c += calc(d + s[1:], r, rs)
        else:
            c += calc(s[1:], (r * 10 + int(s[0])) % 13, rs)

        if s not in rs:
            rs[s] = c

        return c

s  = input()
rs = {}

for i in range(1, len(s) + 1):
	calc(s[len(s) - i:], 0, rs)
	
print(rs[s] % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
s = [int(x) if x!='?' else -1 for x in input()]

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    if s[i] == -1:
        for j in range(13):
            x = mod_x10[j]
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j] % mod
    else:
        for j in range(13):
            x = (mod_x10[j] + s[i] + 1) % 13
            ans[i+1][x] += ans[i][j] % mod

print(ans[length][5] % mod)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len(S)):
    s = S[i]
    if s == '?':
        for j in range(13):
            dp[i+1][j] = 10**cnt-dp[i][4-int((j+2)/3)]-dp[i][8-int((j+1)/3)]-dp[i][12-int(j/3)]
        cnt += 1
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s))%13] += dp[i][j]
print(dp[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

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

for i in range(len(S)):
    s = S[i]
    if s == '?':
        for j in range(13):
            dp[i+1][j] = sum(dp[i])-dp[i][4-int((j+2)/3)]-dp[i][8-int((j+1)/3)]-dp[i][12-int(j/3)]
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s))%13] += dp[i][j]
print(dp[len(S)][5]%MOD)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
s = [int(x) if x!='?' else -1 for x in input()]

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    for j in range(13):
        x = mod_x10[j]
        if s[i] == -1:
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j]
        else:
            x = (x + int(s[i]) + 1) % 13
            ans[i+1][x] += ans[i][j]

print(ans[length][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    for j in range(13):
        x = mod_x10[j]
        if s[i] == '?':
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j]
        else:
            x = (x + int(s[i]) + 1) % 13
            ans[i+1][x] += ans[i][j]

print(ans[length][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[] for i in range(S.count("?"))]
cnt = 0
mul = 1
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
        extra %= 13
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * mul % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

    mul = mul * 10 % 13

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


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

"""
S = list(str(input()))

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

# print(dp)
print(dp[-1][5])
"""

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
        extra %= 13
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod


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

"""
S = list(str(input()))

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

# print(dp)
print(dp[-1][5])
"""

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod

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

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    # for j in range(13):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod

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

Submission status: Time Limit Exceeded

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

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
for i in range(1, len(S)+1):
    s = S[i-1]

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

Submission status: Time Limit Exceeded

Solution code:
#import time
import numpy as np

#st = time.time()

S = list(input())

hatena = S.count('?')
hatena_list = [len(S)-1-i for i, x in enumerate(S) if x == '?']

hatena_list_np = np.array(hatena_list)

#print(hatena_list)  
l_np = np.zeros((hatena+1, 13))
#l = [[0]*13 for _ in range(hatena+1)]
 
SS = S.copy()
for i in range(len(S)):
    if SS[i] == '?':
        SS[i] = '0'
SS_13 = int(''.join(SS))%13
#l[0][SS_13] = 1
l_np[0, SS_13] = 1

def function(x):
    if x<0:
        x = 13+x
    return x
 
def function_np(x):
    return x + (x<0)*13

def power_mod_13(base, p):
    ret = 1
    while(p!=0):
        ret = ret * base % 13 if p%2 else ret
        base = base * base % 13
        p //= 2
    return ret % 13

for i in range(1,hatena+1):
    s = hatena_list[i-1]
    j_np = np.array(range(0,10))
    SS_13_np = (power_mod_13(10, s) * j_np) % 13
    k_np = np.array(range(0,13))
    #l_np[i, k_np] += 
    temp = function_np(k_np.reshape((-1,1)) - SS_13_np.reshape(1,-1))
    l_np[i] = np.sum(l_np[i-1, temp], axis=1) % 1000000007
    #for j in range(0,10):
    #    SS_13 = 10**s *j %13
    #    for k in range(0,13):
    #        l[i][k] += l[i-1][function(k-SS_13)] % 1000000007
    #        l[i][k] %= 1000000007
       
#print(l[-1][5])
print(int(l_np[-1][5]))

Submission status: Time Limit Exceeded

Solution code:
S=input()
n=len(S)
mod=1e9+7
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]=='?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
    else:
        j=int(S[i])
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
    
    for j in range(13):
        dp[i+1][j]%=mod
            
print(int(dp[n][5]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()

MOD = 1000000007

dp = np.zeros(13, dtype=np.int)

for i, ss in enumerate(s[::-1]):
    if i == 0:
        if ss == "?":
            for n in range(10):
                dp[n%13] += 1
        else:
            n = int(ss)
            dp[n%13] = 1
            
    else:
        if ss == "?":
            new_dp = np.zeros(13, dtype=np.int)
            for n in range(10):
                shift = (n*(10**i))%13
                for j in range(13):
                    new_dp[(j+shift)%13] += dp[j]
            dp = new_dp%MOD
        else:
            n = int(ss)
            shift = (n*(10**i))%13
            new_dp = np.zeros(13, dtype=np.int)
            for i in range(13):
                new_dp[(i+shift)%13] = dp[i]
            dp = new_dp%MOD
    
#     print(dp)
    
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
input_num = input()

question_offset = []
for offset, i in enumerate(input_num):
    if i == '?':
        question_offset.append(offset)

count = 0

for i in range(pow(10, len(question_offset))):
    num = input_num
    for j in range(len(question_offset)):
        tmp = int(i / pow(10, len(question_offset)-j-1))
        if tmp < 1:
            num = num.replace('?', '0', 1)
        else:
            num = num.replace('?', str(tmp%10), 1)

    num = int(num)
    if num % 13 == 5:
        count += 1

print(count)