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;
template <class T>
T Mul(T x, T y, T P) {
  T F1 = 0;
  while (y) {
    if (y & 1) {
      F1 += x;
      if (F1 < 0 || F1 >= P) F1 -= P;
    }
    x <<= 1;
    if (x < 0 || x >= P) x -= P;
    y >>= 1;
  }
  return F1;
}
template <class T>
T Pow(T x, T y, T P) {
  T F1 = 1;
  x %= P;
  while (y) {
    if (y & 1) {
      F1 = Mul(F1, x, P);
    }
    x = Mul(x, x, P);
    y >>= 1;
  }
  return F1;
}
template <class T>
T Gcd(T x, T y) {
  if (y == 0) return x;
  T z;
  while (z = x % y) {
    x = y, y = z;
  }
  return y;
}
template <class T>
void UpdateMin(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <class T>
void UpdateMax(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <class T>
T Sqr(const T x) {
  return x * x;
}
template <class T>
T Abs(const T x) {
  return x < 0 ? -x : x;
}
class ReadBuffer {
 private:
  char buff[20000000];
  char *buf;

 public:
  void init(int size = 20000000) {
    fread(buff, 1, size, stdin);
    buf = buff;
  }
  template <class T>
  bool readInteger(T &x) {
    x = 0;
    while (*buf && isspace(*buf)) ++buf;
    if (*buf == 0) return false;
    static bool flag;
    flag = 0;
    if (*buf == '-')
      flag = true;
    else
      x = *buf - '0';
    while (isdigit(*++buf)) x = x * 10 + *buf - '0';
    if (flag) x = -x;
    return true;
  }
  template <class T>
  bool readFloat(T &x) {
    long double nowpos = 0.1;
    x = 0;
    while (*buf && isspace(*buf)) ++buf;
    if (*buf == 0) return false;
    static bool flag, decimal;
    decimal = flag = 0;
    if (*buf == '-')
      flag = true, ++buf;
    else if (*buf == '.')
      decimal = true;
    while (isdigit(*buf) || *buf == '.') {
      if (*buf == '.')
        decimal = true;
      else {
        if (decimal) {
          x += nowpos * (*buf - '0');
          nowpos *= 0.1;
        } else {
          x = x * 10 + *buf - '0';
        }
      }
      ++buf;
    }
    return true;
  }
  bool readChar(char c) {
    if (*buf == 0) return 0;
    return c = *buf++, 1;
  }
  bool readString(char *s) {
    while (*buf && isspace(*buf)) ++buf;
    if (!*buf) return false;
    while (!isspace(*buf)) *s++ = *buf++;
    *s++ = 0;
    return true;
  }
  int countSpacetonext() {
    int total = 0;
    while (*buf && *buf == ' ') ++total, ++buf;
    return total;
  }
  bool splitBycharactor(char *s, char Split = '\n') {
    while (*buf && *buf != Split) *s++ = *buf++;
    *s++ = 0;
    return *buf != 0;
  }
};
struct EDGE {
  int T;
  EDGE *Nxt;
};
long long F[31][31];
long long n;
int m;
struct matrix {
  long long M[31][31];
  long long *operator[](const int dn) { return M[dn]; }
  void Rot(int x) {
    for (int i = 0; i < m; ++i)
      for (int j = 0; j <= m; ++j) F[i][j] = M[i][j];
    int f = x;
    for (int i = 0; i < m; ++i) {
      M[f][m] = F[i][m];
      int g = x;
      for (int j = 0; j < m; ++j) {
        M[f][g] = F[i][j];
        if (++g == m) g = 0;
      }
      if (++f == m) f = 0;
    }
  }
} M[64][30], C, E;
long long now[33];
long long D[33];
vector<long long> Dec;
const int mod = 1000000007;
void Mul(matrix &A, matrix &B) {
  for (int i = 0; i <= m; ++i)
    for (int j = 0; j <= m; ++j)
      for (int k = 0; k <= m; ++k) {
        C[i][j] += B[i][k] * A[k][j];
        if (C[i][j] >= mod) C[i][j] %= mod;
      }
  for (int i = 0; i <= m; ++i)
    for (int j = 0; j <= m; ++j) A[i][j] = C[i][j], C[i][j] = 0;
}
void Mul(long long A[], matrix &B) {
  for (int i = 0; i <= m; ++i)
    for (int j = 0; j <= m; ++j) {
      D[i] += B[i][j] * A[j];
      if (D[i] >= mod) D[i] %= mod;
    }
  for (int i = 0; i <= m; ++i) A[i] = D[i], D[i] = 0;
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i <= m; ++i) {
    E[i][i] = 1;
  }
  for (int j = 0; j <= m; ++j) M[0][0][j][j] = M[0][0][0][j] = 1;
  for (int i = 1; i < m; ++i) {
    M[0][i] = M[0][0];
    M[0][i].Rot(i);
  }
  while (n) {
    Dec.push_back(n % m);
    n /= m;
  }
  for (int i = 1; i < int(Dec.size()); ++i) {
    M[i][0] = E;
    for (int j = 0; j < m; ++j) {
      Mul(M[i][0], M[i - 1][j]);
    }
    for (int j = 1; j < m; ++j) {
      M[i][j] = M[i][0];
      M[i][j].Rot(j);
    }
  }
  now[m] = 1;
  int presum = 0;
  for (int i = int(Dec.size()) - 1; i >= 0; --i) {
    for (int j = 0; j < Dec[i]; ++j) {
      Mul(now, M[i][(j + presum) % m]);
    }
    presum += Dec[i];
    if (presum >= m) presum %= m;
  }
  long long ans = 0;
  for (int i = 0; i <= m; ++i) {
    ans += now[i];
    if (ans >= mod) ans -= mod;
  }
  cout << ans << endl;
}
int main() {
  solve();
  cin >> n;
  return 0;
}