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: def add(a, b):
      mod = 1e9 + 7
      c = a + b
      if c >= mod:
          c -= mod
      return c
  
  
  def subtract(a, b):
      mod = 1e9 + 7
      c = a - b
      if c < 0:
          c += mod
      return c
  
  
  K = input()
  
  D = int(input())
  
  # dp[sum][smaller_already] - no. of ways to have digits sum % D = sum, smaller_already means if it is already less than K
  
  dp = [[0 for _ in range(2)] for _ in range(D)]
  
  str_len = len(K)
  
  dp[0][0] = 1
  
  for where in range(str_len):
      new_dp = [[0 for _ in range(2)] for _ in range(D)]
      for sum_so_far in range(D):
          for smaller_already in [0, 1]:
              for digit in range(10):
                  K_digit = ord(K[where]) - ord("0")
                  if digit > K_digit and smaller_already == 0:
                      break
                  new_sum = (sum_so_far + digit) % D
                  new_smaller = 1 if smaller_already == 1 or digit < K_digit else 0
                  new_dp[new_sum][new_smaller] = add(
                      new_dp[new_sum][new_smaller], dp[sum_so_far][smaller_already]
                  )
      dp = new_dp
  
  
  answer = add(dp[0][0], dp[0][1])
  
  answer = int(subtract(answer, 1))
  
  print(answer)
  
  
  """
  #include <bits/stdc++.h>
  using namespace std;
  
  using ll = long long; 
  
  /*
  30
  4
  
  brute-force -> look one by one -> from 1 to 30 -> if the digit sum is multiple of 4, then add
  O(K * log K)
  
  
  dp[d] - how many ways to get to remainder is d
  
  dp[0] is the ans
  
  dp[d] - how many ways to get to digit_sum as d
  
  */
  
  
  int add(int a, int b) {
      const int mod = 1e9+7;
      int c = a + b;
      if (c >= mod) {
          c -= mod;
      }
      return c;
  }
  
  int subtract(int a, int b) {
      const int mod = 1e9+7;
      int c = a - b;
      if (c < 0) {
          c += mod;
      }
      return c;
  }
  
  int main() {
      const int nax = 10123;
      char K[nax];
      int D;
      scanf("%s", K);
      scanf("%d", &D);
      int len = strlen(K);
      vector<vector<int>> dp(D, vector<int>(2));
      // dp[sum][smaller_already] - no. of ways to choose digits so far
      // such that digits sum % D = sum and smaller_already means if the number
      // is already less than K
      dp[0][0] = 1;
      
      for (int where = 0; where < len; where++) {
          vector<vector<int>> new_dp(D, vector<int>(2));
          for (int sum = 0; sum < D; sum++) {
              for (bool sm_already : {false, true}) {
                  for (int digit = 0; digit < 10; digit++) {
                      if (digit > K[where] - '0' && !sm_already) {
                          break;
                      }
                      int new_sum = (sum + digit) % D;
                      bool smaller = sm_already || digit < (K[where] - '0');
                      new_dp[new_sum][smaller] = add(new_dp[new_sum][smaller], dp[sum][sm_already]);
                  }
              }
          }
          dp = new_dp;
      }
      
      int answer = add(dp[0][false], dp[0][true]);
      
      answer = subtract(answer, 1);
      
      printf("%d", answer);
      /*
      int ans = 0;
      for (int i = 1; i <= K; i++) {
          if (digit_sum(i) % D == 0) {
              ans += 1;
          }
      }
      printf("%d", ans);
      */
      
  }
  """
  
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"}]