#include <bits/stdc++.h>
using namespace std;
const int N = 35, M = 1e9 + 7;
int a[N * 2], k, tot;
long long n;
struct zz {
  int a[N][N];
  void write() {
    for (int i = 0; i <= k; i++) {
      for (int j = 0; j <= k; j++) printf("%d ", a[i][j]);
      puts("");
    }
  }
} A[N * 2][N * 2], pre[N * 2][N * 2], suf[N * 2][N * 2];
zz cf(zz x, zz y) {
  zz z;
  memset(z.a, 0, sizeof z.a);
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= k; j++)
      for (int l = 0; l <= k; l++)
        z.a[i][j] = (z.a[i][j] + (long long)x.a[i][l] * y.a[l][j]) % M;
  return z;
}
int main() {
  scanf("%lld%d", &n, &k);
  while (n) {
    a[++tot] = n % k;
    n /= k;
  }
  for (int i = 0; i < k; i++) {
    for (int j = 0; j <= k; j++) A[0][i].a[j][j] = 1;
    for (int j = 0; j <= k; j++) A[0][i].a[i][j] = 1;
  }
  pre[0][0] = A[0][0];
  suf[0][k - 1] = A[0][k - 1];
  for (int i = 1; i < k; i++) pre[0][i] = cf(pre[0][i - 1], A[0][i]);
  for (int i = k - 2; i >= 0; i--) suf[0][i] = cf(A[0][i], suf[0][i + 1]);
  for (int i = 1; i < tot; i++) {
    A[i][0] = suf[i - 1][0];
    for (int j = 1; j < k; j++) A[i][j] = cf(suf[i - 1][j], pre[i - 1][j - 1]);
    pre[i][0] = A[i][0];
    suf[i][k - 1] = A[i][k - 1];
    for (int j = 1; j < k; j++) pre[i][j] = cf(pre[i][j - 1], A[i][j]);
    for (int j = k - 2; j >= 0; j--) suf[i][j] = cf(A[i][j], suf[i][j + 1]);
  }
  zz Ans;
  int cnt = 0;
  memset(Ans.a, 0, sizeof Ans.a);
  for (int i = 0; i <= k; i++) Ans.a[i][i] = 1;
  for (int i = tot; i; i--) {
    for (int j = 0; j < a[i]; j++) Ans = cf(Ans, A[i - 1][(j + cnt) % k]);
    (cnt += a[i]) %= k;
  }
  int ans = 0;
  for (int i = 0; i <= k; i++) (ans += Ans.a[i][k]) %= M;
  printf("%d\n", ans);
  return 0;
}
