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;
void File() {
  freopen("rudy.in", "r", stdin);
  freopen("rudy.out", "w", stdout);
}
template <typename T>
void read(T &_) {
  T __ = 0, mul = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') mul = -1;
    ch = getchar();
  }
  while (isdigit(ch)) __ = (__ << 1) + (__ << 3) + (ch ^ '0'), ch = getchar();
  _ = __ * mul;
}
const int maxn = 100 + 10;
const long long mod = 1e9 + 7;
int k, tot;
long long n, dp[maxn];
struct Matrix {
  long long c[maxn][maxn];
  Matrix() {
    for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i)
      for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j) c[i][j] = 0;
  }
} d[maxn], f[maxn], g[maxn], gg[maxn];
Matrix operator*(Matrix a, Matrix b) {
  Matrix ret;
  for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i)
    for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
      for (int p = 1, p_end_ = k + 1; p <= p_end_; ++p)
        ret.c[i][j] = (ret.c[i][j] + a.c[i][p] * b.c[p][j]) % mod;
  return ret;
}
void out(Matrix a) {
  for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i) {
    for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
      printf("%lld ", a.c[i][j]);
    printf("\n");
  }
}
void init() {
  read(n), read(k);
  tot = k;
  for (int m = 0, m_end_ = tot; m <= m_end_; ++m) {
    d[m].c[1][k + 1] = 1;
    for (int i = 2, i_end_ = k + 1; i <= i_end_; ++i) {
      for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
        d[m].c[i][j] = d[m].c[i - 1][j] * 2 % mod;
      int p = ((i + m - 1) % k + k) % k;
      if (p == 0) p = k;
      d[m].c[i][p] = (d[m].c[i][p] - 1) % mod;
    }
  }
}
Matrix qpow(Matrix x, long long y) {
  Matrix ret;
  for (int i = 1, i_end_ = k + 1; i <= i_end_; ++i)
    for (int j = 1, j_end_ = k + 1; j <= j_end_; ++j)
      if (i == j)
        ret.c[i][j] = 1;
      else
        ret.c[i][j] = 0;
  while (y) {
    if (y & 1) ret = ret * x;
    x = x * x;
    y >>= 1;
  }
  return ret;
}
void work() {
  int lim = ceil(log(n) / log(k));
  for (int i = 1, i_end_ = lim; i <= i_end_; ++i) {
    g[i] = d[i % k];
    for (int l = 1, l_end_ = k + 1; l <= l_end_; ++l)
      for (int r = 1, r_end_ = k + 1; r <= r_end_; ++r)
        if (l == r)
          f[i].c[l][r] = 1;
        else
          f[i].c[l][r] = 0;
    for (int j = 1, j_end_ = i - 1; j <= j_end_; ++j) {
      f[i] = f[i] * gg[j];
      g[i] = g[i] * gg[j];
    }
    gg[i] = qpow(g[i], k - 1);
  }
  Matrix ans;
  for (int l = 1, l_end_ = k + 1; l <= l_end_; ++l)
    for (int r = 1, r_end_ = k + 1; r <= r_end_; ++r)
      if (l == r)
        ans.c[l][r] = 1;
      else
        ans.c[l][r] = 0;
  int las = 1;
  while (n >= k) {
    int w = 0;
    for (long long tmp = n; tmp >= k; tmp /= k) ++w;
    ans = f[w] * d[las % k] * ans;
    las = w;
    long long tmp = 1;
    for (int i = 1, i_end_ = w; i <= i_end_; ++i) tmp *= k;
    n -= tmp;
  }
  if (n == 0)
    printf("%lld\n", (ans.c[k + 1][k + 1] % mod + mod) % mod);
  else {
    ans = d[las % k] * ans;
    printf("%lld\n", (ans.c[n + 1][k + 1] % mod + mod) % mod);
  }
}
int main() {
  init();
  work();
  return 0;
}