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:
# coding: utf-8
# Your code here!
#借りた
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)
S=["!"]*((6-N%6)%6)+S
N=len(S)

num=[0]*6#左から大きい
que=[0]*6


for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    elif S[i]=="!":
      pass
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10

print(num)
print(que)
    
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

print(len(cand))
print(amari)
#print(cand)

m=10**9+7
ans=0
for item in cand:
    temp=1
    for i in range(6):
        if que[i]==0 and (item[i]!=num[i]):
            temp=0
            break
        elif item[i]==0:
        	continue
        else:
            #これあってる？
            """
            targetは1,11,21...も考えないといけない
            questionの数見ればわかる
            """
            
            target=(item[i]-num[i]+10)%10
            for j in range(target):
                temp*=(target+que[i]-j-1)
                temp*=mod_inv(j+1,m)
                temp%=m
    #print(item)
    ans+=temp

print(ans%(m))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
#借りた
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp+amari)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)

num=[0]*6#左から大きい
que=[0]*6

for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

#print(amari)
#print(cand)

m=10**9+7
ans=0
for item in cand:
    temp=1
    for i in range(6):
        if que[i]==0 and item[i]!=0:
            temp=0
            break
        else:
            #これあってる？
            target=item[i]-num[i] if item[i]-num[i]<0 else item[i]-num[i]+10
            for j in range(min(que[i]-1,target)):
                temp*=(target+que[i]-j-1)
                temp*=mod_inv(j+1,m)%m
    ans+=temp
    """
    if temp!=0:
        print(item)
        print(ans)
    """
print(ans%(m))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
#借りた
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp+amari)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)

num=[0]*6#左から大きい
que=[0]*6

for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

#print(amari)
#print(cand)

m=10**9+7
ans=0
for item in cand:
    temp=1
    for i in range(6):
        if que[i]==0 and item[i]!=0:
            temp=0
            break
        else:
            for j in range(min(que[i]-1,item[i])):
                temp*=(item[i]+que[i]-j-1)*mod_inv(j+1,m)%m
    ans+=temp
    """
    if temp!=0:
        print(item)
        print(ans)
    """
print(ans%(m))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp+amari)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)

num=[0]*6#左から大きい
que=[0]*6

for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

#print(amari)
#print(cand)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp+amari)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)

num=[0]*6#左から大きい
que=[0]*6

for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

#print(amari)
#print(cand)

ans=0
for item in cand:
    temp=1
    for i in range(6):
        if que[i]==0 and item[i]!=0:
            temp=0
            break
        else:
            for j in range(que[i]-1):
                temp*=(item[i]+que[i]-j-1)
    ans+=temp
    """
    if temp!=0:
        print(item)
        print(ans)
    """
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[dgt][mo] := dgt桁目まで確定していて, そこまでで13で割った余りがmoである組み合わせ
# ?であるときは, その数にしかできないため, その数をつかう
# ?であるときは0~9を全て試して遷移させよう
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5+10)]
    dp[0][0] = 1
    for mo in range(13):
        for dgt in range(l):
            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[l][5]%MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

mod = 10**9+7
s = "?"*10**5#readline().rstrip().decode('utf-8')

dp = [0]*13 #あまりが0~12の13通りとなる場合の数
dp[0] = 1
dig = 1 #今見てる桁数
for i in range(len(s)-1,-1,-1): #小さい方の桁から見ていく
    c = s[i]
    next_dp = [0]*13 #逐次更新してはいけないので、次の桁の数についてjを回して入れていく
    if c == "?": #?なら0~10の10通り全てについてあたる必要がある
        for d in range(10):
            for j in range(13):
                next_dp[(d*dig + j)%13] += dp[j]
                next_dp[(d*dig + j)%13] %= mod

    
    else:
        d = int(c)
        for j in range(13):
            next_dp[(d*dig + j)%13] += dp[j]
            next_dp[(d*dig + j)%13] %= mod


    dig *= 10
    dig %= 13
    dp = next_dp

print(dp[5]%mod)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    print(len(s))
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 公式解説に出ているのと同等のアルゴリズム
# 計算量は10*13*10^5 = 1300万

s = input()
# 下位から 1?2?3 だったら 3 → ?3 → 2?3 → …… の順にする 解説で最初に書いてたやつ

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

dp[-1][0] = 1
ten_power = 1
for digit in reversed(range(l)):
    if s[digit] != '?':
        for k in range(13):
            dp[digit][(k + int(s[digit]) * ten_power) % 13] = dp[digit+1][k]
    else:
        for k in range(13):
            for i in range(10):
                dp[digit][(k + i * ten_power) % 13] += dp[digit+1][k]
        for k in range(13):
            dp[digit][k] %= mod

    ten_power *= 10
    ten_power %= mod
        

print(dp[0][5])

Submission status: Wrong Answer

Solution code:
S = input()
memo = [[0]*(13) for _ in range(len(S))]
mod = 10**9 + 7
def main():
    cnt = 1
    R = []
    for _ in range(len(S)):
        R.append(cnt)
        cnt = (cnt*10)%13
    dic = [{} for _ in range(13)]#iに対してS[j]が?だった場合のi*range(13)の余りの全列挙
    for i in range(13):
        for j in range(10):
            if (i*j)%13 not in dic[i]:
                dic[i][(i*j)%13] = True
    if S[-1] == "?":
        for i in range(10):
            memo[0][i] = 1
    else:
        memo[0][int(S[-1])] = 1
    for d in range(len(S) - 1):
        s = S[-2-d]
        if s == "?":
            tmp = dic[R[d+1]]
            for key in tmp.keys():
                for i in range(13):
                    memo[d + 1][(key + i)%13] = (memo[d][i] + memo[d + 1][(key + i)%13])%mod
        else:
            for i in range(13):
                memo[d + 1][(i + int(s)*R[d])%13] = (memo[d][i] + memo[d + 1][(i + int(s)*R[d])%13])%mod
    print(memo[len(S) - 1][5])
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def dot(A, x):
  return [sum([x[t]*A[s][t] for t in range(13)]) for s in range(13)]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

MOD=10**9+7

if S[0]=='?':
  x=[1]*10+[0]*3
else:
  x=[0]*13
  x[int(S[0])]=1
  
P=[
  [
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
  ]
]

for i in range(1, N):
  if S[i]=='?':
    tmp=sum(x)
    x=[
      tmp-x[4]-x[8]-x[12],
      tmp-x[3]-x[8]-x[12],
      tmp-x[3]-x[7]-x[12],
      tmp-x[3]-x[7]-x[11],
      tmp-x[2]-x[7]-x[11],
      tmp-x[2]-x[6]-x[11],
      tmp-x[2]-x[6]-x[10],
      tmp-x[1]-x[6]-x[10],
      tmp-x[1]-x[5]-x[10],
      tmp-x[1]-x[5]-x[9],
      tmp-x[0]-x[5]-x[9],
      tmp-x[0]-x[4]-x[9],
      tmp-x[0]-x[4]-x[8]
    ]
  elif S[i]=='0':
    x=[x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9]]
  elif S[i]=='1':
    x=[x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5]]
  elif S[i]=='2':
    x=[x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1]]
  elif S[i]=='3':
    x=[x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10]]
  elif S[i]=='4':
    x=[x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6]]
  elif S[i]=='5':
    x=[x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2]]
  elif S[i]=='6':
    x=[x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11]]
  elif S[i]=='7':
    x=[x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7]]
  elif S[i]=='8':
    x=[x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3]]
  elif S[i]=='9':
    x=[x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12]]
    
  x=[x[j]%MOD for j in range(13)]
    
print(x)

Submission status: Wrong Answer

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

#i桁目までみて，あまりがjになるものの個数
dp=[[0]*mod for _ in range(N+1)]

dp[0][0]=1

for i in range(N):
    pow10*=10
    if S[-i-1]!="?":
        a=(pow10*int(S[-i-1]))%mod
        for j in range(mod):
            dp[i+1][(j+a)%mod]=dp[i][j]
    else:
        a=pow10%mod
        for j in range(mod):
            for k in range(10):
                dp[i+1][(j+k*a)%mod]+=dp[i][j]
                dp[i+1][(j+k*a)%mod]%=mod2

print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.buffer.readline

def main():
    S = list(str(input()))
    a = len(S)
    dp = [[0 for _ in range(13)] for _ in range(a+1)]
    dp[0][0] = 1
    INF = 10**9+7
    
    for i in range(a):
        if S[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i+1][(10*k+j)%13] += dp[i][k]%INF
        else:
            for k in range(13):
                dp[i+1][(10*k+int(S[i]))%13] += dp[i][k]%INF
    
    print(dp[-1][5])
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
S = "??2??5"
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
mul = 1
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*mul%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*mul%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    mul = mul*10%13
print(dp[amari])

Submission status: Wrong Answer

Solution code:
rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
cnt = 0
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*(10**cnt)%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*(10**cnt)%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    #cnt += 1
    cnt = cnt+1 if cnt <=5 else 0
print(dp[amari])

Submission status: Wrong Answer

Solution code:
rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
cnt = 0
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*(10**cnt)%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*(10**cnt)%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    cnt = cnt+1 if cnt <=11 else 0
print(dp[amari])

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
rotate = lambda x,y:x[y:] + x[:y]
S = input()
mod = 13
amari = 5

dp_tmp = [0]*13
dp_tmp[0] = 1
for i,s in enumerate(S[::-1]):
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*(10**i)%mod)
            for i in range(13):
                dp[i] += dp_tmp_roll[i]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*(10**i)%mod)
        for i in range(13):
            dp[i] += dp_tmp_roll[i]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = deepcopy(dp)
print(dp[amari])

Submission status: Wrong Answer

Solution code:
S = input()
mod = 13
amari = 5

import numpy as np
dp = np.zeros((len(S)+1,mod),dtype="uint64")
dp[0,0%mod] = 1
for i,s in enumerate(S):
    if s == "?":
        for n in range(10):
            dp[i+1,:] += np.roll(dp[i],n*(10**i)%mod)
    else:
        dp[i+1,:] += np.roll(dp[i],int(s)*(10**i)%mod)
    dp = dp%(10**9+7)
print(dp[-1,amari+1])

Submission status: Wrong Answer

Solution code:
s = input()
q = s.count("?")
ans = [0] * 13
ans[0] = 1

for v in s:
    dp = [0] * 13
    for j in range(13):
        dp[(j * 10) % 13] = ans[j] % 1000000007
    dp += dp
    for j in range(13):
        if v == '?':
            ans[j] = sum(dp[j+4:j+14])
        else:
            ans[j] = dp[(j + int(v)) % 13]

print(ans[5] % 1000000007)

Submission status: Wrong Answer

Solution code:
def main():
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            for l in [(a*j) % 13 for j in range(10)]:
                for j in range(13):
                    memo2[(l+j) % 13] += memo[j]
        else:
            l = a*int(s[i])
            memo = memo[(-l) % 13:] + memo[:(-l) % 13]
            memo = [j % mod for j in memo]
    print(memo[5])


main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int32)
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = np.zeros(13, dtype=np.int32)
        a = m13[i % 12]
        if s[i] == "?":
            list_ = np.arange(10)
        else:
            list_ = np.array([int(s[i])])
        list_ = a*list_ % 13
        for l in list_:
            memo2[l:] += memo[:13-l]
            memo2[:l] += memo[13-l:]
        memo = memo2 % mod
    print(int(memo[5]))


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

init = [0 for i in range(13)]
if s[0] == '?':
  dp = [1] * 10 + [0] * 3
else:
  dp = [0 for i in range(13)]
  dp[int(s[0])] = 1

for c in s[1:]:
  d = init
  if c == '?':
    for i in range(13):
      for j in range(10):
        idx = (i * 10 + j) % 13
        d[idx] = (dp[i] + d[idx]) % mod 
  else :
    for i in range(13):
      idx = (i * 10 + int(c)) % 13
      d[idx] = (dp[i] + d[idx]) % mod
  dp = d
print(dp[5])

Submission status: Wrong Answer

Solution code:
import re

s = input()
pattern = s.replace('?','.')
max_s = int(s.replace('?','9'))
min_s = int(s.replace('?','0'))
s_len = len(s)

d = min_s % 13
min_s += 5-d
count = 0

#dot_count = 0
#for i in range(len(pattern)):
#  if pattern[i] != '.':
#    break
#  dot_count += 1
#removed_pattern = pattern[dot_count:len(pattern)] + '$'

for i in range(min_s,max_s+1,13):
  padding = s_len - len(str(i))
  if re.match(pattern,padding*'a'+str(i)):
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import re

s = input()
pattern = s.replace('?','.')
max_s = int(s.replace('?','9'))
min_s = int(s.replace('?','0'))
s_len = len(s)

d = min_s % 13
min_s += 5-d
count = 0

dot_count = 0
for i in range(len(pattern)):
  if pattern[i] != '.':
    break
  dot_count += 1
removed_pattern = '.*'+ pattern[dot_count:len(pattern)] + '$'

for i in range(min_s,max_s+1,13):
  if re.match(removed_pattern,str(i)):
    count += 1
print(count)

Submission status: Wrong Answer

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

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1

# mul = 10**(i-1)
mul = 10
# i: i桁目
for i in range(1,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*mul % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] = (dp[i][(k+jmod)%13] + x) % MOD
    else:
        jmod = int(S[-i])*mul % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] = (dp[i][(k+jmod)%13] + x) % MOD
    mul = (mul * 10) % 13

print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1


# power = 10**(i-1)
power = 10
# i: i桁目
for i in range(1,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*power % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] += x
    else:
        jmod = int(S[-i])*power % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] += x
    
    # 次の探索の準備
    power = power * 10 % 13

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = [[0]*13 for _ in range(len(S)+1)]

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] = [1]*10
else:
    dp[1][int(S[-1])] += 1


# power = 10**(i-1)
power = 10
# i: i桁目
for i in range(1,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        for j in range(10):
            jmod = j*power % 13
            # (i-1)桁目で余りがkとなる個数x
            for k,x in enumerate(dp[i-1]):
                dp[i][(k+jmod)%13] += x
    else:
        jmod = int(S[-i])*power % 13
        for k,x in enumerate(dp[i-1]):
            dp[i][(k+jmod)%13] += x
    
    # 次の探索の準備
    power = power * 10 % 13
    for j,x in enumerate(dp[i]):
      dp[i][j] = x % (10**9+7)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np

S = input().rstrip("\n")

# dp[i][j]: i文字目でjになる個数 (S[-i])
# 1-indexed
dp = np.array([[0]*13 for _ in range(len(S)+1)])

# 初期条件(1桁目)
if S[-1] == "?":
    dp[1][:10] += 1
else:
    dp[1][int(S[-1])] += 1

# i: i桁目
# O(|S|)
for i in range(2,len(S)+1):
    if S[-i] == "?":
        # j: S[-i]がとる値 (?のとき0~9)
        # O(10)
        for j in range(10):
            jmod = j*(10**(i-1)) % 13
            dp[i] += np.roll(dp[i-1], jmod)
    else:
        jmod = int(S[-i])*(10**(i-1)) % 13
        dp[i] = np.roll(dp[i-1], jmod)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

S = input()
mod = int(10**9 + 7)
dp = np.zeros(13, dtype=int)
dp[0] = 1

M = np.zeros((13, 13), dtype=int)
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for s in S:
    ndp = np.zeros(13, dtype=int)
    if s == '?':
        ndp = np.dot(dp, M)
    else:
        d = int(s)
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = ndp % mod
    print(dp)

print(dp[5])

Submission status: Wrong Answer

Solution code:
import numpy as np

S = input()
mod = int(10**9 + 7)
dp = np.zeros(13)
dp[0] = 1

amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)

for s in range(len(S)):
    ndp = np.zeros(13)
    if s == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(s)
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = np.mod(ndp, mod)

print(dp[5])

Submission status: Wrong Answer

Solution code:
s=input()
d=[0]*13
d[0]=1
for i in s:
    dnew=[0]*13
    if i=="?":
        for j in range(10):
            for k in range(13):
                dnew[(10*k+j)%13]+=d[k]
                dnew[k]%=(10**9+7)
    else:
        for k in range(13):
            dnew[(10*k+int(i))%13]+=d[k]
            dnew[k]%=(10**9+7)
    d=dnew

print(d[5])

Submission status: Wrong Answer

Solution code:
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    if s[-1]=="?":
        dp=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp=[0]*13
        dp[int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**(i %13)
        ss0=s[n-i-1]
        if ss0!="?":
            dpnew = [ dp[(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dpnew = [sum( dp[(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
        dp=dpnew[:]
    print(dp[5])
    
if __name__ == '__main__':
    main()