#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
constexpr int64 P = 1000000007;
struct FiniteField {
 private:
  int64 x;

 public:
  FiniteField(int64 x) : x(x) {
    if (x > P || x < 0) {
      cerr << "Invalied FiniteField!" << endl;
      exit(1);
    }
  }
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this);
    r += o;
    return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this);
    r -= o;
    return r;
  }
  inline FiniteField operator*(FiniteField o) const {
    FiniteField r(*this);
    r *= o;
    return r;
  }
  inline FiniteField operator/(FiniteField o) const {
    FiniteField r(*this);
    r /= o;
    return r;
  }
  inline void operator+=(FiniteField o) { x = (x + o.x) % P; }
  inline void operator-=(FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*=(FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2;
    while (p) {
      if (p % 2) {
        *this *= o;
      }
      o *= o;
      p /= 2;
    }
  }
};
template <typename T>
vector<vector<T>> operator*(const vector<vector<T>>& a1,
                            const vector<vector<T>>& a2) {
  int n = a1.size();
  int m = a1[0].size();
  if (a2.size() != m) {
    cerr << "Matrix dimensions don't match for multiplication!" << endl;
    exit(1);
  }
  int l = a2[0].size();
  vector<vector<T>> result(n, vector<T>(l));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      for (int k = 0; k < m; k++) {
        result[i][j] += a1[i][k] * a2[k][j];
      }
    }
  }
  return result;
}
template <typename T>
vector<T> operator*(const vector<vector<T>>& matrix, const vector<T>& v) {
  int n = matrix.size();
  int m = matrix[0].size();
  if (v.size() != m) {
    cerr << "Matrix and vector dimensions don't match for multiplication!"
         << endl;
    exit(1);
  }
  vector<T> result(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      result[i] += matrix[i][j] * v[j];
    }
  }
  return result;
}
template <typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}
template <typename T>
vector<vector<vector<T>>> Make3DVector(int d1, int d2, int d3,
                                       T default_value) {
  return vector<vector<vector<T>>>(
      d1, vector<vector<T>>(d2, vector<T>(d3, default_value)));
}
constexpr int DEBUG = 0;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int64 n;
  int d;
  cin >> n >> d;
  auto shifts = Make3DVector<FiniteField>(d, d + 1, d + 1, 0);
  for (int k = 0; k < d; k++) {
    for (int i = 0; i < d; i++) {
      shifts[k][i][(i + k) % d] = 1;
    }
    shifts[k][d][d] = 1;
  }
  auto units = Make3DVector<FiniteField>(d, d + 1, d + 1, 0);
  for (int k = 0; k < d; k++) {
    for (int i = 0; i < d + 1; i++) {
      units[k][i][i] = 1;
    }
    for (int i = 0; i < d + 1; i++) {
      units[k][k][i] = 1;
    }
  }
  auto identity = Make2DVector<FiniteField>(d + 1, d + 1, 0);
  for (int i = 0; i < d + 1; i++) {
    identity[i][i] = 1;
  }
  map<int64, vector<vector<FiniteField>>> cache;
  function<vector<vector<FiniteField>>(int64)> find_matrix =
      [&](int64 p) -> vector<vector<FiniteField>> {
    if (cache.find(p) != cache.end()) {
      return cache.find(p)->second;
    }
    if (p <= d) {
      auto matrix = identity;
      for (int k = 0; k < p; k++) {
        matrix = units[k] * matrix;
      }
      return matrix;
    }
    int64 child_p = d;
    while ((p + child_p - 1) / child_p > d) child_p *= d;
    auto child = find_matrix(child_p);
    auto matrix = child;
    int64 remaining_p = p;
    remaining_p -= child_p;
    for (int k = 1; k < d; k++) {
      if (remaining_p >= child_p) {
        matrix = shifts[d - k] * child * shifts[k] * matrix;
        remaining_p -= child_p;
      } else if (remaining_p > 0) {
        matrix = shifts[d - k] * find_matrix(remaining_p) * shifts[k] * matrix;
        remaining_p = 0;
      } else {
        break;
      }
    }
    cache[p] = matrix;
    return matrix;
  };
  if (DEBUG) cerr << "PHASE 1" << endl;
  auto matrix = find_matrix(n);
  if (DEBUG) cerr << "PHASE 2" << endl;
  vector<FiniteField> base_vector(d + 1);
  base_vector[d] = 1;
  auto final_vector = matrix * base_vector;
  FiniteField ans = 0;
  for (const auto& x : final_vector) ans += x;
  cout << ans.Value() << endl;
}
