#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9 + 7;
inline void inc(int &first, int second) {
  if ((first += second) >= mo) first -= mo;
}
inline void glance() { freopen("ha.in", "r", stdin); }
long long N;
int an, K, n, a[66];
struct Mat {
  int a[32][32];
  int *operator[](const int &first) { return a[first]; }
  Mat(bool b = 0) {
    for (int _r = K, i = 0; i <= _r; ++i)
      for (int _r = K, j = 0; j <= _r; ++j) a[i][j] = i == j && b;
  }
  Mat operator*(Mat &B) {
    Mat C = Mat();
    for (int _r = K, i = 0; i <= _r; ++i)
      for (int _r = K, j = 0; j <= _r; ++j)
        for (int _r = K, k = 0; k <= _r; ++k)
          inc(C[i][j], 1ll * a[i][k] * B[k][j] % mo);
    return C;
  }
} A, pre[32], suf[32], F[66][32];
inline void pret() {
  for (int _r = K, i = 0; i < _r; ++i) {
    for (int _r = K, j = 0; j <= _r; ++j) F[0][i][j][j] = F[0][i][i][j] = 1;
  }
  for (int _r = n, i = 1; i <= _r; ++i) {
    pre[0] = Mat(1);
    for (int _r = K, j = 1; j < _r; ++j) pre[j] = F[i - 1][j - 1] * pre[j - 1];
    suf[K - 1] = F[i - 1][K - 1];
    for (int _l = 0, j = K - 2; j >= _l; --j) suf[j] = suf[j + 1] * F[i - 1][j];
    for (int _r = K, m = 0; m < _r; ++m) F[i][m] = pre[m] * suf[m];
  }
}
int main() {
  scanf("%I64d%d", &N, &K);
  A = Mat(1);
  for (; N; N /= K) a[n++] = N % K;
  --n;
  pret();
  int la = 0;
  for (int _l = 0, i = n; i >= _l; --i) {
    for (int _r = a[i], j = 0; j < _r; ++j) A = F[i][(la + j) % K] * A;
    la = (la + a[i]) % K;
  }
  for (int _r = K, i = 0; i <= _r; ++i) inc(an, A[i][K]);
  printf("%d\n", an);
}
