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

Solution (Python):

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


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


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


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


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


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


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


def G():

    return


def H():

    return


def I_():

    return


def J():

    return


def K():

    return


if __name__ == "__main__":
    D()

Solution (Python):

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


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


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


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


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


def E():

    return


def F():

    return


def G():

    return


def H():

    return


def I_():

    return


def J():

    return


def K():

    return


if __name__ == "__main__":
    D()

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


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)

Solution (Python):
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)

Solution (Python):
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):
    
    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


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 
answer %= MOD
print(answer)

Solution (Python):
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)

Solution (Python):
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)
"""))

Solution (Python):
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)

Solution (Python):


import sys

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

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        
        
        
        for l in range(2, s):
            
            
            for r in range(d):
                dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                
                
                


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Solution (Python):


import sys

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

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Solution (Python):
mod = 10**9 + 7

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(1,N+1):
    for j in range(D):
        dp[i][(j+int(K[i-1])) % D][0] += dp[i-1][j][0]
        for k in range(int(K[i-1])):
            dp[i][(j+k) % D][1] += dp[i-1][j][0]
        for k in range(10):
            dp[i][(j+k) % D][1] += dp[i-1][j][1]
        
        dp[i][j][0] %= mod
        dp[i][j][1] %= mod

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

Solution (Python):
K = list(map(int, input().strip()))
D = int(input())
mod = 10**9+7

dp = [0]*D
dp[0] += 1
S = 0
for k in K:
    dp[S%D] -= 1
    dp2 = [0]*(D+10)
    for j, d in enumerate(dp):
        dp2[j] += d
        dp2[j+10] -= d
    for j in range(1, D+10):
        dp2[j] = (dp2[j-1] + dp2[j]) % mod
    for j in range(10):
        dp2[(D+j)%D] = (dp2[(D+j)%D] + dp2[D+j]) % mod 
    dp = dp2[:D]
    for j in range(k+1):
        dp[(S+j)%D] = (dp[(S+j)%D] + 1)%mod
    S += k
print((dp[0]-1)%mod)

Solution (Python):
k = input()
d = int(input())
MOD = 10**9 + 7


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

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

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

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

Solution (Python):
K = list(map(int, list(input())))
D = int(input())
N = len(K)
dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
mod = 10**9+7
dp[0][0][0] = 1

for i in range(N):
    for smaller in range(2):
        for j in range(D):
            for x in range(10 if smaller else K[i]+1):
                dp[i+1][smaller or int(x < K[i])][j] = (dp[i+1][smaller or int(x < K[i])][j] + dp[i][smaller][(j-x)%D]) % mod

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

Solution (Python):





MOD = 10**9+7

n=input()
D=int(input())

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

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


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

Solution (Python):

"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import sys

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

input = lambda: sys.stdin.readline().rstrip("\r\n")

MOD = 10**9 + 7


def main():
    K, D = list(map(int, input())), int(input())
    n = len(K)

    dp = [[0] * D for _ in range(n)]
    for i in range(10):
        dp[0][i % D] += 1
    for i in range(n - 1):
        for j in range(D):
            dp[i + 1][j] = sum(dp[i][(j - k) % D] for k in range(10)) % MOD

    cnt, k = 0, 0
    for i in range(n - 1):
        cnt = (cnt + sum(dp[-i - 2][(-j - k) % D] for j in range(K[i]))) % MOD
        k += K[i]
    cnt += sum((j + k) % D == 0 for j in range(K[-1] + 1))

    print((cnt - 1) % MOD)


if __name__ == "__main__":
    main()

Solution (Python):

"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import Counter

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

MOD = 10**9 + 7


def main():
    K, d = list(map(int, input())), int(input())
    n = len(K)

    dp = [[0] * d for _ in range(n)]

    dp0 = dp[0]
    for k in range(10):
        dp0[k % d] += 1

    for i in range(n - 1):
        dpi, dpii = dp[i], dp[i + 1]
        for j in range(d):
            dpii[j] = sum(dpi[(j - k) % d] for k in range(10)) % MOD

    res, k = 0, 0
    for i in range(n - 1):
        dpi = dp[-i - 2]
        res = (res + sum(dpi[(-j - k) % d] for j in range(K[i]))) % MOD
        k += K[i]
    res += sum((k + j) % d == 0 for j in range(K[-1] + 1))

    print((res - 1) % MOD)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")



if __name__ == "__main__":
    main()

Solution (Python):

"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import Counter

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

MOD = 10**9 + 7


def main():
    k, d = list(map(int, input())), int(input())
    n = len(k)

    dp = [[0] * d for _ in range(n)]
    for m in range(10):
        dp[0][m % d] += 1
    for i in range(n - 1):
        for j in range(d):
            dp[i + 1][j] = sum(dp[i][(j - m) % d] for m in range(10)) % MOD

    res, cnt = 0, 0
    for i in range(n - 1):
        res = (res + sum(dp[-i - 2][(-m - cnt) % d] for m in range(k[i]))) % MOD
        cnt += k[i]
    res += sum((cnt + m) % d == 0 for m in range(k[-1] + 1))

    print((res - 1) % MOD)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        ndp[0] = s = sum(dp[i % d] for i in range(-9, 1))
        for i in range(1, d):
            ndp[i] = s = (s + dp[i % d] - dp[(i - 10) % d]) % md

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)

Solution (Python):
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        ndp = [ndk % md for ndk in ndp]

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)

Solution (Python):
import sys
sys.setrecursionlimit(10070)
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(max(2,e)) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print((f(k,0)-1)%MOD)

Solution (Python):


import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() 
D = int(input()) 

print(f(K, D))

Solution (Python):
mod = 10**9 + 7

K = list(map(int, list(input())))
D = int(input())
keta = len(K)

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

from itertools import product
for i, j, k in product(range(keta), range(2), range(D)):
    max_n = K[i] if j else 9
    for l in range(max_n+1):
        dp[i+1][j and l == max_n][(k+l)%D] += dp[i][j][k]
        dp[i+1][j and l == max_n][(k+l)%D] %= mod

ans = 0
for i in range(2):
    ans += dp[-1][i][0]
    ans %= mod
print(max(0, (ans - 1)%mod))

Solution (Python):
mod=10**9+7
K=list(map(int,input().strip()))
d=int(input())
l=len(K)
DP=[[[0]*d for _ in range(2)] for _ in range(l+1)]
DP[0][0][0]=1
for i,k in enumerate(K):
    for less in range(2):
        if less:
            limit=9
        else:
            limit=k
        for m in range(d):
            for l in range(limit+1):
                DP[i+1][less or l<limit][(m+l)%d]+=DP[i][less][m]
                DP[i+1][less or l<limit][(m+l)%d]%=mod
print((DP[-1][0][0]+DP[-1][1][0]-1)%mod)

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

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

for i in range(len(k)):
    for j in range(2):
        for m in range(d):
            if j == 1:
                for num in range(10):
                    dp[i+1][j][(m+num)%d] += dp[i][j][m]
                    dp[i+1][j][(m+num)%d] %= mod
            else:
                for num in range(int(k[i])+1):
                    if num != int(k[i]):
                        dp[i+1][1][(m+num)%d] += dp[i][j][m]
                        dp[i+1][1][(m+num)%d] %= mod
                    else:
                        dp[i+1][0][(m+num)%d] += dp[i][j][m]
                        dp[i + 1][0][(m + num) % d] %= mod

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

Solution (Python):
K = input()
D = int(input())
L = len(K)
MOD = 10**9+7
dp = [[[0]*D for j in range(2)] for i in range(L+1)] 
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for r in range(D):
            for d in range(lim+1):
                dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
                dp[i+1][less or d < lim][(r+d)%D] %= MOD

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

Solution (Python):


MOD = 1000000007

def F(k, s):
    return dp[k][s]

def solve(n):
    resp = 0
    n = map(int, str(n))
    pref = 0
    for i in range(len(n)):
        for d in range(n[i]):
            resp += F(len(n) - i - 1, (pref - d) % D)
            resp %= MOD
        pref -= n[i]
        pref %= D
    return resp


K = raw_input()
D = input()


dp = [[0] * D for _ in range(len(K) + 1)]
dp[0][0] = 1
for i in range(1, len(K) + 1):
    for j in range(D):
        for d in range(10):
            dp[i][j] += dp[i - 1][(j - d) % D]
            dp[i][j] %= MOD

resp = solve(K) - 1
if sum(map(int, str(K))) % D == 0:
    resp += 1
print(resp % MOD)

Solution (Python):
K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D
    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod
print((next_dp[0] + (border == 0) - 1) % mod)

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

L=len(K)

DP=[0]*D
LIMIT=[]

for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        LIMIT=j%D
    else:
        DP[j%D]+=1

for ketanum in K[1:]:
    NDP=[0]*D

    for i in range(D):
        for j in range(10):
            NDP[(i+j)%D]=(NDP[(i+j)%D]+DP[i])%mod

    for j in range(int(ketanum)):
        NDP[(LIMIT+j)%D]+=1

    LIMIT=(LIMIT+int(ketanum))%D

    DP=NDP

print((DP[0]-1+ (LIMIT==0) )%mod)

Solution (Python):
K = input()
D = int(input())
L = len(K)
MOD = 10**9+7
dp = [[[0]*D for j in range(2)] for i in range(L+1)] 
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for r in range(D):
            for d in range(lim+1):
                dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
                dp[i+1][less or d < lim][(r+d)%D] %= MOD

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    k = S()
    d = I()
    t = [0] * d
    c = 0
    for i in k:
        i = int(i)
        u = t[:]
        for j in range(c,c+i):
            u[j%d] += 1
        c += i
        c %= d
        d1 = max(0, d-10)
        for j in range(d1):
            for jj in range(j+1,j+10):
                u[jj] += t[j]
            u[j] %= mod

        for j in range(d1, d):
            for jj in range(j+1,j+10):
                u[jj%d] += t[j]
            u[j] %= mod
        t = u

    if c == 0:
        return t[0] % mod

    return (t[0] - 1) % mod


print(main())