#include <bits/stdc++.h>
using namespace std;
void File() {
  freopen("rudy.in", "r", stdin);
  freopen("rudy.out", "w", stdout);
}
template <typename T>
void read(T &_) {
  T __ = 0, mul = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') mul = -1;
    ch = getchar();
  }
  while (isdigit(ch)) __ = (__ << 1) + (__ << 3) + (ch ^ '0'), ch = getchar();
  _ = __ * mul;
}
const int maxn = 100 + 10;
const long long mod = 1e9 + 7;
int k, tot;
long long n, dp[maxn];
struct Matrix {
  long long c[maxn][maxn];
  Matrix() {
    for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i)
      for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j) c[i][j] = 0;
  }
} d[maxn], f[maxn], g[maxn], gg[maxn];
Matrix operator*(Matrix a, Matrix b) {
  Matrix ret;
  for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i)
    for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
      for (int p = 1, p_end_ = k + 1; p <= p_end_; ++p)
        ret.c[i][j] = (ret.c[i][j] + a.c[i][p] * b.c[p][j]) % mod;
  return ret;
}
void out(Matrix a) {
  for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i) {
    for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
      printf("%lld ", a.c[i][j]);
    printf("\n");
  }
}
void init() {
  read(n), read(k);
  tot = k;
  for (int m = 0, m_end_ = tot; m <= m_end_; ++m) {
    d[m].c[1][k + 1] = 1;
    for (int i = 2, i_end_ = k + 1; i <= i_end_; ++i) {
      for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
        d[m].c[i][j] = d[m].c[i - 1][j] * 2 % mod;
      int p = ((i + m - 1) % k + k) % k;
      if (p == 0) p = k;
      d[m].c[i][p] = (d[m].c[i][p] - 1) % mod;
    }
  }
}
Matrix qpow(Matrix x, long long y) {
  Matrix ret;
  for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i)
    for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
      if (i == j)
        ret.c[i][j] = 1;
      else
        ret.c[i][j] = 0;
  while (y) {
    if (y & 1) ret = ret * x;
    x = x * x;
    y >>= 1;
  }
  return ret;
}
void work() {
  int lim = ceil(log(n) / log(k));
  for (int i = 1, i_end_ = lim; i <= i_end_; ++i) {
    g[i] = d[i % k];
    for (int l = 1, l_end_ = k + 1; l <= l_end_; ++l)
      for (int r = 1, r_end_ = k + 1; r <= r_end_; ++r)
        if (l == r)
          f[i].c[l][r] = 1;
        else
          f[i].c[l][r] = 0;
    for (int j = 1, j_end_ = i - 1; j <= j_end_; ++j) {
      f[i] = f[i] * gg[j];
      g[i] = g[i] * gg[j];
    }
    gg[i] = qpow(g[i], k - 1);
  }
  Matrix ans;
  for (int l = 1, l_end_ = k + 1; l <= l_end_; ++l)
    for (int r = 1, r_end_ = k + 1; r <= r_end_; ++r)
      if (l == r)
        ans.c[l][r] = 1;
      else
        ans.c[l][r] = 0;
  int las = 1;
  while (n >= k) {
    int w = 0;
    for (long long tmp = n; tmp >= k; tmp /= k) ++w;
    ans = f[w] * d[las % k] * ans;
    las = w;
    long long tmp = 1;
    for (int i = 1, i_end_ = w; i <= i_end_; ++i) tmp *= k;
    n -= tmp;
  }
  if (n == 0)
    printf("%lld\n", (ans.c[k + 1][k + 1] % mod + mod) % mod);
  else {
    ans = d[las % k] * ans;
    printf("%lld\n", (ans.c[n + 1][k + 1] % mod + mod) % mod);
  }
}
int main() {
  init();
  work();
  return 0;
}
