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 <typename T, typename U>
inline void amin(T& x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void amax(T& x, U y) {
  if (x < y) x = y;
}
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  ModInt(signed long long sig) {
    int sigt = sig % MOD;
    if (sigt < 0) sigt += MOD;
    x = sigt;
  }
  int get() const { return (int)x; }
  ModInt& operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt& operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt& operator*=(ModInt that) {
    x = (unsigned long long)x * that.x % MOD;
    return *this;
  }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
struct Matrix {
  vector<vector<ModInt<1000000007> > > v, w;
  Matrix() {}
  Matrix(int n, int m) : v(n, vector<ModInt<1000000007> >(m)) {}
  inline int height() const { return (int)v.size(); }
  inline int width() const { return (int)v[0].size(); }
  inline ModInt<1000000007>& at(int i, int j) { return v[i][j]; }
  inline const ModInt<1000000007>& at(int i, int j) const { return v[i][j]; }
  static Matrix identity(int n) {
    Matrix A(n, n);
    for (int(i) = 0; (i) < (int)(n); ++(i)) A.at(i, i) = 1;
    return A;
  }
  inline static Matrix identity(const Matrix& A) {
    return identity(A.height());
  }
  Matrix& operator*=(const Matrix& B) {
    int n = height(), m = B.width(), p = B.height();
    assert(p == width());
    w.assign(n, vector<ModInt<1000000007> >(m, 0));
    for (int(i) = 0; (i) < (int)(n); ++(i))
      for (int(j) = 0; (j) < (int)(m); ++(j)) {
        ModInt<1000000007> x = 0;
        for (int(k) = 0; (k) < (int)(p); ++(k)) x += at(i, k) * B.at(k, j);
        w[i][j] = x;
      }
    v.swap(w);
    return *this;
  }
};
Matrix operator^(const Matrix& t, long long k) {
  Matrix A = t, B = Matrix::identity(t);
  while (k) {
    if (k & 1) B *= A;
    A *= A;
    k >>= 1;
  }
  return B;
}
Matrix getRotateMatrix(int k, int t) {
  t = (t % k + k) % k;
  Matrix A(k + 3, k + 3);
  for (int(i) = 0; (i) < (int)(k); ++(i)) A.at(i, (i + t) % k) = 1;
  A.at(k, k) = A.at(k + 1, k + 1) = A.at(k + 2, k + 2) = 1;
  return A;
}
Matrix getSingletonMatrix(int k, int j) {
  assert(0 <= j && j < k);
  Matrix A(k + 3, k + 3);
  for (int(i) = 0; (i) < (int)(k); ++(i))
    if (i != j) A.at(i, i) += 1;
  A.at(k + 1, k + 1) = A.at(k + 2, k + 2) = 1;
  A.at(k, k + 1) += 1;
  A.at(j, k + 1) -= 1;
  A.at(k, k) += 2;
  A.at(j, k) -= 1;
  A.at(k, j) += 1;
  return A;
}
int s_k(int k, long long j) {
  long long t = j;
  int u = 0;
  while (t > 0) {
    (u += t % k) %= k;
    t /= k;
  }
  return u;
}
int main() {
  long long n;
  int k;
  while (cin >> n >> k) {
    Matrix b(1, k + 3);
    b.at(0, k) = 1;
    b.at(0, k + 1) = b.at(0, k + 2) = 1;
    long long powk = 1;
    int digits = 0;
    while (powk <= n / k) powk *= k, ++digits;
    vector<Matrix> P(digits + 1);
    P[0] = getSingletonMatrix(k, 0);
    for (int(i) = (int)(1); (i) <= (int)(digits); ++(i)) {
      P[i] = Matrix::identity(k + 3);
      for (int(j) = 0; (j) < (int)(k); ++(j)) {
        P[i] *= P[i - 1];
        P[i] *= getRotateMatrix(k, -1);
      }
    }
    long long offset = 0;
    while (powk > 0) {
      int t = (int)((n - offset) / powk);
      for (int(j) = 0; (j) < (int)(t); ++(j)) {
        int s = s_k(k, offset);
        b *= getRotateMatrix(k, -s);
        b *= P[digits];
        b *= getRotateMatrix(k, +s);
        offset += powk;
      }
      powk /= k;
      --digits;
    }
    ModInt<1000000007> ans = b.at(0, k + 1);
    cout << ans.get() << endl;
  }
  return 0;
}