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;
using int64 = long long;
constexpr int64 P = 1000000007;
struct FiniteField {
 private:
  int64 x;

 public:
  FiniteField(int64 x) : x(x) {
    if (x > P || x < 0) {
      cerr << "Invalied FiniteField!" << endl;
      exit(1);
    }
  }
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this);
    r += o;
    return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this);
    r -= o;
    return r;
  }
  inline FiniteField operator*(FiniteField o) const {
    FiniteField r(*this);
    r *= o;
    return r;
  }
  inline FiniteField operator/(FiniteField o) const {
    FiniteField r(*this);
    r /= o;
    return r;
  }
  inline void operator+=(FiniteField o) { x = (x + o.x) % P; }
  inline void operator-=(FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*=(FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2;
    while (p) {
      if (p % 2) {
        *this *= o;
      }
      o *= o;
      p /= 2;
    }
  }
};
template <typename T>
vector<vector<T>> operator*(const vector<vector<T>>& a1,
                            const vector<vector<T>>& a2) {
  int n = a1.size();
  int m = a1[0].size();
  if (a2.size() != m) {
    cerr << "Matrix dimensions don't match for multiplication!" << endl;
    exit(1);
  }
  int l = a2[0].size();
  vector<vector<T>> result(n, vector<T>(l));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      for (int k = 0; k < m; k++) {
        result[i][j] += a1[i][k] * a2[k][j];
      }
    }
  }
  return result;
}
template <typename T>
vector<T> operator*(const vector<vector<T>>& matrix, const vector<T>& v) {
  int n = matrix.size();
  int m = matrix[0].size();
  if (v.size() != m) {
    cerr << "Matrix and vector dimensions don't match for multiplication!"
         << endl;
    exit(1);
  }
  vector<T> result(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      result[i] += matrix[i][j] * v[j];
    }
  }
  return result;
}
template <typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}
template <typename T>
vector<vector<vector<T>>> Make3DVector(int d1, int d2, int d3,
                                       T default_value) {
  return vector<vector<vector<T>>>(
      d1, vector<vector<T>>(d2, vector<T>(d3, default_value)));
}
constexpr int DEBUG = 0;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int64 n;
  int d;
  cin >> n >> d;
  auto shifts = Make3DVector<FiniteField>(d, d + 1, d + 1, 0);
  for (int k = 0; k < d; k++) {
    for (int i = 0; i < d; i++) {
      shifts[k][i][(i + k) % d] = 1;
    }
    shifts[k][d][d] = 1;
  }
  auto units = Make3DVector<FiniteField>(d, d + 1, d + 1, 0);
  for (int k = 0; k < d; k++) {
    for (int i = 0; i < d + 1; i++) {
      units[k][i][i] = 1;
    }
    for (int i = 0; i < d + 1; i++) {
      units[k][k][i] = 1;
    }
  }
  auto identity = Make2DVector<FiniteField>(d + 1, d + 1, 0);
  for (int i = 0; i < d + 1; i++) {
    identity[i][i] = 1;
  }
  map<int64, vector<vector<FiniteField>>> cache;
  function<vector<vector<FiniteField>>(int64)> find_matrix =
      [&](int64 p) -> vector<vector<FiniteField>> {
    if (cache.find(p) != cache.end()) {
      return cache.find(p)->second;
    }
    if (p <= d) {
      auto matrix = identity;
      for (int k = 0; k < p; k++) {
        matrix = units[k] * matrix;
      }
      return matrix;
    }
    int64 child_p = d;
    while ((p + child_p - 1) / child_p > d) child_p *= d;
    auto child = find_matrix(child_p);
    auto matrix = child;
    int64 remaining_p = p;
    remaining_p -= child_p;
    for (int k = 1; k < d; k++) {
      if (remaining_p >= child_p) {
        matrix = shifts[d - k] * child * shifts[k] * matrix;
        remaining_p -= child_p;
      } else if (remaining_p > 0) {
        matrix = shifts[d - k] * find_matrix(remaining_p) * shifts[k] * matrix;
        remaining_p = 0;
      } else {
        break;
      }
    }
    cache[p] = matrix;
    return matrix;
  };
  if (DEBUG) cerr << "PHASE 1" << endl;
  auto matrix = find_matrix(n);
  if (DEBUG) cerr << "PHASE 2" << endl;
  vector<FiniteField> base_vector(d + 1);
  base_vector[d] = 1;
  auto final_vector = matrix * base_vector;
  FiniteField ans = 0;
  for (const auto& x : final_vector) ans += x;
  cout << ans.Value() << endl;
}