#include <bits/stdc++.h>
const int mod = 1e9 + 7;
using namespace std;
int m, lim[70], len = 0;
long long n;
struct mat {
  int n, m, a[31][31];
  mat(int _n = 0, int _m = 0) {
    n = _n, m = _m;
    memset(a, 0, sizeof(a));
  }
  int *operator[](int b) { return a[b]; }
  mat operator*(mat &b) const {
    assert(m == b.n);
    mat tmp(n, b.m);
    for (int i = 0; i <= n; i++)
      for (int k = 0; k <= m; k++)
        for (int j = 0; j <= b.m; j++)
          tmp[i][j] = (tmp[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
    return tmp;
  }
  void print() {
    for (int i = 0; i <= n; i++, puts(""))
      for (int j = 0; j <= m; j++) printf("%d ", a[i][j]);
  }
} f[70][31], pre[70][31], suf[70][31];
void work(int dep, int nw, int sum, mat &res) {
  if (dep < 0) return;
  if (!nw) return work(dep - 1, dep ? lim[dep - 1] : 0, sum, res);
  work(dep, nw - 1, (sum + 1) % m, res);
  res = f[dep][sum] * res;
}
void qmo(int &x) { x += (x >> 31) & mod; }
int main() {
  scanf("%lld%d", &n, &m);
  while (n) lim[len++] = n % m, n /= m;
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < m; j++) {
      f[i][j] = pre[i][j] = suf[i][j] = mat(m, m);
      if (!i)
        for (int k = 0; k <= m; k++) f[0][j][k][k] = 1, f[0][j][j][k] = 1;
      else if (!j)
        f[i][0] = suf[i - 1][0];
      else
        f[i][j] = suf[i - 1][j] * pre[i - 1][j - 1];
    }
    pre[i][0] = f[i][0], suf[i][m - 1] = f[i][m - 1];
    for (int j = 1; j < m; j++) pre[i][j] = pre[i][j - 1] * f[i][j];
    for (int j = m - 2; j >= 0; j--) suf[i][j] = f[i][j] * suf[i][j + 1];
  }
  mat res(m, 0);
  res[m][0] = 1;
  work(len - 1, lim[len - 1], 0, res);
  int ans = 0;
  for (int i = 0; i <= m; i++) qmo(ans += res[i][0] - mod);
  printf("%d\n", ans);
}
