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:
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13), int)
a = S[-1]
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l[li][int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(dp[-1][5])

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x %= mod
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l[li][int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l[li][int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[13 - i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x += np.hstack((x_[v:13], x_[:v]))
    else:
        if s == "0":
            x += x_
        else:
            v = l[li][int(s) - 1]
            x += np.hstack((x_[v:13], x_[:v]))
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)
lookup = {(i, j): (i + j) % 13 for i in range(13) for j in range(13)}

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[lookup[(r, _r)]] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])

Submission status: Time Limit Exceeded

Solution code:
# 桁DP: 

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

# dp[前方からの桁数][13で割ったあまり] := 個数 
dp = [[0] * 13 for _ 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] % mod
    else:
        for k in range(13):
            dp[i+1][(k * 10 + int(S[i])) % 13] += dp[i][k] % mod

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

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in range(1, 10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
    else:
        v = 13 - int(s) * now % 13
        x += np.hstack((x_[v:13], x_[:v]))
    x %= mod
    now, pre = (now - pre) % 13, now
    x_ = x
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        for v in range(10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
    else:
        v = 13 - int(s) * now % 13
        x += np.hstack((x_[v:13], x_[:v]))
    x %= mod
    now, pre = (now - pre) % 13, now
    x_ = x
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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

for i in range(n):
    if S[i] == '?':
        for num in range(10):
            for j in range(13):
                dp[i+1][(j*10+num)%13] += dp[i][j]
    else:
        num = int(S[i])
        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][5])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mod = 10 ** 9 + 7

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(j*10+k)%13] += dp[j]
                    next_dp[(j*10+k)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[(j*10+k)%13] += dp[j]
                    next_dp[(j*10+k)%13] %= mod

    #    mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mul = 1
    mod = 10 ** 9 + 7
    s.reverse()

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=(i*10**k)%13
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=(int(t)*10**k)%13
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
d={i:0 for i in range(13)}
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2={i:0 for i in range(13)}
        for i in range(10):
            u=(i*10**k)%13
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=(int(t)*10**k)%13
        d2={i:0 for i in range(13)}
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mul = 1
    mod = 10 ** 9 + 7
    s.reverse()

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        else:
            for j in range(0, 13):
                    next_dp[(int(s[i])*mul+j)%13] += dp[j]
                    next_dp[(int(s[i])*mul+j)%13] %= mod

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def calc(S):
    N = len(S)
    k = []
    x = 0
    for i in range(N):
        if (S[N - 1 - i] == '?'):
            k += [i]
        else:
            x += int(S[N - 1 - i]) * 10 ** i
    if (not (k)):
        return 1 if x % 13 == 5 else 0
    j = k.pop(0)
    d = {}
    for l in range(10):
        d[(l * 10 ** j) % 13] = 1
    for j in k:
        newd = {i: 0 for i in range(13)}
        for key in d:
            for l in range(10):
                mod = (l * 10 ** j) % 13
                newd[(key + mod) % 13] += d[key]
        d = newd
    m = (5 - x % 13) % 13
    ans = d[m] if m in d else 0
    return ans % (10 ** 9 + 7)


print(calc(input()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007;

dp=np.zeros(13*2,dtype='int64')

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=np.zeros(13,dtype='int64')
c=s[0]

if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp.fill(0)
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r.fill(0)
	if (c==-1):
		w=np.sum(dp[4:14])
		for j in range(13):
			r[j]+=w
			w+=dp[j+1]
			w-=dp[4+j]
	else:
		r+=dp[13-c:26-c]
print (r[5]%MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
if a == "?":
    dp[0][0:10] = 1
else:
    dp[0][int(a)] = 1
for i, s in zip(range(1, n), reversed(S[:-1])):
    x_ = dp[i - 1]
    x = dp[i]
    if s == "?":
        for v in range(10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
        x %= mod
    else:
        v = 13 - int(s) * now % 13
        x += np.hstack((x_[v:13], x_[:v]))
        x %= mod
    now, pre = (now - pre) % 13, now
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

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

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
if a == "?":
    dp[0][0:10] = 1
else:
    dp[0][int(a)] = 1
for i, s in zip(range(1, n), reversed(S[:-1])):
    x_ = dp[i - 1]
    x = dp[i]
    if s == "?":
        for v in range(10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
            x %= mod
    else:
        v = 13 - int(s) * now % 13
        x += np.hstack((x_[v:13], x_[:v]))
        x %= mod
    now, pre = (now - pre) % 13, now
print(int(dp[-1][5]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007;

dp=np.zeros(13*2,dtype='int64')

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=np.zeros(13,dtype='int64')
c=s[0]

if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp.fill(0)
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r.fill(0)
	if (c==-1):
		for j in range(10):r+=dp[13-j:26-j]
	else:
		r+=dp[13-c:26-c]
print (r[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007;


def initMod(c):
	a=np.zeros(13,dtype='int64')
	if (c!=-1):
		a[c]=1
	else:
		for i in range(10):a[i]=1
	return a;


s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=initMod(s[0])

for i in range(1,n):
	dp=np.zeros(13*2,dtype='int64')
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=np.zeros(13,dtype='int64')
	if (c==-1):
		for j in range(10):r+=dp[13-j:26-j]
	else:
		r+=dp[13-c:26-c]
print (r[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    con = 10**9 + 7

    def get_mod(S):
        c = {}
        iii = 1
        for i in range(len(S)):
            if S[len(S) - i - 1] != "?":
                c[i] = {(int(S[len(S) - i - 1]) * iii) % 13: 1}
                iii *= 10
                iii %= 13
                continue
            c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
            iii *= 10
            iii %= 13
        return c
    c = get_mod(S)

    def get_tdp(pdp):
        tdp = {i: 0 for i in range(13)}
        for r in v.keys():
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        for i in range(13):
            tdp[i] %= con
        return tdp

    it = iter(c.items())
    pdp = next(it)[-1]
    for k, v in it:
        pdp = get_tdp(pdp)

    ans = pdp.get(5, 0)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    ss = input()
 
    dp = [0] * 13
    dp[0] = 1
 
    mod = 10 ** 9 + 7
    mul = 1
 
    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13
 
        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod
 
        mul *= 10
        mul %= 13
        dp = next_dp
 
    print(dp[5])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
S = input()

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

c = {}
for i in range(len(S)):
    if S[len(S) - i - 1] != "?":
        continue
    tc = {i: 0 for i in range(13)}
    for j in range(0, 10):
        t = j * 10 ** i
        tc[t % 13] += 1
    c[i] = tc

dp = []
tdp = {i: 0 for i in range(13)}
tdp[SS] += 1
dp.append(tdp)
for k, v in c.items():
    tdp = {i: 0 for i in range(13)}
    for r, c in v.items():
        for _r, _v in dp[-1].items():
            tdp[(_r + r) % 13] += _v * c
    dp.append(tdp)

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

Submission status: Time Limit Exceeded

Solution code:

MOD=10**9+7
s=input()
s.rstrip()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1

coef=1
for i in range(len(s)):
    if s[i]=='?':
        for j in range(13):
            for k in range(10):
                ind=(j+coef*k)%13
                temp=dp[i+1][ind]+dp[i][j]
                dp[i+1][ind] = temp-MOD if temp>=MOD else temp
    else:
        si=int(s[i])
        for j in range(13):
            ind=(j+coef*si)%13
            temp=dp[i+1][ind]+dp[i][j]
            dp[i+1][ind] = temp-MOD if temp>=MOD else temp
    coef=coef*10%13


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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    ss = input()

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

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]

        mul *= 10
        mul %= 13
        dp = next_dp

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    ss = input()

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

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]

        mul *= 10
        dp = next_dp

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MOD = 10**9+7

dp = np.zeros((100001, 13), dtype=int)
S = input()

dp[0, 0] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding utf-8 -*-
MOD = 10 ** 9 + 7

S = input()
# S = '?' * 10000
mods = [0] * 13
mods[0] = 1

digit = 1
for s in S[::-1]:
    next_mods = [0] * 13
    if s == '?':
        for i in range(10):
            for m in range(13):
                next_mods[(m + i * digit) % 13] += mods[m]
    else:
        for m in range(13):
            next_mods[(m + int(s) * digit) % 13] += mods[m]

    for m in range(13):
        next_mods[m] %= MOD
    mods = next_mods
    digit *= 10
    digit %= 13

ans = mods[5]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = list(str(input()))
R_lst = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
len_S = len(S)
mod = 10 ** 9 + 7

for i in range(len_S - 1, -1, -1):
    R_lst.append([0 for i in range(13)])
    # when S[i] is number
    if S[i] != '?':
        S[i] = int(S[i])
        sld = S[i] * (10 ** (len_S - i - 1)) % 13
        # print(sld)
        for j in range(13):
            R_lst[-1][(j + sld) % 13] += R_lst[-2][j]
            R_lst[-1][(j + sld) % 13] %= mod
    
    # when S[i] is '?'
    else:
        for n in range(10):
            sld = n * (10 ** (len_S - i - 1)) % 13
            # print(sld)
            for j in range(13):
                R_lst[-1][(j + sld) % 13] += R_lst[-2][j]
                R_lst[-1][(j + sld) % 13] %= mod
                
# print(R_lst)
print(R_lst[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = list(str(input()))
R_lst = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
len_S = len(S)

for i in range(len_S - 1, -1, -1):
    R_lst.append([0 for i in range(13)])
    # when S[i] is number
    if S[i] != '?':
        S[i] = int(S[i])
        sld = S[i] * (10 ** (len_S - i - 1)) % 13
        # print(sld)
        for j in range(13):
            R_lst[-1][(j + sld) % 13] += R_lst[-2][j]
    
    # when S[i] is '?'
    else:
        for n in range(10):
            sld = n * (10 ** (len_S - i - 1)) % 13
            # print(sld)
            for j in range(13):
                R_lst[-1][(j + sld) % 13] += R_lst[-2][j]
                
# print(R_lst)
print(R_lst[-1][5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding utf-8 -*-
MOD = 10 ** 9 + 7

S = input()
mods = [0] * 13
mods[0] = 1

digit = 1
for s in S[::-1]:
    next_mods = [0] * 13
    if s == '?':
        for i in range(10):
            for m in range(13):
                next_mods[(m + i * digit) % 13] += mods[m]
    else:
        for m in range(13):
            next_mods[(m + int(s) * digit) % 13] += mods[m]

    for m in range(13):
        next_mods[m] %= MOD
    mods = next_mods
    digit *= 10

ans = mods[5]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) for i in range(13)]
    p = p * 10 % 13
print(a[5] % M)

Submission status: Time Limit Exceeded

Solution code:
S = list(str(input()))
R_lst = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
len_S = len(S)

for i in range(len_S - 1, -1, -1):
    R_lst.append([0 for i in range(13)])
    # when S[i] is number
    if S[i] != '?':
        S[i] = int(S[i])
        sld = S[i] * (10 ** (len_S - i - 1)) % 13
        # print(sld)
        for j in range(13):
            if j + sld <= 12:
                R_lst[-1][j + sld] += R_lst[-2][j]
            else:
                R_lst[-1][(j + sld) - 13] += R_lst[-2][j]
    
    # when S[i] is '?'
    else:
        for n in range(10):
            sld = n * (10 ** (len_S - i - 1)) % 13
            # print(sld)
            for j in range(13):
                if j + sld <= 12:
                    R_lst[-1][j + sld] += R_lst[-2][j]
                else:
                    R_lst[-1][(j + sld) - 13] += R_lst[-2][j]
                
# print(R_lst)
print(R_lst[-1][5] % (10 ** 9 + 7))

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

for i, s in enumerate(S):
	if s == "?":
		for n in range(13):
			for m in range(10):
				mod = (n * 10 + m) % 13
				dp[i + 1][mod] += dp[i][n]
				dp[i + 1][mod] %= MOD
	else:
		m = int(s)
		for n in range(13):
			mod = (n * 10 + m) % 13
			dp[i + 1][mod] += dp[i][n]
			dp[i + 1][mod] %= MOD

#for l in dp:
#	print(l)

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
s= '0'+s
dp[0][0] =1
mod = 1000000007
def factory (i,j):
    for premod in range(13):
        curMod = (premod*10+j)%13
        dp[i][curMod]+=dp[i-1][premod]
        dp[i][curMod]%=mod
for i in range(1,len(s)):
    if s[i]!='?':
        factory(i,int(s[i]))
    else:
        for num in range(10):
            factory(i,num)
print(dp[len(s)-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:

def solve():
  s = input()
  n  = len(s)
  mod = 10**9+7
  reverses = s[::-1]
  if reverses[0] != "?":
    tmp = int(reverses[0])
    query = [0 for i in range(13)]
    query[tmp] += 1
  else:
    query = [0 for i in range(13)]
    for i in range(10):
      query[i] += 1
      
  digit = 1
  tmp = [0 for i in range(13)]
  for i in range(1,n):
    digit *= 10
    digit %= 13
    tmp = [0 for i in range(13)]
    
    if reverses[i] =="?":
      for k in range(10):
        for j in range(13):
          tmp[(k*digit + j)%13] += query[j]
      
    else:
      for j in range(13):
        tmp[(digit*int(reverses[i])+j)%13] += query[j]

    for i in range(13):
      tmp[i] %= mod
    query = tmp 
      
  print(query[5])
if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  s = input()
  n  = len(s)
  mod = 10**9+7
  reverses = s[::-1]
  
  query = [0 for i in range(13)]
  if reverses[0] != "?":
    tmp = int(reverses[0])
    query = [0 for i in range(13)]
    query[tmp] += 1
  else:
    for i in range(10):
      query[i] += 1
  digit = 1
  
  for i in range(1,n):
    digit *= 10
    digit %= 13
    tmp = [0 for _ in range(13)]
    
    if reverses[i] =="?":
      for k in range(10):
        for j in range(13):
          num = k*digit
          num += j
          num %= 13
          tmp[num] += query[j]
      
    else:
      for j in range(13):
        num = digit*int(reverses[i])
        num += j
        num %= 13
        tmp[num] += query[j]

    for i in range(13):
      tmp[i] %= mod
    query = tmp 
      
  print(query[5])
solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

s = list(stdin.readline().rstrip())

dp = [0]*13
dp[0] = 1
mul = 1
mod = 10 ** 9 + 7

for i in reversed(range(0,len(s))):
    next_dp = [0]*13
    if s[i] == '?':
       for k in range(0, 10):
           for j in range(0, 13):
               next_dp[(k*mul+j)%13] += dp[j]
               next_dp[(k*mul+j)%13] %= mod

    else:
        for j in range(0, 13):
            next_dp[(int(s[i])*mul+j)%13] += dp[j]
            next_dp[(int(s[i])*mul+j)%13] %= mod

    mul *= 10
    mul %= 13
    dp = next_dp

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

mod = 1000000007
n = 13

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

mul = 1
for i in reversed(range(len(s))):
    nextDp = [0] * 13
    if s[i] == '?':
        for k in range(10):
            for j in range(n):
                nextDp[(k * mul + j) % n] += dp[j]
        for j in range(n):
            nextDp[j] %= mod
    else:
        k = int(s[i])
        for j in range(n):
            nextDp[(k * mul + j) % n] = dp[j]

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()

mod = 1000000007
n = 13

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

mul = 1
for i in reversed(range(len(s))):
    nextDp = [0] * 13
    if s[i] == '?':
        for k in range(10):
            for j in range(n):
                nextDp[(k * mul + j) % n] += dp[j]
                # nextDp[(k * mul + j) % n] %= mod
    else:
        k = int(s[i])
        for j in range(n):
            nextDp[(k * mul + j) % n] += dp[j]
            # nextDp[(k * mul + j) % n] %= mod

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()

mod = 1000000007
n = 13

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

mul = 1
for i in reversed(range(len(s))):
    nextDp = [0] * 13
    if s[i] == '?':
        for k in range(10):
            for j in range(n):
                nextDp[(k * mul + j) % n] += dp[j]
                nextDp[(k * mul + j) % n] %= mod
    else:
        k = int(s[i])
        for j in range(n):
            nextDp[(k * mul + j) % n] += dp[j]
            nextDp[(k * mul + j) % n] %= mod

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# 縦i,横j, 数字k
dp_ = [[0 for j in range(13)] for i in range(len(S)+1)]
dp_[0][0] = 1
dp = np.array(dp_, dtype=int)

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

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

Submission status: Time Limit Exceeded

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

# 縦i,横j, 数字k
dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1


for i, s in enumerate(S):
    if i == len(S):
        break
    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[-1][5] % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            i = (_r + r) % 13
            tdp[i] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)

Submission status: Time Limit Exceeded

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

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            i = (_r + r) % 13
            tdp[i] += _v
            tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)

Submission status: Time Limit Exceeded

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

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

c = {}
iii = 1
for i in range(len(S)):
    if S[len(S) - i - 1] != "?":
        iii *= 10
        iii %= 13
        continue
    tc = {}
    for j in range(0, 10):
        t = (j * iii) % 13
        tc[t] = 1
    c[i] = tc
    iii *= 10
    iii %= 13

dp = []
tdp = {i: 0 for i in range(13)}
tdp[SS] += 1
dp.append(tdp)
for k, v in c.items():
    tdp = {i: 0 for i in range(13)}
    for r, _ in v.items():
        for _r, _v in dp[-1].items():
            tdp[(_r + r) % 13] += _v
            tdp[(_r + r) % 13] %= con
    dp.append(tdp)

ans = dp[-1][5]
print(ans)