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: Wrong Answer

Solution code:
MOD = 10**9 + 7
memo = None


def rec(S, k, total):
    if k == len(S)//3:
        # print(total)
        fixed_total = total + 5 if k % 2 == 0 else total - 5
        # fixed_total = abs(total) + 5
        memo[k][total % 13] = int((fixed_total) % 13 == 0)
        return int((fixed_total) % 13 == 0)

    if memo[k][total % 13] is not None:
        return memo[k][total % 13]

    s = S[k*3:k*3+3]
    d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
    d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
    d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]
    ret = 0

    for i1 in d1:
        for i2 in d2:
            for i3 in d3:
                num = int(i1 + i2 + i3)
                if k % 2 == 0:
                    ret += rec(S, k+1, total + num)
                else:
                    ret += rec(S, k+1, total - num)

    memo[k][total % 13] = ret
    return ret

S = input()

# if len(S) % 3 == 1:
#     S = '00' + S
# elif len(S) % 3 == 2:
#     S = '0' + S

# L = (len(S) // 3)
# dp = [[0 for i in range(14)] for j in range(L + 1)]
# # print(rec(S, 0, 0) % MOD)
# # print(memo)

# dp[0][0] = 1

# for k in range(L):
#     for m in range(13):
#         s = S[k*3:k*3+3]
#         d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
#         d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
#         d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]

#         for i1 in d1:
#             for i2 in d2:
#                 for i3 in d3:
#                     num = int(i1 + i2 + i3)
#                     dp[k + 1][(13 + num - m) % 13] += dp[k][m]

#         for i in range(13):
#             dp[k][m] %= MOD

# print(dp[L][5] % MOD)

L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                print('k', k, 'm', m, '(m * 10 + i)', (m * 10 + i))
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

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

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for dgt in range(N):
  for mo in range(13):
    if S[dgt] == "?":
      for nxt in range(10):
        dp[dgt+1][(mo*10+nxt)%13] += dp[dgt][mo]
    else:
      dp[dgt+1][(mo*10+int(S[dgt]))%13] += dp[dgt][mo]
print(dp[N][5])

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp_org = dp.copy()
dp[0] = 1
mod = 0
for i in range(n):
    dp_old = dp.copy()
    dp = dp_org
    weight = 10**i % 13
    if s[n - i - 1] == '?':
        for k in range(10):
            kw = k * weight
            for j in range(13):
                dp[(j + kw) % 13] += dp_old[j] % 1000000007
                
    else:
        for j in range(13):
            dp[(j + int(s[n - i - 1]) * weight) % 13] += dp_old[j] % 1000000007
print(dp[5] % 1000000007)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
        dp[i] %= MOD
print(dp[5])

Submission status: Wrong Answer

Solution code:
import numpy as np


s = input()[::-1]

dp = np.zeros((len(s),13), dtype="uint64")

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

print(dp)

L1 = range(1, len(s))
L2 = range(13)

for i in L1:
    if s[i] == "?":
        mod = pow(10, i, 13)
        mod_list = ((mod*i)%13 for i in range(10))
        for j in mod_list:
            dp[i, :] += np.roll(dp[i - 1, :], j)
        dp[i, :] %= (10**9+7)
    else:
        mod = (pow(10, i, 13)*int(s[i]))%13
        dp[i, :] += np.roll(dp[i - 1, :], mod)

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

Submission status: Wrong Answer

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

dp = [[0 for _ in range(13)] for _ in range(len(s))]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

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

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

Submission status: Wrong Answer

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

dp = [[0 for _ in range(13)] for _ in range(len(s))]

if s[0] =="?":
    dp[0] = [1]*13
else:
    dp[0][int(s[0])] =1

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

print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
 
S = input()
lenS = len(S)
 
table_bef = [0 for _ in range(13)]
mod = 10**9 + 7
for i in range(lenS):
    if i == 0:
        flag = True
    else:
        flag = False
    table_bef = [one_rem % mod for one_rem in table_bef]
    table_aft = [0 for _ in range(13)]
    remainder_10 = (10**i) % 13
    int_or_str = S[lenS-i-1]
    if int_or_str == '?':
        if flag:
            table_aft = [1 if p < 10 else 0 for p in range(13)]
        else:
            for n in range(10):
                tmp_remainder = (remainder_10 * n) % 13
                for m in range(13):
                    remainder = (tmp_remainder + m) % 13
                    table_aft[remainder] += table_bef[m]
    else:
        int_or_str = int(int_or_str)
        if flag:
            table_aft[int_or_str] += 1
        else:
            for m in range(13):
                remainder = (int_or_str + m) % 13
                table_aft[remainder] += table_bef[m]
    
    table_bef = deepcopy(table_aft)

print(table_aft[5])

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

S = input()
lenS = len(S)

table_bef = [0 for _ in range(13)]
mod = 10**9 + 7
for i in range(lenS):
    if i == 0:
        flag = True
    else:
        flag = False
    table_bef = [one_rem % mod for one_rem in table_bef]
    table_aft = [0 for _ in range(13)]
    remainder_10 = (10**i) % 13
    int_or_str = S[lenS-i-1]
    if int_or_str == '?':
        if flag:
            table_aft = [1 if p < 10 else 0 for p in range(13)]
        else:
            for n in range(10):
                tmp_remainder = (remainder_10 * n) % 13
                for m in range(13):
                    remainder = (tmp_remainder + m) % 13
                    table_aft[remainder] += table_bef[m]
    else:
        int_or_str = int(int_or_str)
        if flag:
            table_aft[int_or_str] += 1
        else:
            for m in range(13):
                remainder = (int_or_str + m) % 13
                table_aft[remainder] += table_bef[m]
    
    print(table_aft)
    table_bef = deepcopy(table_aft)

Submission status: Wrong Answer

Solution code:
a = list(input())

b = [[0 for i in range(13)] for i in range(len(a) + 1)]
b[0][0] = 1

check = 0
for i in range(len(a)):
    if a[i] == '?':
        check = -1
    else:
        check = int(a[i])

    for j in range(10):
        if check == -1 or check == j:
            for k in range(13):
                b[i + 1][(k * 10 + j) % 13] += b[i][k]
        
    for l in range(13):
        b[i + 1][l] %= 1000000007

print(b[len(a)][4])

Submission status: Wrong Answer

Solution code:
import numpy as np
s=list(input())
n=len(s)
mod=10**9 + 7
dp=np.zeros((n,13))
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(n-1):
    if s[n-2-i]=='?':
        for j in range(13):
            if dp[i][j]>0:
                for k in range(10):
                    dp[i+1][(j+(10**(i+1))*k)%13]+=dp[i][j]
                    dp[i+1][(j+(10**(i+1))*k)%13]%=mod
    else:
        for j in range(13):
            if dp[i][j]>0:
                dp[i+1][(j+(10**(i+1))*int(s[n-2-i]))%13]+=dp[i][j]
                dp[i+1][(j+(10**(i+1))*int(s[n-2-i]))%13]%=mod
print(round(dp[n-1][5]%mod))

Submission status: Wrong Answer

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

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(n-1):
    if s[n-2-i]=='?':
        for j in range(13):
            if dp[i][j]>0:
                for k in range(10):
                    dp[i+1][(j+(10**i)*k)%13]+=dp[i][j]
                    dp[i+1][(j+(10**i)*k)%13]%=mod
    else:
        for j in range(13):
            if dp[i][j]>0:
                dp[i+1][(j+(10**i)*int(s[n-2-i]))%13]+=dp[i][j]
                dp[i+1][(j+(10**i)*int(s[n-2-i]))%13]%=mod
print(dp[n-1][6]%mod)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

S = input()
S = S[::-1]
N = len(S)
dp=np.zeros((N+1,13),dtype=np.int)
dp[0,0]=1

for i in range(N):
    print(S[i])
    if S[i]=="?":
        for s in range(10):
            for j in range(13):
                dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
    else:
        s=int(S[i])
        for j in range(13):
            dp[i+1][(s*(10**i)+j) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD

res = dp[N,5]
print(res%MOD)

Submission status: Wrong Answer

Solution code:
s=input()
p=[1]+[0]*12
q=10
t=[[i*k%13 for i in range(10)]for k in range(13)]
for i in s:
    if i!="?":
        i=int(i)
        g=q*i%13
        p=p[-g:]+p[:-g]
    else:
        d=[0]*13
        for j in t[q]:
            r=p[-j:]+p[:-j]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

s = list(input())
n = len(s)

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

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

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

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

s = list(input())
n = len(s)

dp = [[0 for _ in range(13)] for _ 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][(k * 10 ** i + j) % 13] += dp[i][j] % mod
	else:
		for j in range(13):
			dp[i + 1][(int(s[i]) * 10 ** i + j) % 13] += dp[i][j] % mod

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

Submission status: Wrong Answer

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

dp = [[0 for _ in range(13)] for _ 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][(k * 10 ** i + j) % 13] += dp[i][j]
	else:
		for j in range(13):
			dp[i + 1][(int(s[i]) * 10 ** i + j) % 13] += dp[i][j]

print(dp[n][5])

Submission status: Wrong Answer

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

print(dp[5])

Submission status: Wrong Answer

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

print(dp[5])

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9+7
s=[x for x in input()]
n=len(s)
dp=np.zeros((n+1,13)).astype(np.uint64)
dp[0,0]=1
for i in range(n):
  for j in range(10):
    if s[i]!='?' and s[i]!=str(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(int(dp[n,5]))
print(dp)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10%13
    print(dp[5]%1000000007, "d")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10
    print(dp[5]%1000000007, "d")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [[0]*13 for _ in range(length+1)]
    dp[0][0]=1
    mul=1
    for i in range(1,length+1):
        for j in range(13):
            if dp[i-1][j] != 0:
                if S[length-i] == "?":
                    for k in range(10):
                        dp[i][(j+k*mul)%13]+=dp[i-1][j]
                else: 
                    dp[i][(j+int(S[length-i])*mul)%13]+=dp[i-1][j]
        mul=mul*10
    print(dp)
    print(dp[length][5]%1000000007, "d")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(1000000)
def main():
    S = list(input())
    length=len(S)
    dp = [[0]*13 for _ in range(length)]
    dp[0][0]=1
    mul = 1
    for i in range(length-1):
        if S[length-i-2] == "?":
            for k in range(10):
                for j in range(13):
                    j_sub = j-k*mul%13
                    if j_sub < 0: j_sub+= 13
                    dp[i+1][j]+=dp[i][j_sub]
        else:
            for j in range(13):
                j_sub = j-int(S[length-i-2])*mul%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
        mul=mul*10
    print(dp[length-1][5]%1000000007)
    print("db")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    length=len(S)
    dp = [[0]*13 for _ in range(length)]
    dp[0][0]=1
    mul=1
    for i in range(1,length):
        for j in range(13):
            if dp[i-1][j] != 0:
                if S[length-i-1] == "?":
                    for k in range(10):
                        j_sub = j+k*mul%13
                        if j_sub > 12: j_sub-=13
                        dp[i][j_sub]+=dp[i-1][j]
                else: 
                    j_sub = j+int(S[length-i-1])*mul%13
                    if j_sub > 12: j_sub-= 13
                    dp[i][j_sub]+=dp[i-1][j]
        mul=mul*10
    print(dp[length-1][5]%1000000007, "d")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(1000000)
S = list(input())
length=len(S)
dp = [[0]*13 for _ in range(length)]
dp[0][0]=1
mul = 1
for i in range(length-1):
    if S[length-i-2] == "?":
        for k in range(10):
            for j in range(13):
                j_sub = j-k*mul%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
    else:
        for j in range(13):
            j_sub = j-int(S[length-i-2])*mul%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
    mul=mul*10
print(dp[length-1][5]%1000000007)
print("dammy")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(1000000)
S = list(input())
length=len(S)
dp = [[0]*13 for _ in range(length)]
dp[0][0]=1
mul = 1
for i in range(length-1):
    if S[length-i-2] == "?":
        for k in range(10):
            for j in range(13):
                j_sub = j-k*mul%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
    else:
        for j in range(13):
            j_sub = j-int(S[length-i-2])*mul%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
    mul=mul*10
print(dp[length-1][5]%1000000007)
print("db")

Submission status: Wrong Answer

Solution code:
S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

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

i=0
for k in reversed(S):
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


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

Submission status: Wrong Answer

Solution code:

#readed editional
MOD = int(1e9)+7
print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

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

dp[0][0] = 1
print(dp)

for i in range(n):
    c = 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] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])

Submission status: Wrong Answer

Solution code:
N=input()

lists = []
temp=[i for i in range(1,10)]

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            a = amari*10 % 13
            for num in temp:
                if a+num in new_dic:
                    new_dic[a+num]+=count
                else:
                    new_dic[a+num]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=input()

lists = []
temp=[i for i in range(10)]

dic={0:1}

for i in N:
    new_dic={}
    if i == "?":
        for amari,count in list(dic.items()):
            for num in temp:
                a = (amari*10 + num) % 13
                new_dic[a]=count
    else:
        num=int(i)
        for amari,count in list(dic.items()):
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline().strip

import numpy as np
MOD = int(10 ** 9 + 7)

S = input()
N = len(S)
dp = np.zeros([N + 1, 13], dtype = int)
dp[0][0] = 1
for i in range(N):
    s = S[i]
    if s == '?':
        c = -1
    else:
        c = int(s)
    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(10):
        dp[i + 1][j] %= MOD
        
print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

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

Submission status: Wrong Answer

Solution code:
#45 ABC135D 桁DP
s=input()
s=s[::-1]
n=len(s)
dp=[[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	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]%=(10**9+7)
print(dp[n][5])

Submission status: Wrong Answer

Solution code:
import copy
S=input()
length=len(S)
dp=[0 for i in range(13)]
dp[0]=1
nextdp = [0 for i in range(13)]
s=S[::-1]#一桁目が先頭に来た
p=1#その桁数での10の累乗の13で割ったあまり
#毎回、nextdpをdpに代入して、dpに何か操作してnextdpに代入する
for i in range(length):#0~length-1まで
    if i!=0:
        dp = copy.deepcopy(nextdp)
        for k in range(13):
            nextdp[k]=0
    if s[i]=="?":
        for j in range(10):#s[i]の数字に対応
            for k in range(13):#dpの要素数に対応
                nextdp[(k+j*p)%13]+=dp[k]
    else:
         for k in range(13):#dpの要素数に対応
                nextdp[(k+int(s[i])*p)%13]+=dp[k]
    
    for k in range(13):
        nextdp[k]%=10**9+7
    p=(10*p)%13#前回のpの値を用いてpの更新を楽に

print(nextdp[6])

Submission status: Wrong Answer

Solution code:
import copy
S=input()
length=len(S)
dp=[0 for i in range(13)]
dp[0]=1
nextdp = [0 for i in range(13)]
s=S[::-1]#一桁目が先頭に来た
p=1#その桁数での10の累乗の13で割ったあまり
#毎回、nextdpをdpに代入して、dpに何か操作してnextdpに代入する
for i in range(length):#0~length-1まで
    
    print(p)
    if i!=0:
        dp = copy.deepcopy(nextdp)
        for k in range(13):
            nextdp[k]=0
    if s[i]=="?":
        for j in range(10):#s[i]の数字に対応
            for k in range(13):#dpの要素数に対応
                nextdp[(k+j*p)%13]+=dp[k]
    else:
         for k in range(13):#dpの要素数に対応
                nextdp[(k+int(s[i])*p)%13]+=dp[k]
    
    for k in range(13):
        nextdp[k]%=10**9+7
    p=(10*p)%13#前回のpの値を用いてpの更新を楽に

print(nextdp[6])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    if S[-1] == '?':
        for i in range(10):
            DP[i] = 1
    else:
        DP[int(S[-1])] = 1

    for i in range(1, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for x in range(10):
                nx = x * 10
                for k in range(13):
                    t = (nx + k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i]) * 10
            for k in range(13):
                t = (y+k) % 13
                DP[t] = preDP[k] % MOD
    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S = input()
text = S[::-1]
DP = [[0] * 13 for _ in range(len(S))]
MOD = (10**9 + 7)

if text[0] == '?':
    for i in range(10):
        DP[0][i] = 1
else:
    DP[0][int(text[0])] = 1

for i in range(1, len(S)):
    if text[i] == '?':
        for x in range(10):
            nx = x * 10 ** i
            for k in range(13):
                t = (nx + k) % 13
                DP[i][t] += DP[i-1][k] % MOD
    else:
        y = int(text[i]) * 10 ** i
        for k in range(13):
            t = (y+k) % 13
            DP[i][t] = DP[i-1][k] % MOD

ans = DP[len(S)-1][5]
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def main(s):
    reminder = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
    dp = [1] + [0] * 12
    for char in s:
        if char == "?":
            dp = [sum(dp[j] for j in k) % MOD for k in reminder]
        else:
            dp = [dp[(int(char) - k) * 9 % 13] for k in range(13)]
        print(dp)

    return dp[5]


S = input()
print(main(S))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int32)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int32)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int32)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        priv = cur
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Wrong Answer

Solution code:
s = input()
dpa = [0]*13
dpb = [0]*13
mods = [4,1,10,9,12,3]
mod = 10**9+7
lens = len(s)
flag = True


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

for i in range(2,lens+1):
  if s[-i] == '?':
    if flag:
      for k in range(10):
        m = mods[i%6]*k
        for j in range(13):
          dpb[(j+m)%13] += dpa[j]
      for l in range(13):
        dpb[l] %= mod
      dpa = [0]*13
    else:
      for k in range(10):
        m = 10**(i-1)*k%13
        for j in range(13):
          dpa[(j+m)%13] += dpb[j]
      for l in range(13):
        dpb[l] %= mod
      dpb = [0]*13
    flag = not flag          
  else:
    m = mods[i%6]*int(s[-i])
    if flag:
      for j in range(13):
        dpb[(j+m)%13] = dpa[j]
      dpa = [0]*13
    else:
      for j in range(13):
        dpa[(j+m)%13] = dpb[j]
      dpb = [0]*13
    flag = not flag

print(max(dpa[5],dpb[5]))

Submission status: Wrong Answer

Solution code:
#coding utf-8
S=list(input().strip())
S=[0]+S

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

dp[0][0]=1    
for i in range(len(S)):
  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[-1][5])

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

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

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

div13_list = [1]
for ii in range(1, len(S)):
    n = div13_list[-1] * 10 % 13
    if n in div13_list:
        break
    else:
        div13_list.append(n)
div13_mat = np.array([div13_list] * 10, dtype = int)
div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

for ii in range(1, len(S)):
    # ind = -ii-1
    # tmp = div13_mat[ii%6]
    # if S[ind] == -1:
    #     for n in range(10):
    #         res = np.roll(arr, -tmp[n])
    #         # dp[1, res] += dp[0, arr]
    # else:
    #     res = np.roll(arr, -tmp[S[ind]])
    #     # dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0


print (dp[0, 5])