Problem:


Score : 100 points

Problem Statement

Find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo 10^9 + 7:

The sum of the digits in base ten is a multiple of D.

Constraints

All values in input are integers.

1 \leq K < 10^{10000}

1 \leq D \leq 100

Input

Input is given from Standard Input in the following format:

K
D

Output

Print the number of integers satisfying the condition, modulo 10^9 + 7.

Sample Input 1

30
4

Sample Output 1

6

Those six integers are: 4, 8, 13, 17, 22 and 26.

Sample Input 2

1000000009
1

Sample Output 2

2

Be sure to print the number modulo 10^9 + 7.

Sample Input 3

98765432109876543210
58

Sample Output 3

635270834



Sample input:
30
4


Sample output:
6

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    K=[int(i) for i in ST()]
    D=I()
    N=len(K)
    dp = [[[ModInt(0)]*D for _ in range(2)] for _ in range(N+1)] # dp[i][less][j]:=i桁目までで桁和j(mod D)、でなんパターンあるか

    dp[0][0][0]+=1
    for i in range(N):
        for less in range(2):
            limit = 10 if less else K[i]+1
            for d in range(D):
                for j in range(limit):
                    if less or j!=limit-1:
                        dp[i+1][1][(d+j)%D] += dp[i][less][d]
                    else:
                        dp[i+1][0][(d+j)%D] += dp[i][less][d]
    print(dp[-1][0][0] + dp[-1][1][0] - 1) #0の分


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K, = map(int, input().split())
D, = map(int, input().split())
N = len(str(K))
M = 10**9+7
dp = [[0]*D for _ in range(N+1)]
dp2 = [[0]*D for _ in range(N+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1, N+1):
    Ki = K%10
    K //= 10
    for j in range(D):
        for k in range(10):
            dp[i][(j+k)%D] += dp[i-1][j]
            dp[i][(j+k)%D] %= M
        for k in range(Ki):
            dp2[i][(j+k)%D] += dp[i-1][j]
            dp2[i][(j+k)%D] %= M
        dp2[i][(j+Ki)%D] += dp2[i-1][j]
        dp2[i][(j+Ki)%D] %= M
print((dp2[N][0]-1)%M)

Submission status: Accepted

Solution code:
K, = map(int, input().split())
D, = map(int, input().split())
N = len(str(K))
M = 10**9+7
dp = [[0]*D for _ in range(N+1)]
dp2 = [[0]*D for _ in range(N+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1, N+1):
    Ki = K%10
    K //= 10
    for j in range(D):
        for k in range(10):
            dp[i][(j+k)%D] = (dp[i][(j+k)%D] + dp[i-1][j])%M
        for k in range(Ki):
            dp2[i][(j+k)%D] = (dp2[i][(j+k)%D] + dp[i-1][j])%M
        dp2[i][(j+Ki)%D] = (dp2[i][(j+Ki)%D] + dp2[i-1][j])%M
print((dp2[N][0]-1)%M)

Submission status: Accepted

Solution code:
K = input()
D = int(input())

mod = 10**9+7
N = len(K)
dp0 = [[0]*D for _ in range(N)]
dp1 = [[0]*D for _ in range(N)]

for k in range(int(K[0])):
    dp1[0][k%D] += 1
dp0[0][int(K[0])%D] += 1

for i in range(N-1):
    for j in range(D):
        for k in range(10):
            dp1[i+1][(j+k)%D] += dp1[i][j]
            dp1[i+1][(j+k)%D] %= mod
        for k in range(int(K[i+1])):
            dp1[i+1][(j+k)%D] += dp0[i][j]
            dp1[i+1][(j+k)%D] %= mod
        dp0[i+1][(j+int(K[i+1]))%D] += dp0[i][j]
        dp0[i+1][(j+int(K[i+1]))%D] %= mod

print((dp1[N-1][0]+dp0[N-1][0]-1)%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
k = input()
d = int(input())

l = len(k)

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

dp[0][0] = 1
dp2[0][0] = 1

for i in range(1, l+1):
    if i == 1:
        for p in range(10):
            if p > int(k[i-1]):
                continue
            for j in range(d):
                if p < int(k[i-1]):
                    dp[i][(j+p) % d] += dp[i-1][j]
                    dp[i][(j+p) % d] %= mod
                elif p == int(k[i-1]):
                    dp2[i][(j+p) % d] += dp2[i-1][j]
                    dp2[i][(j+p) % d] %= mod
        continue

    for p in range(10):
        for j in range(d):
            dp[i][(j+p) % d] += dp[i-1][j]
            dp[i][(j+p) % d] %= mod

        if p > int(k[i-1]):
            continue

        for j in range(d):
            if p < int(k[i-1]):
                dp[i][(j+p) % d] += dp2[i-1][j]
                dp[i][(j+p) % d] %= mod
            elif p == int(k[i-1]):
                dp2[i][(j+p) % d] += dp2[i-1][j]
                dp2[i][(j+p) % d] %= mod

print((dp[l][0]+dp2[l][0]-1) % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def array(*args, initial=0):
    def forstr(N):
        return "[{} for _ in range("+str(N)+")]"

    a = args[-1]
    ans = eval(forstr(a).format(initial))
    if len(args) == 1:
        return ans
    else:
        return array(*args[:-1], initial=ans)


def solve(K: int, D: int):
    K = str(K)
    N = len(str(K))
    DP = array(N+1, 2, D, initial=0)
    DP[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            lim = 9 if j else int(K[i])
            for k in range(D):
                for d in range(lim+1):
                    DP[i+1][j or d < lim][(k+d) % D] += DP[i][j][k]
                    DP[i+1][j or d < lim][(k+d) % D] %= MOD
    print((DP[N][0][0]+DP[N][1][0]-1) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(K, D)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    K = input()
    D = int(input())
    L = len(K)
    dp = [[[0, 0] for _ in range(D)] for _ in range(L+1)]
    mod = 10 ** 9 + 7
    dp[0][0][1] = 1
    for i in range(L):
        d = int(K[i])
        for j in range(D):
            for k in range(10):
                dp[i+1][(j + k) % D][0] += dp[i][j][0]
                dp[i+1][(j + k) % D][0] %= mod
                if k < d:
                    dp[i+1][(j + k) % D][0] += dp[i][j][1]
                    dp[i+1][(j + k) % D][0] %= mod
                elif k == d:
                    dp[i+1][(j + k) % D][1] += dp[i][j][1]
                    dp[i+1][(j + k) % D][1] %= mod
    print((sum(dp[-1][0]) + mod - 1) % mod)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
k=input()
d=int(input())
m=10**9+7
t=np.zeros(d)
s=0
for i in k:
    p=np.zeros(d)
    for j in range(10):
        p+=np.hstack([t[-(j%d):],t[:-(j%d)]])
    for j in range(int(i)):
        p[(s+j)%d]+=1
    t=p[::]%m
    s+=int(i)
t[s%d]+=1
print((int(t[0])-1)%m)

Submission status: Accepted

Solution code:
k = input()
len_k = len(k)
d = int(input())
MOD = 10**9 + 7

dp = [[[0]*d for i in range(len_k+1)] for i in range(2)]
dp[1][0][0] = 1

for i in range(len_k):
    for j in range(d):
        dp[1][i+1][(j+int(k[i])) % d] += dp[1][i][j]
        dp[1][i+1][(j+int(k[i])) % d] %= MOD
        for l in range(int(k[i])):
            dp[0][i+1][(j+l) % d] += dp[1][i][j]
            dp[0][i+1][(j+l) % d] %= MOD
        for l in range(10):
            dp[0][i+1][(j+l) % d] += dp[0][i][j]
            dp[0][i+1][(j+l) % d] %= MOD

print((dp[0][-1][0] + dp[1][-1][0] - 1) % MOD)

Submission status: Accepted

Solution code:
K = int(input())
D = int(input())
mod = 10**9 + 7

dp = [[[0] * D for _ in range(2)] for _ in range(len(str(K))+1)]
dp[0][0][0] = 1

for i in range(len(str(K))):
    N = int(str(K)[i])
    for j in range(2):
        for k in range(D):
            for n in range((9 if j == 1 else N) + 1):
                dp[i+1][j or n < N][(k+n%D)%D] += dp[i][j][k]%mod

print((dp[-1][0][0]+dp[-1][1][0]-1)%mod)

Submission status: Accepted

Solution code:
K = input()
D = int(input())
N = len(K)
mod = 10**9+7

dp0 = [[0] * D for _ in range(N+1)]
dp1 = [[0] * D for _ in range(N+1)]
dp0[0][0] = 1
for i in range(N):
    k = int(K[i])
    for j in range(D):
        dp0[i+1][(j+k)%D] = (dp0[i+1][(j+k)%D] + dp0[i][j]) % mod
        dp1[i+1][(j+k)%D] = (dp1[i+1][(j+k)%D] + dp1[i][j]) % mod
        for k_ in range(k):
            dp1[i+1][(j+k_)%D] = (dp1[i+1][(j+k_)%D] + dp0[i][j] + dp1[i][j]) % mod
        for k_ in range(k+1, 10):
            dp1[i + 1][(j + k_) % D] = (dp1[i + 1][(j + k_) % D] + dp1[i][j]) % mod

print((dp0[-1][0] + dp1[-1][0] - 1) % mod)

Submission status: Accepted

Solution code:
import sys
from math import log10, floor
K = input()
d = int(input())
digit_num = len(K)
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(K, 1):
    n = int(n)
    for j in range(10):
        for k in range(d):
            _from = (k - j) % d
            memo_ls[i][k][1] = (memo_ls[i][k][1] + memo_ls[i-1][_from][1]) % MOD
            if j == n:
                memo_ls[i][k][0] = (memo_ls[i-1][_from][0] + memo_ls[i][k][0]) % MOD
            elif j < n:
                memo_ls[i][k][1] = (memo_ls[i-1][_from][0] + memo_ls[i][k][1]) % MOD
print((sum(memo_ls[digit_num][0]) - 1) % MOD)

Submission status: Accepted

Solution code:
modulo = 10 ** 9 + 7

k = str(input())
digits = len(k)
d = int(input())

matrix = []

for i in range(10005):
    matrix.append([[0, 0] for j in range(d)])
    
matrix[0][0][1] = 1

for i, digit in enumerate(k):
    digit = int(digit)
    #print(digit)
    
    for j in range(d):
        
        for k in range(10):
            aux = (j - k) % d
            matrix[i+1][j][0] = (matrix[i+1][j][0] + matrix[i][aux][0]) % modulo
        aux = (j - digit) % d
        matrix[i+1][j][1] = matrix[i+1][j][1] + matrix[i][aux][1]
        
        for k in range(digit):
            aux = (j - k) % d
            matrix[i+1][j][0] = (matrix[i+1][j][0] + matrix[i][aux][1]) % modulo
            
result = (matrix[digits][0][0] + matrix[digits][0][1] - 1) % modulo
print(result, end='\n')

Submission status: Accepted

Solution code:
MOD=1000000007
K=input()
n=len(K)
D=int(input())

dp=[[[0,0] for j in range(D)] for i in range(10005)]
dp[0][0][1]=1

for i in range(n):
    num = int(K[i])
    for j in range(D):
        for k in range(10):
            dp[i+1][j][0]+=dp[i][(j-k)%D][0]
            dp[i+1][j][0]%=MOD
        dp[i+1][j][1]+= dp[i][(j-num)%D][1]
        for k in range(num):
            dp[i+1][j][0]+=dp[i][(j-k)%D][1]
            dp[i+1][j][0]%=MOD
print((dp[n][0][0]+dp[n][0][1]-1)%MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    k = [int(c) for c in input()]
    n=len(k)
    d = int(input())
    dp = [[0] * d for _ in range(n)]
    for b in range(k[0]):
        dp[0][b % d] += 1
    border = k[0]
    dpi = dp[0]
    for i, a in enumerate(k[1:], 1):
        dpi1 = dpi
        dpi = dp[i]
        for j in range(d):
            pre = dpi1[j]
            if pre == 0: continue
            for b in range(10):
                nj = (j + b) % d
                dpi[nj] = (dpi[nj] + pre) % md
        for b in range(a):
            nj = (border + b) % d
            dpi[nj] += 1
        border = (border + a) % d

    #p2D(dp)
    ans = dp[n-1][0] - 1 + (border % d == 0)
    print(ans % md)

main()

Submission status: Accepted

Solution code:
mod = 10**9+7
K = input()
n = len(K)
D = int(input())
dp = [[[0]*2 for i in range(D)] for _ in range(n)]
for i in range(int(K[0])):
    dp[0][i%D][0] += 1
dp[0][int(K[0])%D][1] += 1
for i in range(n-1):
    for j in range(D):
        for d in range(10):
            dp[i+1][(j+d)%D][0]+=dp[i][j][0]
            dp[i+1][(j+d)%D][0]%=mod
        for d in range(int(K[i+1])):
            dp[i+1][(j+d)%D][0]+=dp[i][j][1]
            dp[i+1][(j+d)%D][0]%=mod
        dp[i+1][(j+int(K[i+1]))%D][1] += dp[i][j][1]
        dp[i+1][(j+int(K[i+1]))%D][1]%=mod
print((dp[-1][0][0]+dp[-1][0][1]-1)%mod)

Submission status: Accepted

Solution code:
K = int(input())
D = int(input())
mod = 10**9 + 7

dp = [[[0] * D for _ in range(2)] for _ in range(len(str(K))+1)]
dp[0][0][0] = 1

for i in range(len(str(K))):
    N = int(str(K)[i])
    for j in range(2):
        for k in range(D):
            for n in range((9 if j == 1 else N) + 1):
                dp[i+1][j or n < N][(k+n%D)%D] += dp[i][j][k]%mod

print((dp[-1][0][0]+dp[-1][1][0]-1)%mod)

Submission status: Accepted

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

import numpy as np
import itertools

K = list(map(int,readline().rstrip().decode('utf-8')))
D = int(read())

MOD = 10**9 + 7

Kcum = list(itertools.accumulate(K))

x = np.zeros(D,np.int64)
x[0] = 1
answer = 0
for kc,k in zip(Kcum[::-1],K[::-1]):
    for i in range(kc-k,kc):
        rest = (-i)%D
        answer += x[rest]
    y = np.zeros(D+10,np.int64)
    y[:D] = x
    y[10:] -= x
    np.cumsum(y,out=y) # 1-xで割る
    for d in range(D,D+10):
        y[d%D] += y[d]
    x = y[:D] % MOD

answer -= 1 # 0
if Kcum[-1]%D==0:
    answer += 1

answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    k=input()
    d=int(input())
    n=len(k)
    dp=[[[0]*2 for _ in range(d)] for _ in range(n+1)]
    dp[0][0][0]=1
    for i in range(n):
        a=int(k[i])
        for j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                dp[i+1][(j+o)%d][1]%=MOD
                if(o<a):
                    dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                    dp[i+1][(j+o)%d][1]%=MOD
                elif(o==a):
                    dp[i+1][(j+o)%d][0]+=dp[i][j][0]
                    dp[i+1][(j+o)%d][0]%=MOD
    print((dp[n][0][0]+dp[n][0][1]-1)%MOD)
resolve()

Submission status: Accepted

Solution code:
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
from itertools import accumulate
#10**9+7
mod=1000000007


k=input()
d=int(input())
dp=[0]*(d+10)
dp2=0

for c in k:
    c=int(c)
    for e in range(d-1,-1,-1):
        dp[e+10]-=dp[e]
    dp[dp2]+=1
    dp[dp2+c]-=1
    dp=list(accumulate(dp))
    for e in range(9,-1,-1):
        dp[e]+=dp[d+e]
        dp[d+e]=0
    for e in range(d):
        dp[e]%=mod
    dp2=(dp2+c)%d
ans=dp[0]-1
if dp2==0:
    ans+=1
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def ketadp3(a, b):
    L = len(a)

    dp = [[[0 for i in range(2)] for j in range(b)] for k in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = int(a[i])
        for k in range(b):
            for j in range(2):
                for d in range(10 if j else D+1):
                    dp[i + 1][(k + d) % b][j or (d < D)] += dp[i][k][j]
                    dp[i + 1][(k + d) % b][j or (d < D)] %= MOD

    print((dp[L][0][0] + dp[L][0][1] - 1) % MOD)


def main():
    n = input()
    d = int(input())
    ketadp3(n, d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
#桁DP
#0 ~ K[0] - 1までの数をトップとする場合
for i in range(int(K[0])):
  dp[0][i % D] += 1
#tightは上限付近の制御に使う
#K[0]をトップとする場合がtight
#tightは上限ギリギリを攻める
tight = int(K[0]) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
    #Kを超えないようにしている
    for k in range(int(K[i + 1])):
      dp[i + 1][(tight + k) % D] += 1
    #上から(i + 1)桁まで見たもので、上限ギリギリのものの剰余
    tight = (tight + int(K[i + 1])) % D
#tightは最終的に上限の剰余に一致するので、0でないならその分を除く
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
K = input()
D = int(input())
N = len(K)
dp = [[0] * D for i in range(N)]
for i in range(int(K[0])):
    dp[0][i%D] += 1
tight = int(K[0])%D
for i in range(1, N):
    for j in range(D):
        for k in range(10):
            dp[i][j] += dp[i-1][(j-k)%D]
            dp[i][j] %= mod
    for k in range(int(K[i])):
        dp[i][(tight+k)%D] += 1
    tight = (tight+int(K[i]))%D
print((dp[N-1][0]+(tight==0)-1)%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    def f(n):
        a = str(n)
        l = len(a)
        dp = [[[0]*2 for i in range(2)] for j in range(l+1)]
        dp[0][0][0] = 1
        for i in range(l):
            ni = i+1
            for j in range(2):
                x = 9 if j else int(a[i])
                for k in range(2):
                    for d in range(x+1):
                        nj = j|(d < int(a[i]))
                        nk = k|(d in (4,9))
                        dp[ni][nj][nk] += dp[i][j][k]
        return dp[l][0][1]+dp[l][1][1]

    a,b = LI()
    print(f(b)-f(a-1))
    return

#B
def B():
    D = I()
    n = list(map(int, input()))
    l = len(n)
    dp = [[[0]*2 for i in range(D)] for j in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(D):
            for k in range(2):
                x = 9 if k else int(n[i])
                for d in range(x+1):
                    nj = (j+d)%D
                    nk = k|(d < int(n[i]))
                    dp[ni][nj][nk] += dp[i][j][k]
                    dp[ni][nj][nk] %= mod
    print((dp[l][0][0]+dp[l][0][1]-1)%mod)
    return

#C
def C():
    n = list(map(int, input()))
    l = len(n)
    dp = [[[0]*2 for j in range(l+1)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(l):
            for k in range(2):
                x = 9 if k else n[i]
                for d in range(x+1):
                    nj = j+(d == 1)
                    nk = k|(d < n[i])
                    dp[ni][nj][nk] += dp[i][j][k]
    ans = 0
    for i in range(l+1):
        ans += i*sum(dp[l][i])
    print(ans)
    return

#D
def D():
    n = list(map(int, input()))
    l = len(n)
    D = I()
    dp = [[[0]*2 for i in range(D)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        for j in range(D):
            for k in range(2):
                x = 9 if k else n[i]
                for d in range(x+1):
                    ni = i+1
                    nj = (j+d)%D
                    nk = k|(d<n[i])
                    dp[ni][nj][nk] += dp[i][j][k]
                    dp[ni][nj][nk] %= mod
    print((sum(dp[l][0])-1)%mod)
    return

#E
def E():
    n,k = LI()
    a = LI()
    m = max(k,max(a)).bit_length()
    f = [0]*m
    for i in a:
        for j in range(m):
            if i&(1<<j):
                f[j] += 1
    dp = [[-float("inf")]*2 for i in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        ni = i+1
        ki = (k>>(m-i-1))&1
        for j in range(2):
            x = 1 if j else ki
            for d in range(x+1):
                nj = j|(d<ki)
                dp[ni][nj] = max(dp[ni][nj], dp[i][j]+(d*(n-f[m-i-1])+(1-d)*f[m-i-1])*(1<<(m-i-1)))
    print(max(dp[m]))
    return

#F
def F():
    def bit_count(n):
        return bin(n).count("1")
    a,K = LI()
    a = list(map(int, str(a)))
    l = len(a)
    m = 1024
    dp = [[[float("inf")]*2 for j in range(m)] for i in range(l+1)]
    dp[0][0][0] = 0
    for i in range(l):
        ni = i+1
        for j in range(m):
            if bit_count(j) > K:continue
            for k in range(2):
                x = 9 if k else a[i]
                for d in range(x+1):
                    nj = j|(1<<d)
                    nk = k|(d<a[i])
                    c = dp[i][j][k]*10+a[i]-d
                    if c < dp[ni][nj][nk]:
                        dp[ni][nj][nk] = c
    ans = float("inf")
    for i in range(m):
        if bit_count(i) <= K:
            mi = min(dp[l][i])
            if mi < ans:
                ans = mi
    dp = [[[float("inf")]*2 for j in range(m)] for i in range(l+1)]
    dp[0][0][0] = 0
    for i in range(l):
        ni = i+1
        for j in range(m):
            if bit_count(j) > K:continue
            for k in range(2):
                x = 0 if k else a[i]
                for d in range(x,10):
                    nj = j|(1<<d)
                    nk = k|(d>a[i])
                    c = dp[i][j][k]*10+d-a[i]
                    if c < dp[ni][nj][nk]:
                        dp[ni][nj][nk] = c
    for i in range(m):
        if bit_count(i) <= K:
            mi = min(dp[l][i])
            if mi < ans:
                ans = mi
    print(ans)
    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

#K
def K():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    def f(n):
        a = str(n)
        l = len(a)
        dp = [[[0]*2 for i in range(2)] for j in range(l+1)]
        dp[0][0][0] = 1
        for i in range(l):
            ni = i+1
            for j in range(2):
                x = 9 if j else int(a[i])
                for k in range(2):
                    for d in range(x+1):
                        nj = j|(d < int(a[i]))
                        nk = k|(d in (4,9))
                        dp[ni][nj][nk] += dp[i][j][k]
        return dp[l][0][1]+dp[l][1][1]

    a,b = LI()
    print(f(b)-f(a-1))
    return

#B
def B():
    D = I()
    n = list(map(int, input()))
    l = len(n)
    dp = [[[0]*2 for i in range(D)] for j in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(D):
            for k in range(2):
                x = 9 if k else int(n[i])
                for d in range(x+1):
                    nj = (j+d)%D
                    nk = k|(d < int(n[i]))
                    dp[ni][nj][nk] += dp[i][j][k]
                    dp[ni][nj][nk] %= mod
    print((dp[l][0][0]+dp[l][0][1]-1)%mod)
    return

#C
def C():
    n = list(map(int, input()))
    l = len(n)
    dp = [[[0]*2 for j in range(l+1)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(l):
            for k in range(2):
                x = 9 if k else n[i]
                for d in range(x+1):
                    nj = j+(d == 1)
                    nk = k|(d < n[i])
                    dp[ni][nj][nk] += dp[i][j][k]
    ans = 0
    for i in range(l+1):
        ans += i*sum(dp[l][i])
    print(ans)
    return

#D
def D():
    n = list(map(int, input()))
    l = len(n)
    D = I()
    dp = [[[0]*2 for i in range(D)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        for j in range(D):
            for k in range(2):
                x = 9 if k else n[i]
                for d in range(x+1):
                    ni = i+1
                    nj = (j+d)%D
                    nk = k|(d<n[i])
                    dp[ni][nj][nk] += dp[i][j][k]
                    dp[ni][nj][nk] %= mod
    print((sum(dp[l][0])-1)%mod)
    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#J
def J():

    return

#K
def K():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
K = input()
D = int(input())

#dp[桁][余り][未満flag]
dp = [[[0 for k in range(2)] for j in range(D)] for i in range(len(K)+1)]
dp[0][0][0] = 1
s = 0
for i in range(len(K)):
    n = int(K[i])
    dp[i+1][(s+n)%D][0] = dp[i][s%D][0]
    s += n
    for j in range(D):
        for k in range(10):
            if k < n:
                dp[i+1][(j+k)%D][1] += dp[i][j][0]
            dp[i+1][(j+k)%D][1] += dp[i][j][1]
            dp[i+1][(j+k)%D][1] %= 1000000007

print(sum(dp[len(K)][0], -1)%1000000007)

Submission status: Accepted

Solution code:
K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)

Submission status: Accepted

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

import numpy as np
from numpy.fft import rfft, irfft
MOD = 10 ** 9 + 7
K = [int(x) for x in input().rstrip()]
L = len(K)
D = int(input())

def convolve_ones(x,arr):
    # 0,1,...,x-1
    after = np.zeros(D+x,dtype=np.int64)
    for i in range(x):
        after[i:i+D] += arr
    for i in range(D,D+x):
        after[i%D]+= after[i]
    return after[:D] % MOD

# d桁以下、自由に使った場合の余りごとの個数。0を含めて数えておく
full = [np.zeros(D, dtype=np.int64)]
full[0][0] = 1
for d in range(1,L):
    full.append(convolve_ones(10,full[-1]))

dist = np.zeros(D+D, dtype=np.int64)

cumsum = 0
for i,x in enumerate(K):
    arr = convolve_ones(x, full[L-i-1])
    dist[cumsum:cumsum+D] += arr
    cumsum += x
    cumsum %= D
dist[cumsum] += 1 # 全部そのまま使う

answer = dist[::D].sum() - 1 # 0除外
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
K = int(input())
D = int(input())
L = len(str(K))
k = str(K)

dp = [[[0 for _ in range(2)] for _ in range(D)] for _ in range(L+1)]
dp[0][0][0] = 1

mod = 10 ** 9 + 7

for i in range(L):
    for sum in range(D):
        for sml in range(2):
            if sml == 1:
                for d in range(10):
                    dp[i+1][(d+sum)%D][1] += dp[i][sum][1]
                    dp[i+1][(d+sum)%D][1] %= mod
            elif sml == 0:
                lim = int(k[i])
                for d in range(lim):
                    dp[i+1][(d+sum)%D][1] += dp[i][sum][0]
                    dp[i+1][(d+sum)%D][1] %= mod
                dp[i+1][(lim+sum)%D][0] += dp[i][sum][0]
                dp[i+1][(lim+sum)%D][0] %= mod

ans = dp[L][0][0] + dp[L][0][1] - 1
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
r=range
M=10**9+7
n=input()
d=int(input())
dp=[[[0,0]for j in r(d)]for i in r(len(n)+1)]
dp[0][0][0]=1
for i,x in enumerate(map(int,n),1):
  for j in r(10):
    for k in r(d):
      dp[i][(j+k)%d][1]+=dp[i-1][k][1]
      dp[i][(j+k)%d][1]%=M
      if j<x:
        dp[i][(j+k)%d][1]+=dp[i-1][k][0]
        dp[i][(j+k)%d][1]%=M
      if j==x:
        dp[i][(j+k)%d][0]+=dp[i-1][k][0]
        dp[i][(j+k)%d][0]%=M
print(~-sum(dp[-1][0])%M)
"""))

Submission status: Accepted

Solution code:
r=range
M=10**9+7
n=input()
d=int(input())
dp=[[[0,0]for j in r(d)]for i in r(len(n)+1)]
dp[0][0][0]=1
for i,x in enumerate(map(int,n),1):
  for j in r(10):
    for k in r(d):
      dp[i][(j+k)%d][1]+=dp[i-1][k][1]
      dp[i][(j+k)%d][1]%=M
      if j<x:
        dp[i][(j+k)%d][1]+=dp[i-1][k][0]
        dp[i][(j+k)%d][1]%=M
      if j==x:
        dp[i][(j+k)%d][0]+=dp[i-1][k][0]
        dp[i][(j+k)%d][0]%=M
print(~-sum(dp[-1][0])%M)