#include <bits/stdc++.h>
using namespace std;
int getint() {
  int s = 0, o = 1;
  char c;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    if (c == '-') o = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) s *= 10, s += c - '0';
  return s * o;
}
const int mod = (int)1e9 + 7;
struct Mat {
  int n;
  long long x;
  int a[31][31];
  void operator*=(const Mat &p) {
    int c[31][31];
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        long long r = 0;
        for (int k = 0; k < n; k++) r += (1ll * a[i][k] * p.a[k][j]) % mod;
        c[i][j] = r % mod;
        if (c[i][j] < 0) c[i][j] += mod;
      }
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) a[i][j] = c[i][j];
  }
  void write() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) printf("%d ", a[i][j]);
      printf("\n");
    }
  }
} A[70][30], B[70][30];
long long n;
int k;
Mat I;
Mat calc(int i, int j, long long n) {
  Mat r = I;
  if (n == 0) return r;
  for (int timer = 0; timer < k; timer++) {
    if (n >= A[i][j].x)
      r *= A[i][j];
    else
      r *= calc(i - 1, j, n);
    n -= A[i][j].x;
    if (n <= 0) break;
    j = (j + 1) % k;
  }
  return r;
}
int main(int argc, char const *argv[]) {
  scanf("%I64d%d", &n, &k);
  I.n = k + 1;
  for (int i = 0; i < I.n; i++)
    for (int j = 0; j < I.n; j++) I.a[i][j] = i == j;
  for (int i = 0; i < k; i++) {
    Mat &M = A[0][i];
    M.n = k + 1, M.x = 1;
    for (int t = 0; t < k + 1; t++)
      for (int s = 0; s < k + 1; s++) M.a[t][s] = (t == s || t == i);
    Mat &N = B[0][i];
    N.n = k + 1, N.x = 1;
    for (int t = 0; t < k + 1; t++)
      for (int s = 0; s < k + 1; s++) {
        if (t == i) N.a[t][s] = -1;
        if (t == s) N.a[t][s] = 1;
      }
  }
  int i;
  for (i = 0;; i++) {
    long long _x = A[i][0].x * k;
    if (_x > n || _x < 0) break;
    Mat &M = A[i + 1][0];
    M = A[i][0];
    M.x = _x;
    for (int p = 1; p < k; ++p) M *= A[i][p];
    for (int j = 1; j < k; ++j) {
      Mat &M = A[i + 1][j];
      M = B[i][j - 1];
      M *= A[i + 1][j - 1];
      M *= A[i][j - 1];
      M.x = _x;
    }
    Mat &N = B[i + 1][0];
    N = B[i][k - 1];
    N.x = _x;
    for (int p = k - 2; p >= 0; --p) N *= B[i][p];
    for (int j = 1; j < k; ++j) {
      Mat &N = B[i + 1][j];
      N = B[i][j - 1];
      N *= B[i + 1][j - 1];
      N *= A[i][j - 1];
      N.x = _x;
    }
  }
  Mat res = calc(i, 0, n);
  long long r = 0;
  for (int i = 0; i < k + 1; i++) r += res.a[i][k];
  printf("%I64d\n", r % mod);
  return 0;
}
