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;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i];
    if (i != v.size() - 1) cout << endl;
  };
  return os;
}
template <typename T>
void Out(T x) {
  cout << x << endl;
}
template <typename T1, typename T2>
void Ans(bool first, T1 y, T2 n) {
  if (first)
    Out(y);
  else
    Out(n);
}
using vec = vector<long long>;
using mat = vector<vec>;
using Pii = pair<long long, long long>;
using PiP = pair<long long, Pii>;
using PPi = pair<Pii, long long>;
using bools = vector<bool>;
using pairs = vector<Pii>;
const long long mod = 1000000007;
template <long long MOD>
struct ModInt {
  using ll = long long;
  ll val;
  void setval(ll v) { val = v % MOD; };
  ModInt() : val(0) {}
  ModInt(ll v) { setval(v); };
  ModInt operator+(const ModInt &x) const { return ModInt(val + x.val); }
  ModInt operator-(const ModInt &x) const { return ModInt(val - x.val + MOD); }
  ModInt operator*(const ModInt &x) const { return ModInt(val * x.val); }
  ModInt operator/(const ModInt &x) const { return *this * x.inv(); }
  ModInt operator-() const { return ModInt(MOD - val); }
  ModInt operator+=(const ModInt &x) { return *this = *this + x; }
  ModInt operator-=(const ModInt &x) { return *this = *this - x; }
  ModInt operator*=(const ModInt &x) { return *this = *this * x; }
  ModInt operator/=(const ModInt &x) { return *this = *this / x; }
  friend ostream &operator<<(ostream &os, const ModInt &x) {
    os << x.val;
    return os;
  }
  friend istream &operator>>(istream &is, ModInt &x) {
    is >> x.val;
    x.val = (x.val % MOD + MOD) % MOD;
    return is;
  }
  ModInt pow(ll n) const {
    ModInt a = 1;
    if (n == 0) return a;
    long long i0 = 64 - __builtin_clzll(n);
    for (long long i = i0 - 1; i >= 0; i--) {
      a = a * a;
      if ((n >> i) & 1) a *= (*this);
    }
    return a;
  }
  ModInt inv() const { return this->pow(MOD - 2); }
};
using mint = ModInt<mod>;
mint pow(mint x, long long n) { return x.pow(n); }
using mvec = vector<mint>;
using mmat = vector<mvec>;
struct Combination {
  vector<mint> fact, invfact;
  Combination(long long N) {
    fact = vector<mint>({mint(1)});
    invfact = vector<mint>({mint(1)});
    fact_initialize(N);
  }
  void fact_initialize(long long N) {
    long long i0 = fact.size();
    if (i0 >= N + 1) return;
    fact.resize(N + 1);
    invfact.resize(N + 1);
    for (long long i = i0; i <= N; i++) fact[i] = fact[i - 1] * i;
    invfact[N] = (mint)1 / fact[N];
    for (long long i = N - 1; i >= i0; i--)
      invfact[i] = invfact[i + 1] * (i + 1);
  }
  mint nCr(long long n, long long r) {
    if (n < 0 || r < 0 || r > n) return mint(0);
    if (fact.size() < n + 1) fact_initialize(n);
    return fact[n] * invfact[r] * invfact[n - r];
  }
  mint nPr(long long n, long long r) {
    if (n < 0 || r < 0 || r > n) return mint(0);
    if (fact.size() < n + 1) fact_initialize(n);
    return fact[n] * invfact[n - r];
  }
};
template <typename T>
struct Matrix {
  long long R, C;
  vector<T> element;
  __inline__ T &at(long long i, long long j) { return element[i * C + j]; }
  Matrix(long long R, long long C, vector<T> &element)
      : R(R), C(C), element(element) {
    assert(element.size() == R * C);
  }
  Matrix(vector<vector<T>> &_element) {
    R = _element.size();
    C = _element[0].size();
    element.resize(R * C);
    for (long long i = 0; i < R; i++)
      for (long long j = 0; j < C; j++) element[i * C + j] = _element[i][j];
  }
  Matrix(long long R, long long C) : R(R), C(C) {
    element = vector<T>(R * C, (T)0);
  }
  Matrix(long long N) : R(N), C(N) {
    element = vector<T>(N * N, (T)0);
    for (long long i = 0; i < N; i++) element[(N + 1) * i] = (T)1;
  }
  Matrix() : R(0), C(0) {}
  Matrix operator+(Matrix &x) {
    assert(R == x.R && C == x.C);
    Matrix M(R, C);
    for (long long i = 0; i < R * C; i++)
      M.element[i] = element[i] + x.element[i];
    return M;
  }
  Matrix operator-(Matrix &x) {
    assert(R == x.R && C == x.C);
    Matrix M(R, C);
    for (long long i = 0; i < R * C; i++)
      M.element[i] = element[i] - x.element[i];
    return M;
  }
  Matrix operator*(Matrix &x) {
    assert(C == x.R);
    Matrix M(R, x.C);
    for (long long i = 0; i < R; i++)
      for (long long j = 0; j < x.C; j++) {
        for (long long k = 0; k < C; k++) M.at(i, j) += at(i, k) * x.at(k, j);
      }
    return M;
  }
  Matrix operator*(const T &a) {
    Matrix M(R, C);
    for (long long i = 0; i < R * C; i++) M.element[i] = element[i] * a;
    return M;
  }
  Matrix operator+=(Matrix &x) { return *this = *this + x; }
  Matrix operator-=(Matrix &x) { return *this = *this - x; }
  Matrix operator*=(Matrix &x) { return *this = *this * x; }
  Matrix operator*=(const T &a) {
    for (long long i = 0; i < R * C; i++) element[i] *= a;
    return *this;
  }
  Matrix pow(long long n) {
    assert(R == C);
    Matrix M(R);
    if (n == 0) return M;
    long long i0 = 64 - __builtin_clzll(n);
    for (long long i = i0 - 1; i >= 0; i--) {
      M *= M;
      if ((n >> i) & 1) M *= (*this);
    }
    return M;
  }
  void Print() {
    for (long long i = 0; i < R; i++) {
      for (long long j = 0; j < C; j++) cout << element[i * C + j] << " ";
      cout << endl;
    }
  }
  Matrix slide() {
    Matrix A(R, C);
    for (long long i = (0); i < (R); i++)
      for (long long j = (0); j < (C); j++) {
        long long i0 = i, j0 = j;
        if (i0) i0 = i0 % (R - 1) + 1;
        if (j0) j0 = j0 % (C - 1) + 1;
        A.at(i0, j0) = at(i, j);
      }
    return A;
  }
};
signed main() {
  long long n, k;
  cin >> n >> k;
  vec d;
  long long n0 = n;
  while (n0) {
    d.push_back(n0 % k);
    n0 /= k;
  }
  long long D = ((long long)d.size());
  Matrix<mint> A0(k + 1);
  for (long long j = (0); j < (k + 1); j++) A0.at(1, j) = 1;
  vector<Matrix<mint>> Ms(D);
  Ms[0] = A0;
  for (long long i = (0); i < (D - 1); i++) {
    A0 = Ms[i];
    Ms[i + 1] = Matrix<mint>(k + 1);
    for (long long j = (0); j < (k); j++) {
      Ms[i + 1] = A0 * Ms[i + 1];
      A0 = A0.slide();
    }
  }
  Matrix<mint> dp(k + 1, 1);
  dp.at(0, 0) = 1;
  long long tmp = 0;
  for (long long i = (D)-1; i >= (0); i--) {
    for (long long j = (0); j < (tmp); j++) Ms[i] = Ms[i].slide();
    for (long long j = (0); j < (d[i]); j++) {
      dp = Ms[i] * dp;
      Ms[i] = Ms[i].slide();
    }
    tmp = (tmp + d[i]) % k;
  }
  mint ans = 0;
  for (long long j = (0); j < (k + 1); j++) ans += dp.at(0, j);
  Out(ans);
  return 0;
}