Problem: Assume that sk(n) equals the sum of digits of number n in the k-based notation. For example, s2(5) = s2(1012) = 1 + 0 + 1 = 2, s3(14) = s3(1123) = 1 + 1 + 2 = 4.

The sequence of integers a0, ..., an - 1 is defined as <image>. Your task is to calculate the number of distinct subsequences of sequence a0, ..., an - 1. Calculate the answer modulo 109 + 7.

Sequence a1, ..., ak is called to be a subsequence of sequence b1, ..., bl, if there is a sequence of indices 1 ≤ i1 < ... < ik ≤ l, such that a1 = bi1, ..., ak = bik. In particular, an empty sequence (i.e. the sequence consisting of zero elements) is a subsequence of any sequence.

Input

The first line contains two space-separated numbers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 30).

Output

In a single line print the answer to the problem modulo 109 + 7.

Examples

Input

4 2


Output

11


Input

7 7


Output

128

Note

In the first sample the sequence ai looks as follows: (0, 1, 1, 0). All the possible subsequences are: 

(), (0), (0, 0), (0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 1, 0), (1), (1, 0), (1, 1), (1, 1, 0).

In the second sample the sequence ai looks as follows: (0, 1, 2, 3, 4, 5, 6). The subsequences of this sequence are exactly all increasing sequences formed from numbers from 0 to 6. It is easy to see that there are 27 = 128 such sequences.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const long long mod = 1000000007;
long long N, K;
template <class T>
struct Matrix {
  vector<vector<T> > A;
  Matrix() {}
  Matrix(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}
  Matrix(size_t n) : A(n, vector<T>(n, 0)){};
  size_t height() const { return (A.size()); }
  size_t width() const { return (A[0].size()); }
  inline const vector<T> &operator[](int k) const { return (A.at(k)); }
  inline vector<T> &operator[](int k) { return (A.at(k)); }
  static Matrix I(size_t n) {
    Matrix mat(n);
    for (int i = 0; i < n; i++) mat[i][i] = 1;
    return (mat);
  }
  Matrix &operator+=(const Matrix &B) {
    size_t n = height(), m = width();
    assert(n == B.height() && m == B.width());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        (*this)[i][j] = ((*this)[i][j] + B[i][j]) % mod;
    return (*this);
  }
  Matrix &operator-=(const Matrix &B) {
    size_t n = height(), m = width();
    assert(n == B.height() && m == B.width());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        (*this)[i][j] = ((*this)[i][j] - B[i][j] + mod) % mod;
    return (*this);
  }
  Matrix &operator*=(const Matrix &B) {
    size_t n = height(), m = B.width(), p = width();
    assert(p == B.height());
    vector<vector<T> > C(n, vector<T>(m, 0));
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        for (int k = 0; k < p; k++)
          C[i][j] = ((C[i][j] + (*this)[i][k] * B[k][j])) % mod;
    A.swap(C);
    return (*this);
  }
  Matrix &operator^=(long long k) {
    Matrix B = Matrix::I(height());
    while (k > 0) {
      if (k & 1) B *= *this;
      *this *= *this;
      k >>= 1LL;
    }
    A.swap(B.A);
    return (*this);
  }
  Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }
  Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }
  Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }
  Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }
  friend ostream &operator<<(ostream &os, Matrix &p) {
    size_t n = p.height(), m = p.width();
    for (int i = 0; i < n; i++) {
      os << "[";
      for (int j = 0; j < m; j++) {
        os << p[i][j] << (j + 1 == m ? "]\n" : ",");
      }
    }
    return (os);
  }
  T determinant() {
    Matrix B(*this);
    assert(width() == height());
    T ret = 1;
    for (int i = 0; i < width(); i++) {
      int idx = -1;
      for (int j = i; j < width(); j++) {
        if (B[j][i] != 0) idx = j;
      }
      if (idx == -1) return (0);
      if (i != idx) {
        ret *= -1;
        swap(B[i], B[idx]);
      }
      ret *= B[i][i];
      T vv = B[i][i];
      for (int j = 0; j < width(); j++) {
        B[i][j] /= vv;
      }
      for (int j = i + 1; j < width(); j++) {
        T a = B[j][i];
        for (int k = 0; k < width(); k++) {
          B[j][k] -= B[i][k] * a;
        }
      }
    }
    return (ret);
  }
  void rot() {
    Matrix<long long> B(A.size());
    for (int i = 0; i < K; i++) {
      for (int j = 0; j < K; j++) {
        B[i][j] = A[(i + K - 1) % K][(j + K - 1) % K];
      }
      B[i][K] = A[(i + K - 1) % K][K];
      B[K][i] = A[K][(i + K - 1) % K];
      B[K][K] = A[K][K];
    }
    for (int i = 0; i < A.size(); i++) {
      for (int j = 0; j < A[0].size(); j++) {
        A[i][j] = B[i][j];
      }
    }
  }
};
Matrix<long long> mat[70][35];
long long beki(long long a, long long b) {
  if (b == 0) return 1;
  long long ret = beki(a, b / 2);
  ret = ret * ret;
  if (b & 1) ret *= a;
  return ret;
}
int main() {
  cin >> N >> K;
  mat[0][0] = Matrix<long long>::I(K + 1);
  for (int i = 1; i < K + 1; i++) mat[0][0][0][i] = 1;
  for (int i = 1; i < K; i++) {
    mat[0][i] = mat[0][i - 1];
    mat[0][i].rot();
  }
  for (int index = 1; index < 70; index++) {
    mat[index][0] = mat[index - 1][0];
    for (int i = 1; i < K; i++) {
      mat[index][0] = mat[index - 1][i] * mat[index][0];
    }
    for (int i = 1; i < K; i++) {
      mat[index][i] = mat[index][i - 1];
      mat[index][i].rot();
    }
  }
  long long INDEX = 0;
  long long copy = N;
  while (copy >= K) {
    INDEX++;
    copy /= K;
  }
  cerr << INDEX << endl;
  Matrix<long long> ans(K + 1, 1);
  ans[K][0] = 1;
  int used = 0;
  while (INDEX >= 0) {
    for (int i = 0;; i++) {
      if (beki(K, INDEX) <= N) {
        N -= beki(K, INDEX);
        ans = mat[INDEX][used] * ans;
        used++;
        used %= K;
      } else
        break;
    }
    INDEX--;
  }
  long long val = 0;
  for (long long i = 0; i < K + 1; i++) {
    val += ans[i][0];
    val %= mod;
  }
  cout << val << endl;
  return 0;
}