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

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
n = len(s)

class ModInt:
    def __init__(self, n=0, mod=mod):
        self.mod = mod
        self.n = n % self.mod
    
    def value(self):
        return self.n
    
    def __add__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n + rhs.n, self.mod)
        return self.__class__(self.n + rhs, self.mod)
    
    __radd__ = __add__
    
    def __sub__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n - rhs.n, self.mod)
        return self.__class__(self.n - rhs, self.mod)
    
    def __rsub__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n - self.n, self.mod)
        return self.__class__(lhs - self.n, self.mod)

    def __mul__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n * rhs.n, self.mod)
        return self.__class__(self.n * rhs, self.mod)
    
    __rmul__ = __mul__

    def __floordiv__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n // rhs.n, self.mod)
        return self.__class__(self.n // rhs, self.mod)
    
    def __rfloordiv__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n // self.n, self.mod)
        return self.__class__(lhs // self.n, self.mod)

    def __iadd__(self, rhs):
        if isinstance(rhs, ModInt):
            self.n += rhs.n
        else:
            self.n += rhs
        if self.n >= self.mod:
            self.n -= self.mod
        
        return self
    
    def __isub__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        if self.n < rhs_n:
            self.n += self.mod
        self.n -= rhs_n
        return self
    
    def __imul__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        self.n = self.n * rhs_n % self.mod
        return self
    
    def __ifloordiv__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        exp = self.mod - 2
        while exp:
            if exp % 2:
                self *= rhs_n
            
            rhs_n *= rhs_n
            rhs_n %= self.mod
            exp //= 2
        
        return self
    
    def __pow__(self, exp):
        exp_n = exp.n if isinstance(exp, ModInt) else exp
        if exp_n == 0:
            return self.__class__(1, self.mod)
        if exp_n % 2 == 0:
            t = self.__pow__(exp_n // 2)
            return t * t
        return self * self.__pow__(exp_n - 1)
    
    def __str__(self):
        return str(self.n)

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

dp2 = [0] * (n + 7)
dp2[0] = 1
for i in range(n + 6):
    dp2[i + 1] = dp2[i] * 10 % 13

for i in range(n):
    for j in range(13):
        if s[i] != '?':
            dig = int(s[i])
            t = dp2[n - i - 1] * dig + j
            t %= 13
            ni = i + 1
            nj = t
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
        else:
            for k in range(10):
                dig = k
                t = dp2[n - i - 1] * dig + j
                t %= 13
                ni = i + 1
                nj = t
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod

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

Submission status: Accepted

Solution code:
from itertools import accumulate

def solve():
    MOD = 10**9 + 7

    Ss = input()

    dp = [0] * 13
    dp[0] = 1
    for d, Sd in enumerate(Ss):
        dp2 = [0] * 26
        for mod13 in range(13):
            if Sd != '?':
                x = int(Sd)
                mod13n = (10*mod13 + x) % 13
                dp2[mod13n] += dp[mod13]
                dp2[mod13n+1] -= dp[mod13]
            else:
                mod13n = (10*mod13 + 0) % 13
                dp2[mod13n] += dp[mod13]
                dp2[mod13n+10] -= dp[mod13]
        dp2 = list(accumulate(dp2))
        dp = [(a+b) % MOD for a, b in zip(dp2[:13], dp2[13:])]

    print(dp[5])


solve()

Submission status: Accepted

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 %= 13

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

Solution code:
MOD = 10**9 + 7

Ss = input().rstrip()

lenS = len(Ss)

dp = [[0]*(13) for _ in range(lenS+1)]
dp[0][0] = 1
for i, S in enumerate(Ss):
    for j in range(13):
        dp[i][j] %= MOD
    if S != '?':
        S = int(S)
        for j in range(13):
            j2 = (j*10+S) % 13
            dp[i+1][j2] += dp[i][j]
    else:
        for S in range(10):
            for j in range(13):
                j2 = (j*10+S) % 13
                dp[i+1][j2] += dp[i][j]

ans = dp[lenS][5] % MOD
print(ans)

Submission status: Accepted

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

A = []
a = 1
for i in range(l):
    A.append(a)
    a = (10*a) % 13

A.reverse()

dp = [[0]*13 for i in range(l)]

for i in range(l):
    for j in range(13):
        if i == 0:
            if S[i] != '?':
                dp[i][(int(S[i])*A[i]) % 13] = 1
            else:
                for k in range(10):
                    dp[i][(k*A[i]) % 13] = 1
        else:
            if S[i] != '?':
                dp[i][j] = dp[i-1][(j-int(S[i])*A[i]) % 13]
            else:
                for k in range(10):
                    dp[i][j] += dp[i-1][(j-k*A[i]) % 13]
                    dp[i][j] = (dp[i][j]) % mod
print(dp[l-1][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
S= input()
N = len(S)

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res
dp = dpinit((N+1,13))

res = [(i*10) % 13 for i in range(13)]

dp[0][0] = 1
for i in range(1,N+1):
    s = S[i-1]
    if s != '?':
        s = int(s)
        for k in range(13):
            new = (res[k] + s) % 13
            dp[i][new] += dp[i-1][k]
    else:
        for s in range(10):
            for k in range(13):
                new = (res[k] + s) % 13
                dp[i][new] += dp[i-1][k]
    for k in range(13):
        dp[i][k] %= MOD
print(dp[N][5])

Submission status: Accepted

Solution code:
s = input()
n = len(s)
MOD = 10 ** 9 + 7

# 先頭i文字としてあり得る数のうち、13で割ったあまりがjである個数
dp = [[0] * 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 d in range(10):
        if c != -1 and c != d:
            continue
        for j in range(13):
            dp[i+1][(10*j+d)%13] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD
    
print(dp[n][5])

Submission status: Accepted

Solution code:
s=input()
n=len(s)
ten=[1]
p=1
mod=10**9+7
for i in range(n-1):
    p*=10
    p%=13
    ten.append(p)
ten=ten[::-1]
dp=[0]*13
dp[0]=1
for t,c in zip(ten,s):
    newdp=[0]*13
    if c!='?':
        c=t*int(c)%13
        for i in range(13):
            newdp[(i+c)%13]=dp[i]
    else:
        for c in range(10):
            c*=t
            for i in range(13):
                newdp[(i+c)%13]+=dp[i]
                newdp[(i+c)%13]%=mod
    dp=newdp

print(newdp[5])

Submission status: Accepted

Solution code:
M=10**9+7
s=input()
r=range
k=[1]+[0]*12
for c in s:
  l=[0]*13
  for i in r(13):
    if c=='?':
      for j in r(10): l[(i*10+j)%13]+=k[i]
    else: l[(i*10+int(c))%13]+=k[i]
  for i in r(13): k[i]=l[i]%M
print(k[5])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(len(S)):
  s = S[-(i+1)]
  if s == "?":
    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(s)
    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[len(S)][5])

Submission status: Accepted

Solution code:
s=list(input())
s.reverse()
MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
    nd=s[i]
    p=pow(10,i,13)
    for mod in range(13):
        dp[i][mod] %=MOD
        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*p + mod) % 13
            dp[i+1][nmod] += dp[i][mod]

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

Submission status: Accepted

Solution code:
s = input()

n = len(s)
mod = 10**9+7

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

for i in range(n):
    if s[-1-i]=='?':
        p = [x*pow(10,i,13) for x in range(0,10)]
    else:
        p = [int(s[-1-i])*pow(10,i,13)]
    for j in range(13):
        for x in p:
            dp[i+1][(j+x)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=mod

print(dp[-1][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
n = len(s)
MOD = 10**9 + 7
dp = [[0]*13 for _ in range(n+1)]
# dp[i][j]は先頭からi文字目を見た時の13でわったあまりがjのものの数

dp[0][0] = 1
#print(dp[0])
for i in range(n):
    if s[i] != "?":
        for j in range(13):
            dp[i+1][(10*j+int(s[i])) % 13] = dp[i+1][(10*j+int(s[i])) % 13] + dp[i][j] % MOD
    else:
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j+k) % 13] = dp[i+1][(10*j+k) % 13] + dp[i][j] % MOD
print(dp[n][5]%MOD)

Submission status: Accepted

Solution code:



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

# dp[i+1][j] : 左からi番目の文字まで見たときに、13で割ってj余る場合の数
dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1


"""
数字がabcで並んでいて、それを13で割った時の余りがpのときに、末尾にdが追加されると、
abcd = abc * 10 + d だから、これを13で割った余りは、 p*10 % 13 + d % 13 = (10 * p + d) % 13

"""

for i in range(N):
    for j in range(13):
        if S[i] == "?":
            # 0~9
            for n in range(10):
                dp[i+1][(10 * j + n) % 13] += dp[i][j]
                if dp[i+1][(10 * j + n) % 13] >= MOD:
                    dp[i+1][(10 * j + n) % 13] %= MOD
        else:
            dp[i+1][(10 * j + int(S[i])) % 13] += dp[i][j]
            if dp[i+1][(10 * j + int(S[i])) % 13] >= MOD:
                dp[i+1][(10 * j + int(S[i])) % 13] %= MOD


print(dp[-1][5])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
amari = [i for i in range(10)]
p = 10**9 + 7
s =  str(input())
n = len(s)
ans = [0]*13
ans[0] = 1
for i in reversed(s):
  dp = [0]*13
  if i == '?':
    for j in range(13):
      for k in amari:
        dp[(j + k)%13] += ans[j]
  else:
    for j in range(13):
      dp[(j + amari[int(i)])%13] += ans[j]
      
  for i in range(len(dp)):
    dp[i] %= p
  ans = dp
  for i in range(len(amari)):
    amari[i] = amari[i]*10%13
print(ans[5])

Submission status: Accepted

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

MOD = 10 ** 9 + 7

# dp[i][j] i桁までで、あまりjの個数
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
  if s == "?":
    c = -1
  else:
    c = int(s)
  for j in range(10):
    if c != -1 and c != j:
      continue
    for k in range(13):
      dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= MOD
print(dp[n][5])

Submission status: Accepted

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

dp[0][0]=1 #初期値設定
for i in range(l):
  if s[i]!="?":
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
  else:
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
        
print(dp[-1][5]%mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、
j:前からi文字みたとき、13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
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]=='?': #?のときは各値(0～9)について更新する
   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[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答

Submission status: Accepted

Solution code:
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
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]=='?': #?のときは各値(0～9)について更新する
   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[-1][5]%mod) 
#最後まで更新を行ったときのあまりが5となる数の個数が答

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = readline().rstrip().decode()
mod = 10 ** 9 + 7
ans = [0] * 13
ans[0] = 1
for check in s:
    dp = [0] * 13
    for i in range(13):
        dp[(i * 10) % 13] = ans[i] % mod
    dp += dp
    for i in range(13):
        if check == '?':
            ans[i] = sum(dp[i + 4:i + 14])
        else:
            ans[i] = dp[i - int(check)]
print(ans[5] % mod)

Submission status: Accepted

Solution code:
inf = 10 ** 9 + 7
s = input()
n = len(s)
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] %= inf
    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] %= inf
    mul = mul * 10 % 13
print(dp[n][5])

Submission status: Accepted

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

MOD = 10**9+7

dp = []

for i in range(N+1):
  dp.append([0]*13)

dp[0][0] =1

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

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

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

Submission status: Accepted

Solution code:

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

"""
桁DPについて、S以下の数字で～の場合は
dp[i][j][k] : i桁目まで見たときに、その数字がSのj桁までより厳密に小さいか（一致する場合は0）、そこまでの値の13で割った時の値がkとなる個数（？をうめる方法の数）
といつもはしていたが、今回はSの中の？を埋める問題なので、jの厳密に一致するかどうかがいらない
なので、dp[i][j]は、i桁目まで見たときに、そこまでを13で割った時に13余るように？を決める方法の数
"""
dp = [[0 for _ in range(13)] for _ in range(N+1)]

# 0文字目まで見たときに13で割って余りが0になるのは１通り
dp[0][0] = 1

for i in range(N):
    for j in range(13):
        if S[i] == "?":
            # ?には0~9のいずれかを入れる
            for num in range(10):
                dp[i+1][(10*j + num) % 13] += dp[i][j]
                dp[i+1][(10*j + num) % 13] %= MOD
        
        # i文字目が13でない場合は
        else:
            # i番目の数字を13で割った余り
            num = ord(S[i]) - ord("0")
            dp[i+1][(10*j + num) % 13] += dp[i][j]
            dp[i+1][(10*j + num) % 13] %= MOD


print(dp[-1][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = (amari[i] * 10) % 13

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])

Submission status: Accepted

Solution code:
# 解説AC
MOD = 10**9 + 7


def main():
    S = [s for s in input()[::-1]]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    d = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*d)+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*d)+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
        d *= 10
        d %= 13
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# solution

modulous=10**9+7
r=[[(j-i)*4%13 for i in range(10)]for j in range(13)]
d=[1]+[0]*12
for c in input():
  if c>"9":
    d=[(sum(d[i] for i in j))%modulous for j in r]
  else:
    d=[d[((j-int(c))*4%13)] for j in range(13)]
    
print(d[5])

Submission status: Accepted

Solution code:
import sys
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )
#
dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    #
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        #
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    if j==5: j=0
    else: j+=1
#
print(dp[5])

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    n = len(s)
    s = list(reversed(s))
    determined = 0    # 確定枠 (mod 13)
    # 2, 3, 5 と入っていたら s*10^2, t*10^3, u*10^5 をたすことができる (s,t,u=0~9) というようにデータの保存も可能
    # 一歩進めて mod を先に取ろう
    L = []
    for i in range(n):
        if s[i] != '?':
            determined += pow(10, i, 13) * int(s[i])
            determined %= 13
        else:
            L.append(pow(10, i, 13))
    # print(determined)
    # print(L)
    # elm in L に 0~9 をかけて (mod 13)、この余りを作れるような組み合わせを考えれば良い
    target_res = ((13+5) - determined) % 13
    m = len(L)
    if m == 0:
        print(1) if target_res == 0 else print(0)
    else:
        # dp[i][j] = L の i 番目 (0-ind) までの数を用いて (0~9 を自在に掛け合わせて) mod 13 で j にできるような組み合わせの数
        dp = [[0] * 13 for _ in range(m)]
        first_line = [(L[0] * x) % 13 for x in range(10)]
        for j in range(13):
            dp[0][j] = first_line.count(j)
        for i in range(1, m):
            for j in range(13):
                elm = L[i]
                for x in range(10):
                    tmp = (x * elm) % 13
                    j_prime = (j + 13 - tmp) % 13
                    dp[i][j] += dp[i-1][j_prime]
                    dp[i][j] %= mod
        print(dp[m-1][target_res])

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s=input()
n=len(s)
arr=[]
cnt=0
mod=10**9+7
rem=[1,10,9,12,3,4]
for i in reversed(range(n)):
  if s[i]=='?':
    arr.append(rem[(n-i)%6-1])
  else:
    cnt+=rem[(n-i)%6-1]*int(s[i])
    cnt%=13
#print(arr)
#print(cnt)
if arr:
  m=len(arr)
  dp=[[0]*13 for _ in range(m)]
  for i in range(10):
    dp[0][i*arr[0]%13]+=1
  for i in range(1,m):
    for j in range(13):
      for k in range(10):
        dp[i][(k*arr[i]+j)%13]+=dp[i-1][j]
        dp[i][(k*arr[i]+j)%13]%=mod
  #print(dp)
  for i in range(13):
    if (cnt+i)%13==5:
      print(dp[m-1][i]%mod)
      exit()
else:
  if cnt==5:
    print(1)
  else:
    print(0)

Submission status: Accepted

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

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

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

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

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

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

if __name__ == '__main__':
	main()

Submission status: Accepted

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

    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

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

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


if __name__ == '__main__':
    main()