#include <bits/stdc++.h>
using namespace std;
const int Max = 40;
const int LOG = 64;
const int Mod = 1e9 + 7;
int K;
struct DP {
  long long A[Max][Max];
  long long* operator[](int id) { return A[id]; }
  friend DP operator*(DP a, DP b) {
    DP c;
    for (int i = 0; i <= K; i++)
      for (int j = 0; j <= K; j++) c[i][j] = 0;
    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] + a[i][j] * b[j][k]) % Mod;
    return c;
  }
  friend DP operator+(DP a, int x) {
    x = (x + K) % K;
    DP b;
    for (int i = 0; i <= K; i++)
      for (int j = 0; j < K; j++) b[i][j] = a[i][(j + x) % K];
    b[K][K] = a[K][K];
    return b;
  }
};
DP dp[LOG][Max], ans;
long long len;
int main() {
  long long N;
  cin >> N >> K;
  for (int i = 0; i < K; i++) {
    dp[0][1][i][0] = 1;
    dp[0][1][i][i] = 1;
  }
  dp[0][1][K][0] = 1;
  dp[0][1][K][K] = 1;
  for (int j = 2; j <= K; j++)
    dp[0][j] = (dp[0][j - 1] + (-j + 1)) * dp[0][1] + (j - 1);
  for (int lg = 1; lg < LOG; lg++) {
    dp[lg][1] = dp[lg - 1][K];
    for (int j = 2; j <= K; j++)
      dp[lg][j] = (dp[lg][j - 1] + (-j + 1)) * dp[lg][1] + (j - 1);
  }
  ans[0][0] = -1;
  int lg = 0;
  long long pw = 1;
  while (N) {
    int x = N % K;
    if (x) {
      if (ans[0][0] == -1)
        ans = dp[lg][x];
      else {
        int y = x;
        ans = (dp[lg][x] + (-y)) * ans + y;
      }
    }
    len += x * pw, pw *= K, lg++, N /= K;
  }
  long long RES = 0;
  for (int i = 0; i <= K; i++) RES = (RES + ans[K][i]) % Mod;
  cout << RES << '\n';
}
