#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9 + 7;
const double pi = acos(-1);
long long N;
int K, n, a[120];
struct Matrix {
  int a[32][32];
  int* operator[](int x) { return a[x]; }
  friend Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    memset(&c, 0, sizeof(c));
    for (int i = 0; i <= K; ++i)
      for (int j = 0; j <= K; ++j)
        for (int k = 0; k <= K; ++k)
          c[i][k] = (c[i][k] + 1ll * a[i][j] * b[j][k]) % mo;
    return c;
  }
} f[120][32], ans, suc[32], pre[32];
Matrix I() {
  Matrix tmp;
  memset(&tmp, 0, sizeof(tmp));
  for (int i = 0; i <= K; ++i) tmp[i][i] = 1;
  return tmp;
}
void prep() {
  for (int i = 0; i <= K - 1; ++i) {
    for (int j = 0; j <= K; ++j) f[0][i][j][j] = 1;
    for (int j = 0; j <= K; ++j)
      if (i != j) f[0][i][i][j] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    pre[0] = f[i - 1][0];
    for (int j = 1; j <= K - 1; ++j) pre[j] = pre[j - 1] * f[i - 1][j];
    suc[K - 1] = f[i - 1][K - 1];
    for (int j = K - 2; j >= 0; --j) suc[j] = f[i - 1][j] * suc[j + 1];
    for (int j = 0; j <= K - 1; ++j)
      f[i][j] = suc[j] * (j == 0 ? I() : pre[j - 1]);
  }
}
int main() {
  scanf("%I64d%d", &N, &K);
  while (N) {
    a[++n] = N % K;
    N /= K;
  }
  prep();
  for (int i = 0; i <= K; ++i) ans[1][i] = 1;
  int x = 0;
  for (int i = n; i >= 1; --i) {
    for (int j = 0; j <= a[i] - 1; ++j) ans = ans * f[i - 1][(j + x) % K];
    x = (x + a[i]) % K;
  }
  printf("%d\n", ans[1][K]);
}
