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 getre() {
  int x = 0;
  printf("%d\n", 1 / x);
}
void gettle() {
  int res = 1;
  while (1) res <<= 1;
  printf("%d\n", res);
}
template <typename T, typename S>
inline bool upmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename N, typename PN>
inline N flo(N a, PN b) {
  return a >= 0 ? a / b : -((-a - 1) / b) - 1;
}
template <typename N, typename PN>
inline N cei(N a, PN b) {
  return a > 0 ? (a - 1) / b + 1 : -(-a / b);
}
template <typename N>
N gcd(N a, N b) {
  return b ? gcd(b, a % b) : a;
}
template <typename N>
inline int sgn(N a) {
  return a > 0 ? 1 : (a < 0 ? -1 : 0);
}
inline void gn(long long &x) {
  int sg = 1;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  c == '-' ? (sg = -1, x = 0) : (x = c - '0');
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  x *= sg;
}
inline void gn(int &x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(unsigned long long &x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gn(long double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gs(char *s) { scanf("%s", s); }
inline void gc(char &c) {
  while ((c = getchar()) > 126 || c < 33)
    ;
}
inline void pc(char c) { putchar(c); }
inline long long sqr(long long a) { return a * a; }
inline double sqrf(double a) { return a * a; }
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846264338327950288L;
const double eps = 1e-6;
const int mo = 1e9 + 7;
int qp(int a, long long b) {
  int n = 1;
  do {
    if (b & 1) n = 1ll * n * a % mo;
    a = 1ll * a * a % mo;
  } while (b >>= 1);
  return n;
}
long long n;
int k;
const int MM_N = 33;
int mm_n;
struct mat {
  int a[MM_N][MM_N];
  void plus() {
    for (int i = (0), _ed = (mm_n); i < _ed; i++)
      for (int j = (0), _ed = (mm_n); j < _ed; j++)
        a[i][j] = (a[i][j] % mo + mo) % mo;
  }
} one;
mat operator*(const mat &a, const mat &b) {
  static long long ans[MM_N][MM_N];
  memset((ans), (0), sizeof(ans));
  long long infa = 8e18;
  for (int k = (0), _ed = (mm_n); k < _ed; k++)
    for (int i = (0), _ed = (mm_n); i < _ed; i++)
      for (int j = (0), _ed = (mm_n); j < _ed; j++) {
        if ((ans[i][j] += 1ll * a.a[i][k] * b.a[k][j]) >= infa) ans[i][j] %= mo;
      }
  mat c;
  for (int i = (0), _ed = (mm_n); i < _ed; i++)
    for (int j = (0), _ed = (mm_n); j < _ed; j++) c.a[i][j] = ans[i][j] % mo;
  return c;
}
mat qp(mat a, long long b) {
  a.plus();
  mat n = one;
  do {
    if (b & 1) n = n * a;
    a = a * a;
  } while (b >>= 1);
  return n;
}
void mm_init(int sz) {
  mm_n = sz;
  for (int i = (0), _ed = (mm_n); i < _ed; i++) one.a[i][i] = 1;
}
int nu[111];
int tot = 0;
mat a[100];
mat jia(const mat &x, int d) {
  mat ret;
  for (int i = (0), _ed = (k + 1); i < _ed; i++)
    for (int j = (0), _ed = (k + 1); j < _ed; j++)
      ret.a[i != k ? (i + d) % k : k][j != k ? (j + d) % k : k] = x.a[i][j];
  return ret;
}
int main() {
  gn(n);
  gn(k);
  mm_init(k + 1);
  while (n) {
    nu[tot++] = n % k;
    n /= k;
  }
  for (int j = 0; j <= k; j++) a[0].a[0][j] = 1;
  for (int j = 0; j <= k; j++) a[0].a[j][j] = 1;
  for (int i = 1; i < tot; i++) {
    mat now = one;
    for (int j = (0), _ed = (k); j < _ed; j++) now = now * jia(a[i - 1], j);
    a[i] = now;
  }
  int ad = 0;
  mat ans = one;
  for (int i = tot - 1; i >= 0; i--) {
    for (int j = 0; j < nu[i]; j++) ans = ans * jia(a[i], (j + ad) % k);
    ad = (ad + nu[i]) % k;
  }
  int ret = 0;
  for (int i = (0), _ed = (k + 1); i < _ed; i++)
    (((ret) = ((ret) + (ans.a[i][k])) % mo) < 0 ? (ret) += mo : (ret));
  printf("%d\n", ret);
  return 0;
}