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()[::-1]
 
dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0]=1

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):

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
#S = "?" * 100000
S = S[::-1]
N = 13
mod = 10 ** 9 + 7
dp = [0] * 26
dp[13] = 1
digit = 1
for c in range(len(S)):
    dp[:13] = [0] * N
    if S[c] == '?':
        for k in range(10):
            for j in range(N):
                dp[(k * digit + j) % N] += dp[j + 13]
                dp[(k * digit + j) % N] %= mod
    else:
        k = int(S[c])
        for j in range(N):
            #index = (k * digit + j) % N
            dp[(k * digit + j) % N] += dp[j + 13]
            dp[(k * digit + j) % N] %= mod

    digit *= 10
    digit %= N
    #print(dp)
    dp[13:26] = dp[:13]
    #print(dp)
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
#S = "?" * 100000
S = S[::-1]
N = 13
mod = 10 ** 9 + 7
dp = [0] * 26
dp[13] = 1
digit = 1
for c in S:
    dp[:13] = [0] * N
    if c == '?':
        for k in range(10):
            for j in range(N):
                dp[(k * digit + j) % N] += dp[j + 13]
                dp[(k * digit + j) % N] %= mod
    else:
        k = int(c)
        for j in range(N):
            #index = (k * digit + j) % N
            dp[(k * digit + j) % N] += dp[j + 13]
            dp[(k * digit + j) % N] %= mod

    digit *= 10
    digit %= N
    #print(dp)
    dp[13:26] = dp[:13]
    #print(dp)
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
N = 13
mod = 10 ** 9 + 7
dp = [0] * N
dp[0] = 1
digit = 1
for c in S:
    nextDP = [0] * N
    if c == '?':
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += dp[j]
                nextDP[(k * digit + j) % N] %= mod
    else:
        k = int(c)
        for j in range(N):
            index = (k * digit + j) % N
            nextDP[(k * digit + j) % N] += dp[j]
            nextDP[(k * digit + j) % N] %= mod

    digit *= 10
    digit %= N
    dp = nextDP
    #print(nextDP)
print(dp[5])

Submission status: Time Limit Exceeded

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

dp=[[0]*13 for _ in range(len(S)+1)]
#dp[i][j] :先頭 i 文字として考えられるもののうち、13 で割ったあまりが j であるものの数
dp[0][0]=1

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

for i in range(1,len(S)+1):
  if S[i-1]=="?":
    for k in range(10):
      for j in range(13):
        dp[i][memo[j][k]]+=dp[i-1][j]
        dp[i][memo[j][k]]%=mod        
  else:
    for j in range(13):
      dp[i][memo[j][int(S[i-1])]]+=dp[i-1][j]
      dp[i][memo[j][int(S[i-1])]]%=mod
      
print(dp[len(S)][5]%mod)

Submission status: Time Limit Exceeded

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

dp=[[0]*13 for _ in range(len(S)+1)]
#dp[i][j] :先頭 i 文字として考えられるもののうち、13 で割ったあまりが j であるものの数
dp[0][0]=1

for i in range(1,len(S)+1):
  if S[i-1]=="?":
    for k in range(10):
      for j in range(13):
        dp[i][(10*j+k)%13]+=dp[i-1][j]
        dp[i][(10*j+k)%13]%=mod
        
  else:
    for j in range(13):
      dp[i][(10*j+int(S[i-1]))%13]+=dp[i-1][j]
      dp[i][(10*j+int(S[i-1]))%13]%=mod
      
print(dp[len(S)][5]%mod)

Submission status: Time Limit Exceeded

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

dp=[[0]*13 for _ in range(len(S)+1)]
#dp[i][j] :先頭 i 文字として考えられるもののうち、13 で割ったあまりが j であるものの数
dp[0][0]=1

for i in range(1,len(S)+1):
  if S[i-1]=="?":
    for k in range(10):
      for j in range(13):
        dp[i][(10*j+k)%13]+=dp[i-1][j]
    
    
  else:
    for j in range(13):
      dp[i][(10*j+int(S[i-1]))%13]+=dp[i-1][j]
      
print(dp[len(S)][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*(10**(i))%13)%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*(10**(i))%13)%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*(10**(i))%13)%13] += dp[i][k]
                    dp[i+1][(k+l*(10**(i))%13)%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[-1] == '?':
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(S[-1])] += 1
    for i in range(N-1):
        for k in range(13):
            if S[-(i+2)] != '?':
                dp[i+1][(k+int(S[-(i+2)])*(10**(i+1))%13)%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+2)])*(10**(i+1))%13)%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*(10**(i+1))%13)%13] += dp[i][k]
                    dp[i+1][(k+l*(10**(i+1))%13)%13] %= MOD
    print(dp[-1][5])





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    s_1 = [1]
    for n in range(1,N):
        s_1.append((s_1[n-1] * 10)%13)
    for i in range(1,N):
        if S[-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j] + dp[i-1][(j-(k*s_1[i])%13)%13]) % MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] = (dp[i][l] + dp[i-1][(l-m)%13]) % MOD
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j] + dp[i-1][(j-(k*10**i)%13)%13]) % MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] = (dp[i][l] + dp[i-1][(l-m)%13]) % MOD
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j] + dp[i-1][(j-(k*10**i)%13)%13]) % MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = list(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j]%MOD + dp[i-1][(j-(k*10**i)%13)%13]%MOD)%MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = list(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] += dp[i-1][(j-(k*10**i)%13)%13]%MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 7 + 10**9
    S = list(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                dp[i][j] += sum([dp[i-1][(j-(k*10**i)%13)%13]%MOD for k in range(10)])
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
dp=[[0 for _ in range(13)] for _ in range(len(S))]
MOD=10**9+7
if S[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[0])]+=1
for i in range(1, len(S)):
  cur_nums=[i for i in range(10)] if S[i]=='?' else [int(S[i])]
  for cur in cur_nums:
    for rem in range(13):
      dp[i][(10*rem+cur)%13]=(dp[i][(10*rem+cur)%13]+dp[i-1][rem])%MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = list(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                dp[i][j] += sum([dp[i-1][(j-(k*10**i)%13)%13] for k in range(10)])
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%(7+10**9))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
M = [[0 for _ in range(13)] for _ in range(6)]
for i in range(6):
  for j in range(10):
    M[i][j] = j * 10 ** i % 13
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = M[i % 6][j]
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = M[i % 6][int(s)]
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = j * 10 ** i % 13
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = int(s) * 10 ** i % 13
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
  #print(DP[i])
#print(DP[-1])
print(DP[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = j * 10 ** i % 13
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = int(s) * 10 ** i % 13
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] = 1
keta = 1

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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+1)]
dp[0][0]=1

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

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

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(13)] for j in range(l+1)]
dp[0][0] = 1
#dp[i][j]=i桁目までを13で割った時、
#そのあまりがjになる場合の数

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

Submission status: Time Limit Exceeded

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

dp = [0 for i in range(13)]
dp2 = [0 for i in range(13)]
dp[0] = 1

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)
	dp2 = dp.copy()
	if num == '?':
		for j in range(1,10):
			tmp = ( j * keta ) % 13
			for k in range(13):
				dp[(tmp + k) % 13] += dp2[k] % mod
	else:
		tmp = ( int(num) * keta ) % 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[index] = dp2[k] % mod
print(dp[5] % mod)

Submission status: Time Limit Exceeded

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

dp = [0 for i in range(13)]
dp2 = [0 for i in range(13)]
dp[0] = 1

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)
	dp2 = dp.copy()
	if num == '?':
		for j in range(1,10):
			tmp = ( j * keta ) % 13
			for k in range(13):
				index = (tmp + k) % 13
				dp[index] += dp2[k]
	else:
		tmp = ( int(num) * keta ) % 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[index] = dp2[k]
print(dp[5] % mod)

Submission status: Time Limit Exceeded

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

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

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)
	if num == '?':
		for j in range(10):
			tmp = ( int(j) * keta ) % 13
			for k in range(13):
				index = (tmp + k) % 13
				dp[i][index] += dp[i-1][k]
				dp[i][index] %= mod
	else:
		tmp = ( int(num) * keta ) % 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[i][index] += dp[i-1][k]
			dp[i][index] %= mod
print(dp[l][5] % mod)

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s)

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

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)
	if num == '?':
		for j in range(10):
			tmp = ( int(j) * keta ) % 13
			for k in range(13):
				index = (tmp + k) % 13
				dp[i][index] += dp[i-1][k]
	else:
		tmp = ( int(num) * keta ) % 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[i][index] += dp[i-1][k]
print(dp[l][5] % (pow(10,9)+7))

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s)

dp = [[0 for i in range(13)] for j in range(l+1)]
dp[0][0] = 1
#dp[i][j]=i桁目までを13で割った時、
#そのあまりがjになる場合の数

for i in range(1,l+1):
	num = s[-i]
	if num == '?':
		for j in range(10):
			tmp = int(j) * pow(10,i-1)
			tmp %= 13
			for k in range(13):
				index = (tmp + k) % 13
				dp[i][index] += dp[i-1][k]
	else:
		tmp = int(num) * pow(10,i-1)
		tmp %= 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[i][index] += dp[i-1][k]
print(dp[l][5] % (pow(10,9)+7))

Submission status: Time Limit Exceeded

Solution code:
"""
この解答に自分用にコメントつけただけ
https://atcoder.jp/contests/abc135/submissions/6585300
"""

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
    # dp[i][j] は頭からi番目までの数字を13で割った時j余る数がいくつあるか
    MOD = 10**9 + 7

    dp[0][0] = 1 # 何もなしのとき０とする

    """
    たとえば５６７８という数字について考えるとき
    5：s[1][5] = 1で他のjが０
    56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
    先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
    """

    for i in range(1, len(S)+1):
        if S[i-1] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i][(k*10 + j) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく
        else:
            for k in range(13):
                dp[i][(k*10 + int(S[i-1])) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
# dp[i][j] は頭からi番目までの数字を13で割った時j余る数がいくつあるか
MOD = 10**9 + 7

dp[0][0] = 1 # 何もなしのとき０とする

"""
たとえば５６７８という数字について考えるとき
5：s[1][5] = 1で他のjが０
56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
"""

for i in range(1, len(S)+1):
    if S[i-1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k*10 + j) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく
    else:
        for k in range(13):
            dp[i][(k*10 + int(S[i-1])) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく

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

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                for k in range(13):
                    dp[1][(pow(10, i, 13) * j + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(pow(10, i, 13) * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(pow(10, i, 13) * j + k) % 13] += (dp[0][k] % mod)
        else:
            if i == 0:
                dp[1][s[-i-1] % 13] += 1
            else:
                for k in range(13):
                    dp[1][(pow(10, i, 13) * s[-i-1] + k) % 13] += (dp[0][k] % mod)
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][((10 ** i) % 13 * j + k) % 13] += (dp[0][k] % mod)
        else:
            if i == 0:
                dp[1][s[-i-1] % 13] += 1
            else:
                for k in range(13):
                    dp[1][((10 ** i) % 13 * s[-i-1] + k) % 13] += (dp[0][k] % mod)
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(10 ** i * j + k) % 13] += (dp[0][k] % mod)
        else:
            if i == 0:
                dp[1][s[-i-1] % 13] += 1
            else:
                for k in range(13):
                    dp[1][(10 ** i * s[-i-1] + k) % 13] += (dp[0][k] % mod)
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    for i in range(len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(10 ** i * j + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        else:
            if i == 0:
                dp[1][s[-i-1] % 13] += 1
            else:
                for k in range(13):
                    dp[1][(10 ** i * s[-i-1] + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    dp = [[0] * 13 for _ in range(2)]
    for i in range(len(s)):
        if s[-i-1] == "?":
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(10 ** i * j + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        else:
            if i == 0:
                dp[1][int(s[-i-1]) % 13] += 1
            else:
                for k in range(13):
                    dp[1][(10 ** i * int(s[-i-1]) + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    dp = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if s[-i-1] == "?":
            for j in range(10):
                if i == 0:
                    dp[0][j % 13] += 1
                else:
                    for k in range(13):
                        dp[i][(10 ** i * j + k) % 13] += (dp[i-1][k] % (10 ** 9 + 7))
        else:
            if i == 0:
                dp[0][int(s[-i-1]) % 13] += 1
            else:
                for k in range(13):
                    dp[i][(10 ** i * int(s[-i-1]) + k) % 13] += (dp[i-1][k] % (10 ** 9 + 7))
    print(dp[-1][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

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

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

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)

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

for i in range(1,n):
    c = s[i]
    for j in range(13):
        count = 0
        if c!="?":
            cc = int(c)
            for k in range(13):
                if (cc+(10*k)) %13 ==j:
                    count += dp[i-1][k] 
        else:
            for k in range(13):
                for cc in range(10):
                    if (cc+10*k) % 13 == j:
                        count += dp[i-1][k]
        dp[i][j] = count
print(dp[n-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
mul = 1
for index in range(len(S)):
    s = S[len(S) - index - 1]
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul +  pre_index ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i * mul  +  pre_index ) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
    mul *= 10
 
 
 
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(1, len(S) + 1):
    s = S[len(S) - index ]
    mul = (10 ** (index - 1)) % 13
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul  +  pre_index ) % 13
                dp[index][next_i] += dp[index - 1][pre_index] 
    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i * mul +  pre_index ) % 13
            dp[index][next_i] += dp[index - 1][pre_index] 
 
    for i in range(13):
        dp[index][i] %= MOD
 
 
 
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

MOD = 10**9+7

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


dp[0][0] = 1



for index in range(1, len(S) + 1):
    s = S[len(S) - index ]
    mul = (10 ** (index - 1)) % 13
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul  +  pre_index ) % 13
                dp[index][next_i] += dp[index - 1][pre_index] % MOD
    else:
        i = int(s)
        for pre_index in range(13):
            next_i = (i * mul +  pre_index ) % 13
            dp[index][next_i] += dp[index - 1][pre_index] % MOD




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