Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

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

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

??2??5

Sample Output 1

768

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

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

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

Sample Input 4

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

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
S = input()

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
    dp.append(tdp)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    S=input()
    MOD=10**9+7
    dp=[0]*13
    dp[0]=1
    r=1
    for i in range(len(S)):
        new_dp=[0]*13
        s=S[-1-i]
        if s=="?":
            for j in range(10):
                rem=(j*r)%13
                for k in range(13):
                    new_dp[(k+rem)%13]+=dp[k]
        else:
            rem=(int(s)*r)%13
            for k in range(13):
                new_dp[(k+rem)%13]+=dp[k]
        for l in range(13):
            new_dp[l]%=MOD
        dp=new_dp
        r=(r*10)%13
    print(dp[5])
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S=input()
    MOD=10**9+7
    dp=[[0]*13 for _ in range(1+len(S))]
    dp[0][0]=1
    r=1
    for i in range(len(S)):
        s=S[-1-i]
        if s=="?":
            for j in range(10):
                rem=(j*r)%13
                for k in range(13):
                    dp[i+1][(k+rem)%13]+=dp[0][k]
        else:
            rem=(int(s)*r)%13
            for k in range(13):
                dp[i+1][(k+rem)%13]+=dp[0][k]
        for l in range(13):
            dp[i+1][l]%=MOD
        dp[0]=dp[i+1]
        r=(r*10)%13
    print(dp[len(S)][5])
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S=input()
    MOD=10**9+7
    dp={0:1,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
    for i in range(len(S)):
        new_dp={0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
        s=S[-1-i]
        if s=="?":
            for j in range(10):
                rem=(j*10**i)%13
                for k in range(13):
                    new_dp[(k+rem)%13]+=dp[k]
        else:
            rem=(int(s)*10**i)%13
            for k in range(13):
                new_dp[(k+rem)%13]+=dp[k]
        for l in range(13):
            new_dp[l]%=MOD
        dp=new_dp
    print(dp[5])
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007;
 
s = input()
 
n=len(s)
 
if n<1 or n>10**5:
	print ('Illegal')
	exit()
b=[0]*13
#pr=[0]*13

p=1

for i in range(n):
	ix=n-1-i
	if(s[ix]=="?"):
		c=-1
	else:
		c=int(s[ix])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[(p*j)%13]=1
		else:
			b[(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[(k+p*j)%13]+=pr[k]
		else:
			for k in range(13):
				b[(k+p*c)%13]+=pr[k]
 
	if (i%30==0 or i==n-1):
		for k in range(13):b[k]%=MOD
	p=p*10%13
	pr=b
	b=[0]*13
#	print (pr)
#	for k in range(13):
#		pr[k]=b[k]
#		b[k]=0
#	print (pr)
print (pr[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007;
 
s = input()
 
n=len(s)
 
if n<1 or n>10**5:
	print ('Illegal')
	exit()
b=[0]*13
pr=[0]*13

p=1

for i in range(n):
	ix=n-1-i
	if(s[ix]=="?"):
		c=-1
	else:
		c=int(s[ix])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[(p*j)%13]=1
		else:
			b[(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[(k+p*j)%13]+=pr[k]
		else:
			for k in range(13):
				b[(k+p*c)%13]+=pr[k]
 
	if (i%30==0 or i==n-1):
		for k in range(13):b[k]%=MOD
	p=p*10%13
#	print (pr)
	for k in range(13):
		pr[k]=b[k]
		b[k]=0
#	print (pr)
print (pr[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
#b=np.zeros((n+1, 13), dtype = 'int64')
#p=np.zeros(n,dtype=int)

b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


p=1
#for i in reversed(range(n)):
#	p[i]=x%13
#	x=p[i]*10
	
for i in range(n):
	ix=n-1-i
	if(s[ix]=="?"):
		c=-1
	else:
		c=int(s[ix])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p*j)%13]=1
		else:
			b[0][(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p*c)%13]+=b[i-1][k]

	if (i%30==0 or i==n-1):
		for k in range(13):b[i][k]%=MOD
	p=p*10%13
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
#b=np.zeros((n+1, 13), dtype = 'int64')
#p=np.zeros(n,dtype=int)

b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


p=1
#for i in reversed(range(n)):
#	p[i]=x%13
#	x=p[i]*10
	
for i in range(n):
	ix=n-1-i
	if(s[ix]=="?"):
		c=-1
	else:
		c=int(s[ix])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p*j)%13]=1
		else:
			b[0][(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
	p=p*10%13
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

MOD = 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

Solution code:

MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
#b=np.zeros((n+1, 13), dtype = 'int64')
#p=np.zeros(n,dtype=int)

b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


x=1
#for i in reversed(range(n)):
#	p[i]=x%13
#	x=p[i]*10
	
for i in range(n):
	p=(10**(n-1-i))%13
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p*j)%13]=1
		else:
			b[0][(p*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
b=np.zeros((n+1, 13), dtype = 'int64')
p=np.zeros(n,dtype=int)
#b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


x=1
for i in reversed(range(n)):
	p[i]=x%13
	x=p[i]*10
	
for i in range(n):
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p[i]*j)%13]=1
		else:
			b[0][(p[i]*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p[i]*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p[i]*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                # dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            # dp[i + 1][(mul * k + j) % 13] %= INF
    mul *= 10

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
b=np.zeros((n+1, 13), dtype = 'int64')
p=np.zeros(n,dtype=int)

b.shape
p.shape


x=1
for i in reversed(range(n)):
	p[i]=x%13
	x=p[i]*10
	
for i in range(n):
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p[i]*j)%13]=1
		else:
			b[0][(p[i]*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p[i]*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p[i]*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul *= 10

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()


#a=[-1]*len(s)
b=[[0 for i in range(13)] for j in range(n+1)]
p=[0]*n

x=1
for i in reversed(range(n)):
	p[i]=x%13
	x=p[i]*10
	
for i in range(n):
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p[i]*j)%13]=1
		else:
			b[0][(p[i]*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p[i]*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p[i]*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

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

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

    for i in range(1,n):
        a = len(s) - i
        if s[a-1] == '?':
            for j in range(13):
                for k in range(10):
                    b = (k * 10 ** i + j) % 13
                    dp[i][b] += dp[i-1][j]
        else:
            k = int(s[a-1])
            for j in range(13):
                b = (k * 10 ** i + j) % 13
                dp[i][b] += dp[i-1][j]
        for j in range(13):
            dp[i][j] %= mod

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in list10:
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      r = 0
      for j in list10:
        np[(0 + r) % 13] += p[0]
        np[(1 + r) % 13] += p[1]
        np[(2 + r) % 13] += p[2]
        np[(3 + r) % 13] += p[3]
        np[(4 + r) % 13] += p[4]
        np[(5 + r) % 13] += p[5]
        np[(6 + r) % 13] += p[6]
        np[(7 + r) % 13] += p[7]
        np[(8 + r) % 13] += p[8]
        np[(9 + r) % 13] += p[9]
        np[(10 + r) % 13] += p[10]
        np[(11 + r) % 13] += p[11]
        np[(12 + r) % 13] += p[12]
        r += multiplier
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in list10:
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[(k + r) % 13] += p[k]
        r += multiplier
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in list10:
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      for j in list10:
        r = multiplier * j
        for k in list13:
          np[(k + r) % 13] += p[k]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

Submission status: Time Limit Exceeded

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

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

for i in range(1,n):
    a = len(s) - i
    if s[a-1] == '?':
        for j in range(13):
            for k in range(10):
                b = (k * 10 ** i + j) % 13
                dp[i][b] += dp[i-1][j]
    else:
        k = int(s[a-1])
        for j in range(13):
            b = (k * 10 ** i + j) % 13
            dp[i][b] += dp[i-1][j]
    for j in range(13):
        dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
"""解説
dp

dp[i][j] := 先頭i文字として考えられるもののうち、13で割ったあまりがjであるものの数

1?2?3 を分解すると、
10000 ≡ 3
 A000 ≡ A*(10**3) % MOD ≡ A*12
  200 ≡ 5
   B0 ≡ B*(10**1) % MOD
    3 ≡ 3
    -----
        11 + ? ≡ 11 + A*12 + B*10

"""


def solve():
    S = input()
    MOD = 10**9+7

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

    for i in range(0, N):
        if S[i] == "?":
            c = -1
        else:
            c = int(S[i])
        
        for j in range(0, 10):
            if c != -1 and c != j: continue
            
            for ki in range(0, 13):
                dp[i+1][(ki* 10 + j)%13] += dp[i][ki]
        
        for j in range(0, 13):
            dp[i+1][j] %= MOD

    res = dp[N][5]
    print(res)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  p = [0 for i in range(13)]
  np = [0 for i in range(13)]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in range(10):
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in range(13):
        np[(j + r) % 13] = p[j]
    else:
      for j in range(10):
        r = multiplier * j
        for k in range(13):
          np[(k + r) % 13] += p[k]
    for j in range(13):
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

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)}
    iii = 10 ** i
    for j in range(0, 10):
        t = j * iii
        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, _ in v.items():
        if _ > 0:
            for _r, _v in dp[-1].items():
                tdp[(_r + r) % 13] += _v
    dp.append(tdp)

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

Submission status: Time Limit Exceeded

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

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

for i in range(1,n):
    a = len(s) - i
    if s[a-1] == '?':
        for j in range(13):
            for k in range(10):
                b = (k * 10 ** i + j) % 13
                dp[i][b] += dp[i-1][j]
                dp[i][b] %= mod
    else:
        k = int(s[a-1])
        for j in range(13):
            b = (k * 10 ** i + j) % 13
            dp[i][b] += dp[i-1][j]
            dp[i][b] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007;

s = input()

if len(s)<1 or len(s)>10**5:
	print ('Illegal')
	exit()

n=len(s)

#a=[-1]*len(s)
b=[[0 for i in range(13)] for j in range(n+1)]
p=[0]*n

x=1
for i in reversed(range(n)):
	p[i]=x%13
	x=p[i]*10
	
for i in range(n):
	if(s[i]=="?"):
		c=-1
	elif(s[i]>="0" and s[i]<="9"):
		c=int(s[i])
	else:
		print (a[i]+"   Illegal")
		exit()
	if ( i== 0):
		for j in range(10):
			if (c!=-1 and c!=j): continue
			b[0][(p[i]*j)%13]=1
	else:
		for j in range(10):
			if (c!=-1 and c!=j): continue
			y=(p[i]*j)%13
			for k in range(13):
				b[i][(k+y)%13]+=b[i-1][k]


	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

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

Submission status: Time Limit Exceeded

Solution code:
s = ''.join(reversed(raw_input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
np = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  for j in range(13):
    np[j] = 0
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print p[5] % divisor

Submission status: Time Limit Exceeded

Solution code:
S = input()

MOD=(10**9) + 7
N=13

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

dpi = 1
mul = 1
for c in S[::-1]:    
    for i in range(N):
        if c=='?':
            for j in range(10):
                ii = (i + (int(j)*mul)) % N
                dp[dpi][ii] += dp[dpi-1][i] % MOD
        else:
            ii = (i + (int(c)*mul)) % N
            dp[dpi][ii] += dp[dpi-1][i] % MOD
    mul *= 10
    dpi += 1

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

Submission status: Time Limit Exceeded

Solution code:
s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
np = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  for j in range(13):
    np[j] = 0
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)

Submission status: Time Limit Exceeded

Solution code:


s = input()


def main():
#    s = ['0' for _ in range(10**5)]
#   TLE check py3 だとちょっと遅いかもしれない？
    n = len(s)
    mod = 10**9 + 7

    dp = [[0]* 13 for _ in range(n+1)]
    dp[0][0] = 1

    #print(len(dp),len(dp[0]))

    # i : 桁数
    # j : 13で割った余り
    # k : ? をkと仮定
    # dp[i][j] : i+1 桁目 までの数字を13で割ったとき、余りがjになる数の個数
    for i in range(n):
        if s[i] != '?':

            c = int(s[i]) - int('0')
            for j in range(13):
                i_ = i+1
                j_ = (j*10+c); j_%=13
                dp[i_][j_] += dp[i][j]
                dp[i_][j_] %= mod
        else: 
            for j in range(13):
                for k in range(10):
                    i_ = i+1
                    j_ = j*10+k ; j_ %= 13
                    dp[i_][j_] += dp[i][j]
                    dp[i_][j_] %= mod

        # print(i,j,dp[i+1])
    print(dp[-1][5])      
     
main()

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 ind,s in enumerate(S):
    if(s=='?'):
        for i in range(10):
            for j in range(13):
                dp[ind+1][(j*10+i)%13] += dp[ind][j]
                dp[ind+1][(j*10+i)%13] %= mod
    else:
        for j in range(13):
            dp[ind+1][(j*10+int(s))%13] += dp[ind][j]
            dp[ind+1][(j*10+int(s))%13] %= mod
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

MOD=(10**9) + 7
N=13

dp=[0]*N
dp[0] = 1

mul = 1
for c in S[::-1]:
    next_dp=[0]*N
    
    for i in range(N):
        if c=='?':
            for j in range(10):
                ii = (i + (int(j)*mul)) % N
                next_dp[ii] += dp[i]
                next_dp[ii] = next_dp[ii] % MOD
        else:
            ii = (i + (int(c)*mul)) % N
            next_dp[ii] += dp[i]
            next_dp[ii] = next_dp[ii] % MOD

    mul *= 10
    dp = next_dp

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = input()
dp = np.zeros((10**5+5,13))
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 ki in range(13):
      dp[(i+1,(ki*10 + j) % 13)] += dp[(i, ki)]
      
  for j in range(13):
    dp[(i+1,j)] = dp[(i+1,j)] % (10**9 + 7)
      
print(int(dp[(len(S), 5)]))

Submission status: Time Limit Exceeded

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

n = len(s)
dp = [1] + [0] * 12
mod = 10**9 + 7
mlist = [(10**i)%13 for i in range(6)]

for i in range(n):
    m = mlist[i%6]
    if s[i] == "?":
        dp = [sum([dp[(j-m*k)%13] for k in range(10)]) % mod for j in range(13)]
    else:
        num = (int(s[i])*m)%13
        dp = [dp[(j-num)%13] for j in range(13)]
            
print(dp[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    c = -1 if S[i] == '?' else 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

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
l = len(s)
mod = (10**9)+7

dp = np.zeros((l,13), dtype=np.int64)

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

dp_memo = dp[0]

for i in range(l-1):
    a = i+1
    x = s[a]
    if x == '?':
        for j in range(10):
            for k in range(13):
                dp[a][(k*10+j)%13] += dp_memo[k]%mod
    else:
        for k in range(13):
            dp[a][(k*10+int(x))%13] += dp_memo[k]%mod
    dp_memo = dp[a]

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

S = input()

# 末尾から各あまりについてDP
M = 13
MOD = 10**9 + 7
ans = reduce(
    lambda acc, c: (
        [
            sum(
                acc[0][(i - acc[1] * j) % M]
                for j in range(10)
            ) % MOD
            for i in range(M)
        ] if c == '?' else
        [
            acc[0][(i - acc[1] * int(c)) % M]
            for i in range(M)
        ],
        (10 * acc[1]) % M
    ),
    S[::-1],
    (
        [
            1 if i == 0 else
            0
            for i in range(M)
        ],
        1
    )
)[0][5]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
l = len(s)
mod = (10**9)+7

dp = np.zeros((l,13), dtype=np.int64)

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

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

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

Submission status: Time Limit Exceeded

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

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

n = len(s)
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
mod = 10**9 + 7
mlist = [(10**i)%13 for i in range(6)]

for i in range(n):
    m = mlist[i%6]
    if s[n-i-1] == "?":
        for j in range(13):
            tmp = [dp[i][(j-m*k)%13] for k in range(10)]
            dp[i+1][j] = sum(tmp) % mod
    else:
        num = (int(s[n-i-1])*m)%13
        for j in range(13):
            dp[i+1][j] = dp[i][(j-num)%13]
            
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
mod = (10**9)+7

dp = [[0 for j in range(13)] for i in range(l)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

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

for i in range(n):
    m = (10**i) % 13
    if s[n-i-1] == "?":
        for j in range(13):
            tmp = [dp[i][(j-m*k)%13] for k in range(10)]
            dp[i+1][j] = sum(tmp) % mod
    else:
        num = (int(s[n-i-1])*(10**i))%13
        for j in range(13):
            dp[i+1][j] = dp[i][(j-num)%13] % mod
            
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
mod = (10**9)+7

dp = [[0 for j in range(13)] for i in range(l)]

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

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

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