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;
int k = 34;
struct Matrix {
  long long a[35][35];
  Matrix() {
    for (int i = 0; i <= k; ++i) fill(a[i], a[i] + (k + 1), 0);
  }
  Matrix operator*(const Matrix &to) const {
    Matrix ans;
    for (int i = 0; i <= k; ++i)
      for (int k1 = 0; k1 <= k; ++k1)
        for (int j = 0; j <= k; ++j)
          ans.a[i][j] = (ans.a[i][j] + a[i][k1] * to.a[k1][j]) % 1000000007ll;
    return ans;
  }
} one;
vector<long long> operator*(const vector<long long> &v, const Matrix &to) {
  vector<long long> ans(k + 1);
  for (int i = 0; i <= k; ++i)
    for (int j = 0; j <= k; ++j)
      ans[j] = (ans[j] + v[i] * to.a[i][j]) % 1000000007ll;
  return ans;
}
Matrix initial(int t) {
  Matrix ans;
  for (int i = 0; i < k; ++i)
    if (i != t) {
      ans.a[i][i] = 1;
    } else {
      ans.a[i][k] = 1;
    }
  ans.a[k][k] = 2;
  ans.a[k][t] = -1;
  return ans;
}
long long sum(long long n) {
  long long ans = 0;
  while (n) {
    ans += n % k;
    n /= k;
  }
  return ans % k;
}
void get(long long n, vector<Matrix> A, vector<long long> &S) {
  if (n == 0) return;
  vector<Matrix> tA(k);
  vector<Matrix> suff(k + 1), pref(k + 1);
  pref[0] = one;
  for (int i = 0; i < k; ++i) {
    pref[i + 1] = pref[i] * A[i];
  }
  suff[k] = one;
  for (int i = k - 1; i >= 0; --i) {
    suff[i] = A[i] * suff[i + 1];
  }
  for (int i = 0; i < k; ++i) {
    tA[i] = suff[i] * pref[i];
  }
  long long b = n / k;
  get(b, tA, S);
  for (int i = sum(b * k); i < sum(b * k) + n % k; ++i) S = S * A[i % k];
}
int main() {
  ios_base::sync_with_stdio(false);
  for (int i = 0; i < 35; ++i) one.a[i][i] = 1;
  long long n;
  cin >> n >> k;
  vector<Matrix> to;
  for (int i = 0; i < k; ++i) to.push_back(initial(i));
  vector<long long> b(k + 1);
  b[k] = 1;
  get(n, to, b);
  long long ans = b[k];
  if (ans < 0) ans += 1000000007ll;
  cout << ans << "\n";
  return 0;
}