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:
N=input()

lists = []
temp=[i for i in range(10)]

dic={0:1}

for i in N:
    new_dic={}
    if i == "?":
        for amari,count in list(dic.items()):
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in list(dic.items()):
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
N=input()

lists = []
temp=[i for i in range(10)]

dic={0:1}

for i in N:
    new_dic={}
    if i == "?":
        for amari,count in list(dic.items()):
            for num in temp:
                a = (amari*10 + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in list(dic.items()):
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=list(input())
n=[1,10,9,12,3,4]
ns=[[]for i in range(6)]
for i in range(6):
  for j in range(10):
    ns[i].append(n[i]*j%13)
#print(ns)
miti=[0,0,0,0,0,0]
now=0
for i in range(len(s)):
  if s[-i-1]=="?":
    miti[i%6]+=1
  else:
    now+=ns[i%6][int(s[-i-1])]
now=now%13
#print(now,miti)

dp=[0 for i in range(26)]
dp[now]=1
for i in range(6):
  for j in range(miti[i]):
    for n in range(13):
      dp[n]=dp[n]%mod
    for k in range(10):
      for l in range(13):
        dp[(l+ns[i][k])%13+13]+=dp[l]
    #print("1",dp)
    dp[0:13]=dp[13:26]
    for m in range(13):
      dp[13+m]=0
    #print("2",dp)
print(dp[5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline().strip

MOD = int(10 ** 9 + 7)

S = input()
N = len(S)
dp1 = [1] + ([0] * 12)
for i in range(N):
    dp2 = [0] * 13
    s = S[i]
    if s == '?':
        c = -1
    else:
        c = int(s)
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp2[(ki * 10 + j) % 13] += dp1[ki]
    for j in range(10):
        dp2[j] %= MOD
    dp1 = dp2
        
print(dp2[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline().strip

MOD = int(10 ** 9 + 7)

dp = []
S = input()
N = len(S)
dp.append([1] + ([0] * 12))
for i in range(N):
    dp.append([0] * 13)
    s = S[i]
    if s == '?':
        c = -1
    else:
        c = int(s)
    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(10):
        dp[i + 1][j] %= MOD
        
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

dp={i:0 for i in range(13)}
dp[0]=1

for i in range(n):
    next_dp={i:0 for i in range(13)}
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            next_dp[(j*10+k)%13] += dp[j]
    dp = {i:next_dp[i]%MOD for i in range(13)}

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

dp={i:0 for i in range(13)}
dp[0]=1

for i in range(n):
    next_dp={i:0 for i in range(13)}
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            next_dp[(j*10+k)%13] += dp[j]%MOD
    dp = next_dp

print(dp[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:

MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

dp={i:[0]*13 for i in range(n+1)}

dp[0][0]=1
for i in range(n):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
dsl = list(input())
n=len(dsl)

dp=[[0]*13]
for i in range(n):
    dp.append([0]*13)

dp[0][0]=1

for i in range(n):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
s = input()
#ind = list(range(len(s)))
dsl = list(s)
#print(sl)
#dsl = dict(zip(ind, sl))
#print(dsl)

#ind2 = list(range(13))
#dp={}
##dp.setdefault(0, dict(zip(ind2,[0]*13)))
#for i in range(len(s)+1):
    ##dp.append(dict(zip(ind2,[0]*13)))
    #dp.setdefault(i, dict(zip(ind2,[0]*13)))
dp=[[0]*13]
for i in range(len(s)):
    dp.append([0]*13)

#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    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()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    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()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

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

dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    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()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

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

dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]
    for k in range(13):
        dp[i+1][k] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
MOD = 10**9+7
n = len(s)
dp = [[0]*13 for _ in range(n)]

if s[0] == '?':
    for i in range(10): dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
MOD = 10**9+7
n = len(s)
dp = [[0]*13 for _ in range(n)]

if s[0] == '?':
    for i in range(10): dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
MOD = 10**9+7
n = len(s)
dp = [0]*13

if s[0] == '?':
    for i in range(10): dp[i] = 1
else:
    dp[int(s[0])] = 1

for num in s[1:]:
    new_dp = [0]*13
    if num == '?':
        for i in range(13):
            for j in range(10):
                new_dp[(i*10+j)%13] += dp[i]
                new_dp[(i*10+j)%13] %= MOD
    else:
        for i in range(13):
            new_dp[(i*10+int(num))%13] += dp[i]
            new_dp[(i*10+int(num))%13] %= MOD
    dp = new_dp

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()

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

# init
if S[0] == '?':
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1

def update(i,j,n):
  dp[i][(j*10+n)%13] += dp[i-1][j]

for i in range(1,len(S)):
  for j in range(13):
    if S[i] == '?':
      for n in range(10):
        update(i,j,n)
    else:
      update(i,j,int(S[i]))

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

Submission status: Time Limit Exceeded

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

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

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

for i in range(2, lenS+1):
    chara = S[i-1]
    if chara=='?':
        for d in range(13):
            for e in range(10):
                newd = (d*10+e)%13
                dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div
    else:
        for d in range(13):
            newd = (d*10+int(chara))%13
            dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()

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

# init
if S[0] == '?':
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1

def update(i,j,n):
  dp[i][(j*10+n)%13] += dp[i-1][j]

for i in range(1,len(S)):
  for j in range(13):
    if S[i] == '?':
      for n in range(10):
        update(i,j,n)
    else:
      update(i,j,int(S[i]))

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

Submission status: Time Limit Exceeded

Solution code:
#45 ABC135D 桁DP
s=input()
n=len(s)
dp=[[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	if s[i]=="?":
		c=-1
	else:
		c=int(s[i])
	for j in range(10):
		if c!=-1 and c!=j:
			continue
		for ki in range(13):
			dp[i+1][(ki*10+j)%13]+=dp[i][ki]
	#for j in range(13):
		#dp[i+1][j]%=(10**9+7)
print(dp[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 1000000007
dp = [[0 for i in range(15)] for _ in range(100005)]
dp[0][0] = 1
for i in range(len(S)):
    c = 0
    if(S[i] == '?'):
        c = -1
    else:
        c = int(S[i])

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)
s.reverse()
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        for j in range(13):
            k = (s1*(10**i))%13
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        for j in range(13):
            for x in range(10):
                k = (x*((10**i)%13))%13
                dp[i][(j+k)%13] += dp[i-1][j]
            dp[i] = [dp[i][j]%(10**9 + 7) for j in range(13)]
print(dp[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)
s.reverse()
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        for j in range(13):
            k = j - (s1*(10**i))%13
            if k < 0:
                k = k + 13
            else:
                k = k % 13
            dp[i][j] = dp[i-1][k]
    else:
        for j in range(13):
            for x in range(10):
                k = (x*((10**i)%13))%13
                dp[i][(j+k)%13] = (dp[i-1][j] + dp[i][(j+k)%13])%(10**9 + 7)
print(dp[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import copy
S=input()
length=len(S)
dp=[0 for i in range(13)]
dp[0]=1
nextdp = [0 for i in range(13)]
s=S[::-1]#一桁目が先頭に来た
p=1#その桁数での10の累乗の13で割ったあまり
#毎回、nextdpをdpに代入して、dpに何か操作してnextdpに代入する
for i in range(length):#0~length-1まで
    if i!=0:
        dp = copy.copy(nextdp)
        for k in range(13):
            nextdp[k]=0
    #print(p)
    if s[i]=="?":
        for j in range(10):#s[i]の数字に対応
            for k in range(13):#dpの要素数に対応
                nextdp[(k+j*p)%13]=(dp[k]+nextdp[(k+j*p)%13])%(10**9+7)
    else:
         for k in range(13):#dpの要素数に対応
                nextdp[(k+int(s[i])*p)%13]=(dp[k]+nextdp[(k+int(s[i])*p)%13])%(10**9+7)
    
    for k in range(13):
        nextdp[k]%=(10**9+7)
    p=(10*p)%13#前回のpの値を用いてpの更新を楽に
    #print(dp)
    #print(nextdp)

         
print(nextdp[5])

Submission status: Time Limit Exceeded

Solution code:
import copy
S=input()
length=len(S)
dp=[0 for i in range(13)]
dp[0]=1
nextdp = [0 for i in range(13)]
s=S[::-1]#一桁目が先頭に来た
p=1#その桁数での10の累乗の13で割ったあまり
#毎回、nextdpをdpに代入して、dpに何か操作してnextdpに代入する
for i in range(length):#0~length-1まで
    if i!=0:
        dp = copy.deepcopy(nextdp)
        for k in range(13):
            nextdp[k]=0
    #print(p)
    if s[i]=="?":
        for j in range(10):#s[i]の数字に対応
            for k in range(13):#dpの要素数に対応
                nextdp[(k+j*p)%13]+=dp[k]
    else:
         for k in range(13):#dpの要素数に対応
                nextdp[(k+int(s[i])*p)%13]+=dp[k]
    
    for k in range(13):
        nextdp[k]%=(10**9+7)
    p=(10*p)%13#前回のpの値を用いてpの更新を楽に
    #print(dp)
    #print(nextdp)

         
print(nextdp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    dd = (10 ** c) % 13
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod

print(table[c + 1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    dd = (10 ** c) % 13
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]

    for i in range(13):
        table[c + 1][i] %= mod
print(table[c + 1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    dd = (10 ** c) % 13
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]

print(table[c + 1][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0
table[0][0] = 1
dd = 1
for c in range(len(s)):
    dd = (10 ** d) % 13
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * dd) % 13] += table[d][i]
    else:
        num = int(s[c])
        for i in range(13):
            table[d + 1][(i + num * dd) % 13] += table[d][i]
    d += 1
print(table[d][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0
table[0][0] = 1
dd = 1
for c in s[::-1]:
    dd = (10 ** d) % 13
    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * dd) % 13] += table[d][i]
    else:
        c = int(c)
        for i in range(13):
            table[d + 1][(i + c * dd) % 13] += table[d][i]
    d += 1
print(table[d][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0
table[0][0] = 1
dd = 1
for c in s[::-1]:
    dd = (10 ** d) % 13
    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * dd) % 13] += table[d][i]
    else:
        for i in range(13):
            table[d + 1][(i + int(c) * dd) % 13] += table[d][i]
    d += 1

    for j in range(13):
        table[d + 1][j] %= mod
print(table[d][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0

for c in s[::-1]:
    if d == 0:
        d += 1
        if c == "?":
            for i in range(10):
                table[1][i] = 1
        else:
            table[1][int(c)] = 1
        continue
    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * 10 ** d) % 13] += table[d][i]

    else:
        for i in range(13):
            table[d + 1][(i + int(c) * 10 ** d) % 13] += table[d][i]
    d += 1

    for j in range(13):
        table[d + 1][j] %= mod
print(table[d][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
d = 0

for c in s[::-1]:
    if d == 0:
        d += 1
        if c == "?":
            for i in range(10):
                table[1][i] = 1
        else:
            table[1][int(c)] = 1
        continue

    if c == "?":
        for n in range(10):
            for i in range(13):
                table[d + 1][(i + n * 10 ** d) % 13] += table[d][i]

    else:
        for i in range(13):
            table[d + 1][(i + int(c) * 10 ** d) % 13] += table[d][i]
    d += 1

print(table[d][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    if S[-1] == '?':
        for i in range(10):
            DP[i] = 1
    else:
        DP[int(S[-1])] = 1

    for i in range(1, n):
        preDP = DP
        DP = [0] * 13
        if S[-i-1] == '?':
            for x in range(10):
                nx = x * 10 ** i
                for k in range(13):
                    t = (nx + k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[-i-1]) * 10 ** i
            for k in range(13):
                t = (y+k) % 13
                DP[t] = preDP[k] % MOD
    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    DP = [0] * 13
    n = len(S)
    if S[-1] == '?':
        for i in range(10):
            DP[i] = 1
    else:
        DP[int(S[-1])] = 1

    for i in range(1, n):
        preDP = DP
        DP = [0] * 13
        if S[-i-1] == '?':
            for x in range(10):
                nx = x * 10 ** i
                for k in range(13):
                    t = (nx + k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[-i-1]) * 10 ** i
            for k in range(13):
                t = (y+k) % 13
                DP[t] = preDP[k] % MOD
    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
text = S[::-1]
MOD = 10**9 + 7


def main():
    DP = [0] * 13
    if text[0] == '?':
        for i in range(10):
            DP[i] = 1
    else:
        DP[int(text[0])] = 1

    for i in range(1, len(S)):
        preDP = DP
        DP = [0] * 13
        if text[i] == '?':
            for x in range(10):
                nx = x * 10 ** i
                for k in range(13):
                    t = (nx + k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(text[i]) * 10 ** i
            for k in range(13):
                t = (y+k) % 13
                DP[t] = preDP[k] % MOD
    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
text = S[::-1]
DP = [0] * 13
MOD = 10**9 + 7

if text[0] == '?':
    for i in range(10):
        DP[i] = 1
else:
    DP[int(text[0])] = 1

for i in range(1, len(S)):
    preDP = DP
    DP = [0] * 13
    if text[i] == '?':
        for x in range(10):
            nx = x * 10 ** i
            for k in range(13):
                t = (nx + k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD
    else:
        y = int(text[i]) * 10 ** i
        for k in range(13):
            t = (y+k) % 13
            DP[t] = preDP[k] % MOD

ans = DP[5]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
text = S[::-1]
DP = [[0] * 13 for _ in range(len(S))]

if text[0] == '?':
    for i in range(10):
        DP[0][i] = 1
else:
    DP[0][int(text[0])] = 1

for i in range(1, len(S)):
    if text[i] == '?':
        for x in range(10):
            nx = x * 10 ** i
            for k in range(13):
                t = (nx + k) % 13
                DP[i][t] += DP[i-1][k]
    else:
        y = int(text[i]) * 10 ** i
        for k in range(13):
            t = (y+k) % 13
            DP[i][t] = DP[i-1][k]

ans = DP[len(S)-1][5] % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

remainder = {0: 1}

for s in S:
    rx = {r: 0 for r in range(13)}
    for n in (range(10) if s == '?' else [int(s)]):
        for r in remainder:
            r2 = (r * 10 + n) % 13
            rx[r2] += remainder[r]
            rx[r2]  = rx[r2] % modulo
    remainder = rx

print(remainder[5] % modulo)

Submission status: Time Limit Exceeded

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

if s[0] == '?':
    for i in range(10):
        dp[i][0] = 1
else:
    dp[int(s[0])][0] = 1

mod_change_table = [(i*10)%13 for i in range(13)]

for x in range(1,len(s)):
    for y in range(13):
        if s[x]=='?':
            for j in range(10):
                dp[(mod_change_table[y]+j)%13][x] += dp[y][x-1]
        else:
            dp[(mod_change_table[y]+int(s[x]))%13][x] += dp[y][x-1]
            

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

Submission status: Time Limit Exceeded

Solution code:
#10:30
s = input()
n = len(s)
now = [1,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  last = now
  now = [0 for _ in range(13)]
  here = s[i]
  if here == '?':
    for k in range(10):
      for j in range(13):
        now[(10*j+k)%13] += last[j]
  else:
    k = int(here)
    for j in range(13):
      now[(10*j+k)%13] += last[j]
  for j in range(13):
    now[j] %= 10**9+7
print(now[5])

Submission status: Time Limit Exceeded

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

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = (int(d) * MODS[i % 6]) % 13
            cur[m:m+13] = priv[0:13]
            cur[0:13] += cur[13:26]
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Time Limit Exceeded

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

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Time Limit Exceeded

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

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        priv = cur[0:13]
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Time Limit Exceeded

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

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13, dtype=np.int)
        d = s[i]
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] = (cur[(j+m) % 13] + priv[j]) % P_MOD
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Time Limit Exceeded

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

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = [1, 10, 9, 12, 3, 4]

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = [1] + [0] * 12
    # print(priv)
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        # print('i=', i, 'd=', d)
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] += priv[j]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        # print(cur)
        for j in range(13):
            priv[j] = cur[j] % P_MOD
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Time Limit Exceeded

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

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = [1, 10, 9, 12, 3, 4]

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = [1] + [0] * 12
    # print(priv)
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        # print('i=', i, 'd=', d)
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] += priv[j]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        # print(cur)
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()
a = [[0 for i in range(len(s))] for j in range(13)]

if s[0] == '?':
    for i in range(10):
        a[i][0] += 1
else:
    a[int(s[0])][0] += 1


for i in range(len(s)-1):
    if s[i+1] == '?':
        for j in range(13):
            #a[j][i]
            tmp = j * 10
            for k in range(10):
                a[tmp%13][i+1] += a[j][i]
                tmp += 1
    else:
        tmp = int(s[i+1])
        for j in range(13):
            x = (j * 10 + tmp)%13
            a[x][i+1] += a[j][i]
#print(a)
print(a[5][len(s)-1]%1000000007)