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 mo = 1e9 + 7;
inline void inc(int &first, int second) {
  if ((first += second) >= mo) first -= mo;
}
inline void glance() { freopen("ha.in", "r", stdin); }
long long N;
int an, K, n, a[66];
struct Mat {
  int a[32][32];
  int *operator[](const int &first) { return a[first]; }
  Mat(bool b = 0) {
    for (int _r = K, i = 0; i <= _r; ++i)
      for (int _r = K, j = 0; j <= _r; ++j) a[i][j] = i == j && b;
  }
  Mat operator*(Mat &B) {
    Mat C = Mat();
    for (int _r = K, i = 0; i <= _r; ++i)
      for (int _r = K, j = 0; j <= _r; ++j)
        for (int _r = K, k = 0; k <= _r; ++k)
          inc(C[i][j], 1ll * a[i][k] * B[k][j] % mo);
    return C;
  }
} A, pre[32], suf[32], F[66][32];
inline void pret() {
  for (int _r = K, i = 0; i < _r; ++i) {
    for (int _r = K, j = 0; j <= _r; ++j) F[0][i][j][j] = F[0][i][i][j] = 1;
  }
  for (int _r = n, i = 1; i <= _r; ++i) {
    pre[0] = Mat(1);
    for (int _r = K, j = 1; j < _r; ++j) pre[j] = F[i - 1][j - 1] * pre[j - 1];
    suf[K - 1] = F[i - 1][K - 1];
    for (int _l = 0, j = K - 2; j >= _l; --j) suf[j] = suf[j + 1] * F[i - 1][j];
    for (int _r = K, m = 0; m < _r; ++m) F[i][m] = pre[m] * suf[m];
  }
}
int main() {
  scanf("%I64d%d", &N, &K);
  A = Mat(1);
  for (; N; N /= K) a[n++] = N % K;
  --n;
  pret();
  int la = 0;
  for (int _l = 0, i = n; i >= _l; --i) {
    for (int _r = a[i], j = 0; j < _r; ++j) A = F[i][(la + j) % K] * A;
    la = (la + a[i]) % K;
  }
  for (int _r = K, i = 0; i <= _r; ++i) inc(an, A[i][K]);
  printf("%d\n", an);
}