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;
const int P = 1000000007;
long long n;
int m;
struct Matrix {
  int data[30][30];
  Matrix() { memset(data, 0, sizeof(data)); }
  int* operator[](int x) { return data[x]; }
};
Matrix operator+(Matrix x, Matrix y) {
  Matrix z;
  for (int i = 0; i <= m - 1; i++)
    for (int j = 0; j <= m - 1; j++) z[i][j] = (x[i][j] + y[i][j]) % P;
  return z;
}
Matrix operator*(Matrix x, Matrix y) {
  Matrix z;
  for (int i = 0; i <= m - 1; i++)
    for (int k = 0; k <= m - 1; k++)
      for (int j = 0; j <= m - 1; j++)
        z[i][j] = (z[i][j] + (long long)x[i][k] * y[k][j]) % P;
  return z;
}
void calc(Matrix mul[], Matrix add[], Matrix mu_[], Matrix ad_[]) {
  static Matrix mu0[30], ad0[30];
  static Matrix mu1[30], ad1[30];
  mu0[0] = mu_[0];
  ad0[0] = ad_[0];
  for (int i = 1; i <= m - 1; i++) {
    mu0[i] = mu0[i - 1] * mu_[i];
    ad0[i] = ad0[i - 1] * mu_[i] + ad_[i];
  }
  mu1[m - 1] = mu_[m - 1];
  ad1[m - 1] = ad_[m - 1];
  for (int i = m - 2; i >= 0; i--) {
    mu1[i] = mu_[i] * mu1[i + 1];
    ad1[i] = ad_[i] * mu1[i + 1] + ad1[i + 1];
  }
  for (int i = 0; i <= m - 1; i++) {
    mul[i] = mu1[i];
    add[i] = ad1[i];
    if (i > 0) {
      mul[i] = mul[i] * mu0[i - 1];
      add[i] = add[i] * mu0[i - 1] + ad0[i - 1];
    }
  }
}
Matrix mul[60][30];
Matrix add[60][30];
int val[60], cnt = -1;
int main() {
  cin >> n >> m;
  while (n) {
    val[++cnt] = n % m;
    n = n / m;
  }
  for (int i = 0; i <= m - 1; i++) {
    for (int j = 0; j <= m - 1; j++) mul[0][i][j][j] = 1;
    for (int j = 0; j <= m - 1; j++) mul[0][i][j][i] = 1;
    add[0][i][0][i] = 1;
  }
  for (int k = 1; k <= cnt; k++) {
    calc(mul[k], add[k], mul[k - 1], add[k - 1]);
  }
  Matrix ans;
  int k = 0;
  for (int i = cnt; i >= 0; i--) {
    for (int j = 1; j <= val[i]; j++) {
      ans = ans * mul[i][k] + add[i][k];
      k = (k + 1) % m;
    }
  }
  int res = 1;
  for (int i = 0; i <= m - 1; i++) res = (res + ans[0][i]) % P;
  cout << res << endl;
  return 0;
}