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:
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[[0 for _ in range(10**5+1)] for _ in range(13)]
#DP[i][j] あまりがi, j番目の数字までみた。その個数
DP[0][0]=1
m = 10**9+7

for i in range(len(s)):
    dig = s[i]
    shift = pow(10,i,m)
    if dig == '?':
        for j in range(10):
            for k in range(13):
                DP[(k+shift*j)%13][i+1] +=DP[k][i]
                DP[(k+shift*j)%13][i+1] %=m
                
    else:
        j = int(dig)
        for k in range(13):
            DP[(k+shift*j)%13][i+1] +=DP[k][i]
            DP[(k+shift*j)%13][i+1] %=m

print(DP[5][len(s)])

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[[0 for _ in range(10**5+1)] for _ in range(13)]
#DP[i][j] あまりがi, j番目の数字までみた。その個数
DP[0][0]=1
m = 10**9+7

for i in range(len(s)):
    dig = s[i]
    shift = pow(10,i,m)
    if dig == '?':
        for j in range(10):
            for k in range(13):
                DP[(k+shift*j)%13][i+1] +=DP[k][i]
                DP[(k+shift*j)%13][i+1] %=m
                
    else:
        j = int(dig)
        for k in range(13):
            DP[(k+shift*j)%13][i+1] +=DP[k][i]
            DP[(k+shift*j)%13][i+1] 

print(DP[5][len(s)])

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[[0 for _ in range(10**5+1)] for _ in range(13)]
#DP[i][j] あまりがi, j番目の数字までみた。その個数
DP[0][0]=1
m = 10**9+7

for i in range(len(s)):
    dig = s[i]
    shift = pow(10,i,m)
    if dig == '?':
        for j in range(10):
            for k in range(13):
                DP[(k+shift*j)%13][i+1] +=DP[k][i]
                
    else:
        j = int(dig)
        for k in range(13):
            DP[(k+shift*j)%13][i+1] +=DP[k][i]

print(DP[5][len(s)]%m)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D - Digits Parade
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
S = readline().decode().rstrip()
N = len(S)

dp = [0]*13
dp[0] = 1
# if S[0] == '?':
#     rem = pow(10,N,13)
#     for j in range(10):
#         t = rem*j%13
#         dp[t] += 1
# else:
#     s = int(S[0])
#     rem = pow(10,N,13)*s%13
#     dp[rem] += 1

for i in range(N):
    s = S[i]
    ndp = [0]*13
    rem = pow(10,N-i,13)
    if s == '?':
        for j in range(10):
            t = rem*j%13
            for k in range(13):
                ndp[(k+t)%13] += dp[k]
                ndp[(k+t)%13] %= MOD
    else:
        s = int(s)
        t = rem*s%13
        for k in range(13):
            ndp[(k+t)%13] += dp[k]
            ndp[(k+t)%13] %= MOD
    dp = ndp
print(dp[6]%MOD)

Submission status: Wrong Answer

Solution code:
S=input()
S=S[::-1]
dp=[[0]*14 for _ in [0]*(len(S)+1)]
dp[0][0]=1
#dp[n%2][m]:=下位n桁を決定したとき13でわった余りがmになるようなものの数
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p
p=10**9+7
for n in range(len(S)):
    x=pow_k(10,n,p)
    if S[n]=='?':
        for i in range(10):
            for m in range(13):
                dp[(n+1)][(m+i*x)%13]=(dp[(n+1)][(m+i*x)%13]+dp[n][m])%p
    else:
        s=int(S[n])
        for m in range(13):
            dp[(n+1)][(m+s*x)%13]=dp[n][m]%p
    
print(dp[len(S)][5])

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9 + 7
mul = 1
# n桁目の?は10^nを13で割った余り(mul)と掛け合わせて足される

for i in range(N):
    for k in range(10):
        if S[i] != '?' and S[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j + mul * k) % 13] += dp[i][j]
    mul = (mul * 10) % 13
    for j in range(13):
        dp[i+1][j] %= MOD

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s = input()
s = s[::-1]

app = defaultdict(int)

for i in range(len(s)):
    tmp_dic = defaultdict(int)
    if i == 0:
        if s[i] != '?':
            tmp_dic[int(s[i])]+= 1
        else:
            for j in range(13):
                tmp_dic[j] += 1

    else:
        if s[i] != '?':
            tmp = int(s[i]) * pow(10, i, 13)
            for j in range(13):
                tmp_dic[(tmp+j)%13] += app[j] % (10**9+7)

        else:
            for j in range(10):
                tmp = int(j) * pow(10, i, 13)
                for k in range(13):
                    tmp_dic[(tmp+k)%13] += app[k] % (10**9+7)

    app = tmp_dic

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

Submission status: Wrong Answer

Solution code:
s=input()

n=[0]*6
q=[0]*6
j=[1,10,9,12,3,4,1]
lens=len(s)
for i in range(lens):
    i6=i%6
    if s[lens-1-i]=="?":
        q[i6]+=1
    else:
        n[i6]+=int(s[lens-1-i])

mod=10**9+7

nsum=0
for i in range(6):
    nsum+=(n[i]*j[i])%13
nsum=(5-nsum)%13
    
cc2=[[-1]*13 for i in range(6)]

for i6 in range(6):
    for i in range(10):
        iii=(i*10**i6)%13
        cc2[i6][i]=iii

dpm=[0]*13
dpn=[0]*13
icnt=-1
for i6 in range(6):
    for i in range(q[i6]):
        dpn=[0]*13
        icnt+=1
        if icnt==0:
            for j in range(10):
                jj=(j*10**i6)%13
                dpm[jj]=1
            continue
        for mi in range(13):
            for j in range(10):
                ccir=(mi-cc2[i6][j])%13
                dpn[mi]=(dpn[mi]+dpm[ccir])%mod
        dpm=dpn.copy()  

print(dpm[nsum]%mod)

Submission status: Wrong Answer

Solution code:
s=input()

n=[0]*6
q=[0]*6
j=[1,10,9,12,3,4,1]
lens=len(s)
for i in range(lens):
    i6=i%6
    if s[lens-1-i]=="?":
        q[i6]+=1
    else:
        n[i6]+=int(s[lens-1-i])

mod=10**9+7

nsum=0
for i in range(6):
    nsum+=(n[i]*j[i])%13
nsum=(5-nsum)%13
    
cc2=[[-1]*13 for i in range(6)]

for i6 in range(6):
    for i in range(10):
        iii=(i*10**i6)%13
        cc2[i6][i]=iii

dpm=[0]*13
dpn=[0]*13
icnt=-1
for i6 in range(6):
    for i in range(q[i6]):
        dpn=[0]*13
        icnt+=1
        if icnt==0:
            for j in range(10):
                jj=(j*10**i6)%13
                dpm[jj]=1
            continue
        for mi in range(13):
            for j in range(10):
                ccir=(mi-cc2[i6][j])%13
                dpn[mi]=(dpn[mi]+dpm[ccir])%mod
        dpm=dpn.copy()  

print(dpm[nsum]%mod)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7

S=input()
old=[0]*13
old[0]=1
n=1
for c in S[::-1]:
  dp=[0]*13
  if c=='?':
    for j in range(10):
      for i in range(13):
        dp[(j*n%13+i)%13]+=old[i]
        dp[(j*n%13+i)%13]%=MOD
  else:
    c=int(c)
    for i in range(13):
      dp[(c*n%13+i)%13]+=old[i]
      dp[(c*n%13+i)%13]%=MOD
  old=[i for i in dp]
  n*=10
  n%=MOD
print(dp[5])

Submission status: Wrong Answer

Solution code:
import numpy as np

mod = 10 ** 9 + 7

S = input()
l = len(S)

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

dp[0][0] = 1

for i in range(l):
    D = S[i]
    if D == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][((j * 10) + k) % 13] += dp[i][j]

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

    for j in range(13):
        dp[i + 1][j] %= mod


print(dp[l][5])

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

for i in range(13):
    dp[i] %= mod

print(dp[5])

Submission status: Wrong Answer

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)

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

Submission status: Wrong Answer

Solution code:

S=list(input())[::-1]
N=len(S)
p=10**9+7
dp=[[0]*13 for _ in range(N)]
if S[0]!="?":
    dp[0][int(S[0])]+=1
else:
    for i in range(10):
        dp[0][i]+=1


for i in range(1,N):
    pre=dp[i-1]
    s=S[i]
    if s=="?":
        for k in range(0,10):
            for j,x in enumerate(pre):
                now=(k*pow(10,i,p)+j)%13
                dp[i][now]=(x+dp[i][now])%p
    else:
        s=int(s)
        for j,x in enumerate(pre):
            now=(s*pow(10,i,p)+j)%13
            dp[i][now]=(x+dp[i][now])%p
#print(dp)
print(dp[N-1][5])

Submission status: Wrong Answer

Solution code:

S=list(input())[::-1]
N=len(S)
p=10**9+7
dp=[[0]*13 for _ in range(N)]
if S[0]!="?":
    dp[0][int(S[0])]+=1
else:
    for i in range(10):
        dp[0][i]+=1


for i in range(1,N):
    pre=dp[i-1]
    s=S[i]
    if s=="?":
        for k in range(0,10):
            for j,x in enumerate(pre):
                now=(k*pow(10,i,p)+j)%13
                dp[i][now]=(x+dp[i][now])%p
    else:
        s=int(s)
        for j,x in enumerate(pre):
            now=(s*pow(10,i,p)+j)%13
            dp[i][now]=(x+dp[i][now])%p
print(dp)
print(dp[N-1][5])

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

S = list(input())
pre = [0]*13
now = [0]*13

if S[0]=="?":
    for i in range(0,10,1):
        pre[(i*pow(10,len(S)-1,13))%13]+=1
else:
    pre[(int(S[0])*pow(10,len(S)-1,13))%13]=1

for i in range(1,len(S),1):
    now =[0]*13
    if S[i]=="?":
        for k in range(0,10,1):
            for j in range(0,13,1):
                now[j] = (now[j] + pre[(j - (k*pow(10,len(S)-i-1,13))%13)%13])%MOD
    else:
        for j in range(0,13,1):
            now[j] = pre[(j - (int(S[i])*pow(10,len(S)-i-1,13))%13)%13]
    
    for j in range(0,13,1):
        pre[j]=now[j]

print(now[5])

Submission status: Wrong Answer

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    MOD=10**9+7
    S=input().strip("\n")
    q=[]
    g=0
    S=S[::-1]
    m13=(1,10,9,12,3,4)
    for i in range(len(S)):
        if S[i] == "?":
            q.append(m13[i%6])
        else:
            g+=m13[i%6]
            g%=13
    N=len(q)
    q=[0]+q
    dp=[[0]*13 for i in range(N+1)]
    dp[0][0]=1
    for i in range(1,N+1):
        for j in range(13):
            for k in range(10):
                x=(j-k*q[i])%13
                dp[i][j]+=dp[i-1][x]
            dp[i][j]%=MOD
    print(dp[N][5])
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int


def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = [0] * 13, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, pre
        for i in range(13): # 再生成を避ける
            cur[i] = 0
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Wrong Answer

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

for i in range(n):
    x=s[-(i+1)]  # 後ろから見ていく
    if x=='?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j)%13]+=dp[i][j]
                dp[i+1][(mul*k+j)%13]%=mod
    else:
        k=int(x)
        for j in range(13):
            dp[i+1][(mul*k+j)%13]+=dp[i][j]
            dp[i+1][(mul*k+j)%13]%=mod
    mul=mul*10%13
print(dp)
print(dp[n][5])

Submission status: Wrong Answer

Solution code:
import numpy as np

S = input()
check = []
ans = 0
plo = np.zeros(13, dtype = int)
N = len(S)
for i in range(N):
    if S[N - 1 - i] == '?':
        check.append(i)
    else:
        ans += int(S[N - 1 - i])*10**i
if len(check) == 0:
    print((ans % 13 == 5) * 1)
else:
    p = check.pop()
    for i in range(10):
        j = (i * 10 ** p) % 13
        plo[j] = 1
    for p in check:
        temp = np.zeros(13, dtype = int)
        for i in range(10):
            j = (i * 10 ** p) % 13
            temp += np.r_[plo[-j:],plo[:-j]]
        plo = temp
        plo = plo % (10**9+7)
l = (5 - ans % 13) % 13
print(plo[l] % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
print "test 2"

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
print "hello"

Submission status: Wrong Answer

Solution code:
s=input()

#i桁以下の数字でmodがjの数
#dp[i][j]=

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

MOD=10**9+7

result=0
for i in range(len(s)):
    index=len(s)-i-1

    if i==0:
        if s[index]!="?":
            #数字,300のmodをtempに
            temp=(int(s[index])*(10**i))%13
            dp[index][temp]=1
        else:
            for l in range(10):
                temp=(l*(10**i))%13
                for j in range(13):
                    k=(temp+j)%13
                    dp[index][k]+=1

    else:
        if s[index]!="?":
            #数字,300のmodをtempに
            temp=(int(s[index])*(10**i))%13
            for j in range(13):
                k=(temp+j)%13
                dp[index][k]+=dp[index+1][j]%MOD
        else:
            for l in range(10):
                temp=(l*(10**i))%13
                for j in range(13):
                    k=(temp+j)%13
                    dp[index][k]+=dp[index+1][j]%MOD
    #print(dp[index],sum(dp[index]))



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

Submission status: Wrong Answer

Solution code:
s=input()

#i桁以下の数字でmodがjの数
#dp[i][j]=

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

MOD=10**9+7

result=0
for i in range(len(s)):
    index=len(s)-i-1

    if i==0:
        if s[index]!="?":
            #数字,300のmodをtempに
            temp=(int(s[index])*(10**i))%13
            dp[index][temp]=1
        else:
            for l in range(10):
                temp=(l*(10**i))%13
                for j in range(13):
                    k=(temp+j)%13
                    dp[index][k]+=1

    else:
        if s[index]!="?":
            #数字,300のmodをtempに
            temp=(int(s[index])*(10**i))%13
            for j in range(13):
                k=(temp+j)%13
                dp[index][k]+=dp[index+1][j]%MOD
        else:
            for l in range(10):
                temp=(l*(10**i))%13
                for j in range(13):
                    k=(temp+j)%13
                    dp[index][k]+=dp[index+1][j]%MOD
    print(dp[index],sum(dp[index]))



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

Submission status: Wrong Answer

Solution code:
s=input()

#i桁以下の数字でmodがjの数
#dp[i][j]=

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

MOD=10**9+7

result=0
for i in range(len(s)):
    index=len(s)-i-1

    if i==0:
        if s[index]!="?":
            #数字,300のmodをtempに
            temp=(int(s[index])*(10**i))%13
            dp[index][temp]=1
        else:
            for l in range(10):
                temp=(l*(10**i))%13
                for j in range(13):
                    k=(temp+j)%13
                    dp[index][k]+=1

    else:
        if s[index]!="?":
            #数字,300のmodをtempに
            temp=(int(s[index])*(10**i))%13
            for j in range(13):
                k=(temp+j)%13
                dp[index][k]+=dp[index+1][j]
        else:
            for l in range(10):
                temp=(l*(10**i))%13
                for j in range(13):
                    k=(temp+j)%13
                    dp[index][k]+=dp[index+1][j]
    #print(dp[index])



print(dp[0][5])

Submission status: Wrong Answer

Solution code:
import numpy as np
S=input()
N=len(S)
mod=10**9+7
dp=[[0]*13 for _ in range(N+1)]
dp=np.array(dp)
S=S[::-1]
dp[0][0]=1
for i in range(1,N+1):
    if i==1:
        p=1
    else:
        p*=10
        p%=mod
    s=S[i-1]
    if s!="?":
        now=(p*int(s))%mod
        idx=(13-now)%13
        add=np.concatenate([dp[i-1][idx:],dp[i-1][:idx]])
        p#rint(add)
        dp[i]+=add%mod
    else:
        for j in range(10):
            now=(p*j)%mod
            idx=(13-now)%13
            #print(idx)
            add=np.concatenate([dp[i-1][idx:],dp[i-1][:idx]])
            #print(add)
            dp[i]+=add%mod
    dp[i]%=mod
#print(dp)
print(dp[N][5])

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

# 初期値
if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1


# dpテーブル更新式
for i in range(1, N):
    si = S[i]
    if si == "?":
        for si_cand in range(10):
            for j in range(13):
                dp[i][(j*10+si_cand)%13] += dp[i-1][j] % MOD
    else:
        for j in range(13):
            dp[i][(j*10+int(si))%13] += dp[i-1][j] % MOD

print(dp[N-1][5])

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i][j]: S[i]までみて13で割ってjあまるものの個数

# 初期値
if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1


# dpテーブル更新式
for i in range(1, N):
    si = S[i]
    if si == "?":
        for si_cand in range(10):
            for j in range(13):
                dp[i][(j*10+si_cand)%13] = dp[i-1][j] % MOD
    else:
        for j in range(13):
            dp[i][(j*10+int(si))%13] = dp[i-1][j] % MOD

print(dp[N-1][5])

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  # dp[i]j]: S[i]までみて13で割ってjあまるものの個数

# 初期値
if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1


# dpテーブル更新式
for i in range(1, N):
    si = S[i]
    if si == "?":
        for si_cand in range(10):
            for j in range(13):
                dp[i][(j*10+si_cand)%13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j*10+int(si))%13] += dp[i-1][j]

print(dp[N-1][5])

Submission status: Wrong Answer

Solution code:
p = 10**9+7
S = input().strip()
A = [[0 for k in range(13)] for j in range(13)]
for j in range(13):
    for k in range(13):
        for m in range(10):
            if (10*k+m)%13==j:
                A[j][k] = 1
                break
B = [[0 for _ in range(10)] for _ in range(13)]
for j in range(13):
    for m in range(10):
        for k in range(13):
            if (10*k+m)%13==j:
                B[j][m] = k
                break
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N+1)]
for j in range(13):
    if S[0]!="?":
        dp[1][j] = (int(S[0])==j)
    else:
        if j<10:
            dp[1][j] = 1
for i in range(2,N+1):
    for j in range(13):
        if S[i-1]!="?":
            dp[i][j] = (dp[i][j]+dp[i-1][B[j][int(S[i-1])]])%p
        else:
            for k in range(13):
                dp[i][j] = (dp[i][j]+dp[i-1][k]*A[j][k])%p
print(dp[N][5])

Submission status: Wrong Answer

Solution code:
p = 10**9+7
S = input().strip()
A = [[0 for k in range(13)] for j in range(13)]
for j in range(13):
    for k in range(13):
        for m in range(10):
            if (10*k+m)%13==j:
                A[j][k] = 1
                break
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N+1)]
for j in range(13):
    if S[0]!="?":
        dp[1][j] = (int(S[0])==j)
    else:
        if j<10:
            dp[1][j] = 1
for i in range(2,N+1):
    for j in range(13):
        if S[i-1]!="?":
            for k in range(13):
                dp[i][j] = (dp[i][j]+dp[i-1][k]*((10*k+int(S[i-1]))%13==j))%p
        else:
            for k in range(13):
                dp[i][j] = (dp[i][j]+dp[i-1][k]*A[j][k])%p
print(dp[N][5])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = inputStr()
	S_len = len(S)

	DP = [[0 for j in range(13)] for i in range(S_len)]
	S = S[::-1]

	for i,val in enumerate(S):
		if i == 0:
			if val == "?":
				for j in range(0,10):
					tmp = (10**i * j) % 13
					DP[i][tmp] += 1
			else:
				tmp = (10**i * int(val)) % 13
				DP[i][tmp] += 1
		else:
			if val == "?":
				for j in range(0,10):
					pass
			else:
				tmp = (10**i * int(val)) % 13
				for j,vol in enumerate(DP[i-1]):
					if vol == 0:
						continue
					tmptmp = (j + tmp) % 13
					DP[i][tmptmp] = (DP[i][tmptmp] + vol) % mod

	#print(DP)
	print(DP[S_len-1][5] % mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    N = len(S)
    dp = [[0] * 13 for _ in range(N)]

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

    tenfactor = 1
    for i in range(1, N):
        tenfactor *= 10
        tenfactor %= MOD

        if S[N - i - 1] != "?":
            for k in range(13):
                j = int(S[N - i - 1])
                idx = (k + j * tenfactor) % 13
                dp[i][idx] += dp[i - 1][k]
                dp[i][idx] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    idx = (k + j * tenfactor) % 13
                    dp[i][idx] += dp[i - 1][k]
                    dp[i][idx] %= MOD

    print(dp[-1][5])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    N = len(S)
    dp = [[0] * 13 for _ 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[N - i - 1] != "?":
            for k in range(13):
                j = int(S[N - i - 1])
                idx = (k + j * (10 ** i)) % 13
                dp[i][idx] += dp[i - 1][k]
                dp[i][idx] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    idx = (k + j * (10 ** i)) % 13
                    dp[i][idx] += dp[i - 1][k]
                    dp[i][idx] %= MOD

    print(dp[-1][5])


if __name__ == "__main__":
    main()