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;
struct matrix {
  long long e[40][40];
  static int sz;
  matrix(bool iden = false) {
    memset(e, 0, sizeof(e));
    int i;
    if (iden) {
      for (i = 0; i < sz; i++) e[i][i] = 1;
    }
  }
  matrix operator*(const matrix &rhs) const {
    matrix r;
    int i, j, k;
    for (i = 0; i < sz; i++) {
      for (j = 0; j < sz; j++) {
        for (k = 0; k < sz; k++) {
          r.e[i][j] += e[i][k] * rhs.e[k][j];
          r.e[i][j] %= 1000000007;
        }
      }
    }
    return r;
  }
  vector<long long> operator*(const vector<long long> &v) const {
    int i, j;
    vector<long long> ret(sz, 0);
    for (i = 0; i < sz; i++) {
      for (j = 0; j < sz; j++) {
        ret[i] += e[i][j] * v[j];
        ret[i] %= 1000000007;
      }
    }
    return ret;
  }
  matrix shift(int r) const {
    matrix tmp;
    int i, j;
    for (i = 0; i < sz; i++) {
      for (j = 0; j < sz; j++) {
        tmp.e[i == sz - 1 ? sz - 1 : (i + r) % (sz - 1)]
             [j == sz - 1 ? sz - 1 : (j + r) % (sz - 1)] = e[i][j];
      }
    }
    return tmp;
  }
  void print() const {
    int i, j;
    for (i = 0; i < sz; i++) {
      for (j = 0; j < sz; j++) {
        printf("%d ", e[i][j]);
      }
      putchar('\n');
    }
  }
} A[100];
int matrix::sz;
int main() {
  long long n, r = 1, sum = 0;
  int k, i, j, w, up = 0, os;
  matrix B;
  scanf("%I64d%d", &n, &k);
  matrix::sz = k + 1;
  vector<long long> ans(k + 1, 0);
  ans[k] = 1;
  for (i = 0; i < k + 1; i++) {
    A[0].e[0][i] = A[0].e[i][i] = 1;
  }
  while (n / r >= k) {
    r *= k;
    up++;
  }
  for (i = 1; i <= up; i++) {
    B = A[i - 1];
    A[i] = matrix(true);
    j = k;
    w = 0;
    while (j) {
      if (j & 1) {
        A[i] = A[i] * B.shift((j ^ 1) << w);
      }
      B = B.shift(1 << w) * B;
      w++;
      j >>= 1;
    }
  }
  os = 0;
  while (n) {
    for (i = 0; i < n / r; i++) {
      ans = A[up].shift(os + i) * ans;
    }
    os = (os + i) % k;
    n %= r;
    r /= k;
    up--;
  }
  for (i = 0; i < k + 1; i++) {
    sum = (sum + ans[i]) % 1000000007;
  }
  printf("%I64d\n", sum);
  return 0;
}