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 getint() {
  int s = 0, o = 1;
  char c;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    if (c == '-') o = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) s *= 10, s += c - '0';
  return s * o;
}
const int mod = (int)1e9 + 7;
struct Mat {
  int n;
  long long x;
  int a[31][31];
  void operator*=(const Mat &p) {
    int c[31][31];
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        long long r = 0;
        for (int k = 0; k < n; k++) r += (1ll * a[i][k] * p.a[k][j]) % mod;
        c[i][j] = r % mod;
        if (c[i][j] < 0) c[i][j] += mod;
      }
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) a[i][j] = c[i][j];
  }
  void write() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) printf("%d ", a[i][j]);
      printf("\n");
    }
  }
} A[70][30], B[70][30];
long long n;
int k;
Mat I;
Mat calc(int i, int j, long long n) {
  Mat r = I;
  if (n == 0) return r;
  for (int timer = 0; timer < k; timer++) {
    if (n >= A[i][j].x)
      r *= A[i][j];
    else
      r *= calc(i - 1, j, n);
    n -= A[i][j].x;
    if (n <= 0) break;
    j = (j + 1) % k;
  }
  return r;
}
int main(int argc, char const *argv[]) {
  scanf("%I64d%d", &n, &k);
  I.n = k + 1;
  for (int i = 0; i < I.n; i++)
    for (int j = 0; j < I.n; j++) I.a[i][j] = i == j;
  for (int i = 0; i < k; i++) {
    Mat &M = A[0][i];
    M.n = k + 1, M.x = 1;
    for (int t = 0; t < k + 1; t++)
      for (int s = 0; s < k + 1; s++) M.a[t][s] = (t == s || t == i);
    Mat &N = B[0][i];
    N.n = k + 1, N.x = 1;
    for (int t = 0; t < k + 1; t++)
      for (int s = 0; s < k + 1; s++) {
        if (t == i) N.a[t][s] = -1;
        if (t == s) N.a[t][s] = 1;
      }
  }
  int i;
  for (i = 0;; i++) {
    long long _x = A[i][0].x * k;
    if (_x > n || _x < 0) break;
    Mat &M = A[i + 1][0];
    M = A[i][0];
    M.x = _x;
    for (int p = 1; p < k; ++p) M *= A[i][p];
    for (int j = 1; j < k; ++j) {
      Mat &M = A[i + 1][j];
      M = B[i][j - 1];
      M *= A[i + 1][j - 1];
      M *= A[i][j - 1];
      M.x = _x;
    }
    Mat &N = B[i + 1][0];
    N = B[i][k - 1];
    N.x = _x;
    for (int p = k - 2; p >= 0; --p) N *= B[i][p];
    for (int j = 1; j < k; ++j) {
      Mat &N = B[i + 1][j];
      N = B[i][j - 1];
      N *= B[i + 1][j - 1];
      N *= A[i][j - 1];
      N.x = _x;
    }
  }
  Mat res = calc(i, 0, n);
  long long r = 0;
  for (int i = 0; i < k + 1; i++) r += res.a[i][k];
  printf("%I64d\n", r % mod);
  return 0;
}