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:
# -*- coding: utf-8 -*-
import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7

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

for i,x in enumerate(S[::-1]):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[i][(x*pow(10,i,13))%13]=1
        else:
            for x in range(10):
                dp[i][(x*pow(10,i,13))%13]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                dp[i][(x*pow(10,i,13)+j)%13]+=dp[i-1][j]
        else:
            for j in range(13):
                for x in range(10):
                    dp[i][(x*pow(10,i,13)+j)%13]+=dp[i-1][j]
print dp[N-1][5]%mod

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7

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

for i,x in enumerate(S[::-1]):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[i][(x*10**i)%13]=1
        else:
            for x in range(10):
                dp[i][(x*10**i)%13]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                dp[i][(x*pow(10,i,13)+j)%13]+=dp[i-1][j]
        else:
            for j in range(13):
                for x in range(10):
                    dp[i][(x*pow(10,i,13)+j)%13]+=dp[i-1][j]
print dp[N-1][5]%mod

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7

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

for i,x in enumerate(S[::-1]):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[i][(x*10**i)%13]=1
        else:
            for x in range(10):
                dp[i][(x*10**i)%13]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                dp[i][(x*10**i+j)%13]+=dp[i-1][j]
                dp[i][(x*10**i+j)%13]%=mod
        else:
            for j in range(13):
                for x in range(10):
                    dp[i][(x*10**i+j)%13]+=dp[i-1][j]
                    dp[i][(x*10**i+j)%13]%=mod
print dp[N-1][5]%mod

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7

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

for i,x in enumerate(S[::-1]):  #i桁目
    if i==0:
        if x!="?":
            x=int(x)
            dp[i][(x*10**i)%13]=1
        else:
            for x in range(10):
                dp[i][(x*10**i)%13]=1
    else:
        if x!="?":
            x=int(x)
            for j in range(13):
                dp[i][(x*10**i+j)%13]+=dp[i-1][j]
        else:
            for j in range(13):
                for x in range(10):
                    dp[i][(x*10**i+j)%13]+=dp[i-1][j]
print dp[N-1][5]%mod

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	import sys
	readline = sys.stdin.readline

	#s = tuple(input())
	s = input().rstrip()
	n = len(s)

	dp = [[0]*13 for _ in range(n)]
	MOD = 10**9+7

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

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	import sys
	readline = sys.stdin.readline

	#s = tuple(input())
	s = input().rstrip()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

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

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
	readline = sys.stdin.readline

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

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

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

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

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7

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

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1
	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-i-1] != '?':
			num = int(s[-i-1])
			for j in range(13):
				dp[i][(a*num+j)%13] += dp[i-1][j]
				dp[i][(a*num+j)%13] %= MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k]
					dp[i][k] %= MOD
				#a += num

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1
	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-i-1] != '?':
			num = int(s[-i-1])
			for j in range(13):
				dp[i][(a*num+j)%13] = dp[i-1][j]
				dp[i][(a*num+j)%13] %= MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k]
					dp[i][k] %= MOD
				#a += num

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():

	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

dp = [[0 for _ in range(13)]for _ in range(len(s)+1)]
MOD = 10**9+7
if s[-1] == '?':
	for i in range(10):
		dp[1][i] = 1
else:
	dp[1][int(s[-1])] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():

	s = list(input())

	dp = [[0 for _ in range(13)]for _ in range(len(s)+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

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

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

dp = [[0 for _ in range(13)]for _ in range(len(s)+1)]
MOD = 10**9+7
if s[-1] == '?':
	for i in range(10):
		dp[1][i] = 1
else:
	dp[1][int(s[-1])] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

mod = [[0] * 10 for _ in range(13)]
for i in range(13):
	for j in range(10):
		mod[i][j] = (10 * i + j) % 13

dp = [[0] * 13 for _ in S]
for i in range(len(S)):
	if i == 0:
		if S[0] == '?':
			for j in range(10):
				dp[0][j] = 1
		else:
			dp[0][int(S[0])] = 1
	else:
		if S[i] == '?':
			for j in range(10):
				for k in range(13):
					dp[i][mod[k][j]] += dp[i - 1][k]
		else:
			x = int(S[i])
			for j in range(13):
				dp[i][mod[j][x]] = dp[i - 1][j]

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = ''.join(reversed(input().strip()))

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
list10 = list(range(10))
list13 = list(range(13))
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for i in range(len(S)):
    s = S[i]
    if s == '?':
        for d in list10:
            m = mod13_list[(d * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in list13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for j in list13:
        dp_[j] = dp[j] % divisor
        dp[j] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = ''.join(reversed(input().strip()))

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
list10 = list(range(10))
list13 = list(range(13))
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in list10:
            m = mod13_list[(d * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in list13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in list13:
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = reversed(input().strip())

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
list10 = list(range(10))
list13 = list(range(13))
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in list10:
            m = mod13_list[(d * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in list13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in list13:
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = reversed(input().strip())

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
range10 = range(10)
range13 = range(13)
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in range10:
            m = mod13_list[(d * mul)]
            for pm in range13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in range13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range13:
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = reversed(input().strip())

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = list(reversed(input().strip()))
N = len(S)

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5] % divisor)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in reversed(input().strip())]
N = len(S)

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for i, s in enumerate(S, start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        m = mod13_list[(s * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5] % divisor)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        m = mod13_list[(s * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5] % divisor)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        m = mod13_list[(s * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]
    dp_ = dp % divisor
    dp = dp * 0 # np.zeros((13), dtype=int)
    mul = mod13_list[(mul * 10)]
print(dp_[5] % divisor)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mod)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        m = mod13_list[(s * mod)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]
    dp_ = dp % divisor
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = mod13_list[(mod * 10)]
print(dp_[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mod)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = mod13_list[(s * mod)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp % divisor
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = mod13_list[(mod * 10)]
print(dp_[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
# divisor = 10 ** 9 + 7
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mod)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = mod13_list[(s * mod)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp % (10 ** 9 + 7)
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = mod13_list[(mod * 10)]
print(dp_[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mod)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = mod13_list[(s * mod)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = mod13_list[(mod * 10)]
print(dp_[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[(pm+m)%13] = (dp[(pm+m)%13] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = (s * mod) % 13
        for pm in range(13):
            dp[(pm+m)%13] = (dp[(pm+m)%13] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = (mod * 10) % 13
print(dp_[5] % (10 ** 9 + 7))