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()[::-1]
mod = 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
#%%time
mod=10**9+7
s=input()
#s="?"*10**5


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:

    #print(i+num+1)
    if v=="?":
        t_d=keep.copy()
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])

Submission status: Time Limit Exceeded

Solution code:
s = [i for i 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):
	return a*data[i]%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

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

Submission status: Time Limit Exceeded

Solution code:
s = [i for i in input()]
n =len(s)
A=13
data=[10**(n-(i+1))%A for i in range(n)]

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

def benri(a,i):
	return a*data[i]%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

			
			

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

Submission status: Time Limit Exceeded

Solution code:
s = [i for i in input()]
n =len(s)
A=13

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

def benri(a,i):
	return a*10**(n-(i+1))%A


for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

			
			

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

Submission status: Time Limit Exceeded

Solution code:
s = [i for i in input()]
n =len(s)
A=13

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

for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-int(s[i])*10**(len(s)-(i+1))%13>=0:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13]
			else:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13+13]

		else:
			for c in range(10):
				if j-c*10**(len(s)-(i+1))%13>=0:
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13+13]

			
			

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
# from numba import njit

MOD = 1000000007


# @njit
def solve(x, y, f):
    digit = 0
    for n in range(S.shape[0]):
        k = n % 6
        if S[n] == 15:
            s = 0
            for i in range(13):
                s += x[i]
            for i in range(13):
                g = f[k, i]
                y[i] = (s - x[g[0]] - x[g[1]] - x[g[2]]) % MOD
            x, y = y, x
        else:
            digit += a[k] * S[n]
    return (5 - digit) % 13, x


# @njit
def set_dp(f, c):
    for k in range(6):
        x = np.zeros(13, dtype=np.uint64)
        for m in range(c.shape[1]):
            x[c[k, m]] = 1
        count = 0
        for m in range(13):
            if x[m] == 0:
                f[k, 0, count] = m
                count += 1
        for i in range(12):
            for j in range(3):
                f[k, i + 1, j] = f[k, i, j] + 1


S = np.frombuffer(sys.stdin.buffer.read(), dtype=np.int8)
S = S[:-1][::-1] - 48

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10), (6, 1))
c = (-a * b.T % 13).T
f = np.empty((6, 13, 3), dtype=np.uint64)
set_dp(f, c)
f %= 13
dp = np.zeros(13, dtype=np.int64)
dp[0] = 1
nex = np.zeros(13, dtype=np.int64)
m, dp = solve(dp, nex, f)
print(dp[m])

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

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

print(ans[length][5])

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)
#print(tblpow)
#1 10 9 12 3 4

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1])

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*10**i+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=1024)
    def get_c(iii):
        return [mm13[iii][j] for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    mm13 = {i: {j: (i * j) % 13 for j in range(11)} for i in range(1000)}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([mm13[iii][int(s)]])
        else:
            c.append(get_c(iii))
        iii = mm13[iii][10]

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=1024)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 10**9+7
dp = [0] * 13
next_dp = [0] * 13
amari = [0] * 13
dp[0] = 1
for i,s in enumerate(S):
    digit = len(S)-i-1
    if s == '?':
        for j in range(10):
            d = (10**digit*j)%13
            amari[d] += 1
    else:
        j = int(s)
        d = (10**digit*j)%13
        amari[d] += 1
    # print(amari)
    for k in range(13):
        for l in range(13):
            next_dp[(k+l)%13] += dp[k]*amari[l]
            next_dp[(k+l)%13]%=mod
    dp = next_dp
    next_dp = [0] * 13
    amari = [0] * 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(10**5+10)

mod = 10**9+7

S = input()
S = S[::-1]
#print(S)

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@lru_cache(maxsize=None)
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res%mod

print(search(0,0))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=128, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

    @lru_cache(maxsize=128, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 5
        pdp = tdp

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

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Time Limit Exceeded

Solution code:
N = input()
digit = len(N)
mod = 1000000007

# dp[i番目まで][未満かどうか][mod13]
dp = [[[0]*13 for _ in range(2)] for _ in range(digit+2)]
dp[0][0][0] = 1

for i in range(digit-1,-1,-1):
  ii = digit-i-1
  d = 10**(ii)
  for j in range(2):
    for k in range(13):
      if N[i] == "?":
        for n in range(9+1):
          dp[ii+1][j][(k + n*d)%13] += dp[ii][j][k] %mod
      else:
        n = int(N[i])
        dp[ii+1][j][(k + n*d)%13] += dp[ii][j][k] %mod

print((dp[digit][0][5] + dp[digit][1][5]) %mod)

Submission status: Time Limit Exceeded

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

    ns = list(range(10))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
            iii = (iii * 10) % 13
            continue
        c.append([(j * iii) % 13 for j in ns])
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in range(13)}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 0
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in range(13):
                tdp[i] %= con
        d = (d + 1) % 50
        pdp = tdp

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()[::-1]
mod = 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()
mod = 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = input()
mod = 1000000007

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(S):
    mod = 10**9 + 7
    t = [0] * 13
    t[0] = 1
    m = 1
    for c in reversed(S):
        nt = [0] * 13
        if c != '?':
            n = (m * int(c)) % 13
            for k in range(13):
                nt[(k+n) % 13] = t[k]
        else:
            for j in range(10):
                n = (m * j) % 13
                for k in range(13):
                    l = (k+n) % 13
                    nt[l] = (nt[l] + t[k]) % mod
        t = nt
        m *= 10
        m %= 13
    return t[5]


def main():
    S = read_str()
    # S = '?' * (10**5)
    print(slv(S))


if __name__ == '__main__':
    main()

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

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

Submission status: Time Limit Exceeded

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

dp[0][0] = 1
for i in range(0,len):
    ch = test[i]
    for r in range(0,13):
        if ch != '?':
            dp[i + 1][(r*10 + int(ch)) % 13] += dp[i][r]
        else:
            for j in range(0,10):
                dp[i + 1][(r*10 + j) % 13] += dp[i][r]
                
    for j in range(0,10):
        dp[i + 1][j] %= MOD


print(dp[len][5])

Submission status: Time Limit Exceeded

Solution code:
test = input()
len = len(test)
dp = []
MOD = 10**9 + 7
for i in range(0,len+1):
    dp.append([])
    for r in range(0,13):
        dp[i].append(0)

dp[0][0] = 1
for i in range(0,len):
    ch = test[i]
    for r in range(0,13):
        if ch != '?':
            dp[i + 1][(r*10 + int(test[i])) % 13] += dp[i][r]
        else:
            for j in range(0,10):
                dp[i + 1][(r*10 + j) % 13] += dp[i][r]
    for j in range(0,10):
        dp[i+1][j] %= MOD
print(dp[len][5])

Submission status: Time Limit Exceeded

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

dp = [1] + [0] * 12
new_dp = [0] * 13

res = [[x * 10 ** i % 13 for x in range(10)] for i in range(6)]
mod = 10 ** 9 + 7

for idx, char in enumerate(s):
    new_dp = [0] * 13
    if char != "?":
        for i in range(13):
            new_i = (i + res[idx % 6][int(char)]) % 13
            new_dp[new_i] += dp[i]
        dp = new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i = (i + res[idx % 6][j]) % 13
                new_dp[new_i] += dp[i]
        dp = [x % mod for x in new_dp]

print(dp[5])

Submission status: Time Limit Exceeded

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

case = [1] + [0] * 12
temp = [0] * 13
unit = 1
before = 0
for i in reversed(range(len(S))):
    if(S[i] == '?'):
        for k in range(13):
            for j in range(10):
                before = (k - unit * j) % 13
                temp[k] += case[before]
            temp[k] %= M
    else:
        for k in range(13):
            before = (k - unit * int(S[i])) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13
    temp = [0] * 13

print(case[5])

Submission status: Time Limit Exceeded

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

case = [0] * 13
case[0] = 1
unit = 1
for i in reversed(range(N)):
    temp = [0] * 13
    if(S[i] == '?'):
        for j in range(10):
            increase = unit * j % 13
            for k in range(13):
                before = (k - increase) % 13
                temp[k] += case[before]
                temp[k] %= M
    else:
        num = int(S[i])
        increase = unit * num % 13
        for k in range(13):
            before = (k - increase) % 13
            temp[k] = case[before]
    case = temp
    unit *= 10
    unit %= 13

print(case[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), 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] * (n // 6 + 1)
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x, l_ in zip(S[-2::-1], dp[1:], l[1:]):
    if s == "?":
        x += x_
        for v in l_:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            v = l_[int(s) - 1]
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    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)
a = S[-1]
x = np.zeros(13, int)
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 in S[-2::-1]:
    x_ = np.zeros(13, int)
    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
    if li == 5:
        li = 0
    else:
        li += 1
    x = x_
print(x[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), 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
    if li == 5:
        li = 0
    else:
        li += 1
    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), 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 i in range(1, n):
    x = dp[i]
    s = S[-i - 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), 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 %= 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(dp[-1][5])