output_description: Print the number of integers satisfying the condition, modulo 10^9 + 7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      K
      D
attempt: 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())
  
  fft_len = 1
  while fft_len < 2 * D:
      fft_len *= 2
  
  
  def fft_convolve(A, B):
      return np.round(irfft(rfft(A, fft_len) * rfft(B, fft_len))).astype(np.int64) % MOD
  
  
  def convolve(A, B):
      M = 1 << 16
      mask = M - 1
      A1, A2 = A >> 16, A & mask
      B1, B2 = B >> 16, B & mask
      X, Y, Z = [fft_convolve(P, Q) for P, Q in [[A1, B1], [A1 - A2, B1 - B2], [A2, B2]]]
      X = (X << 32) + ((X - Y + Z) << 16) + Z
      X[:D] += X[D : D + D]
      return X[:D] % MOD
  
  
  # d桁以下、自由に使った場合の余りごとの個数。0を含めて数えておく
  ones = [np.zeros(D, dtype=np.int64)]
  for x in range(10):
      arr = ones[-1].copy()
      arr[x % D] += 1
      ones.append(arr)
  full = []
  dp = np.zeros(D, dtype=np.int64)
  dp[0] = 1
  full.append(dp)
  for d in range(1, L):
      dp = convolve(dp, ones[10])
      full.append(dp)
  
  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
  
  answer = dist[::D].sum() - 1  # 0除外
  answer %= MOD
  print(answer)
  
problem_description: 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.
samples: [{"input": "30\n    4", "output": "6\n    \n\nThose six integers are: 4, 8, 13, 17, 22 and 26.\n\n* * *"}, {"input": "1000000009\n    1", "output": "2\n    \n\nBe sure to print the number modulo 10^9 + 7.\n\n* * *"}, {"input": "98765432109876543210\n    58", "output": "635270834"}]