#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 101;
const int LOG = 63;
int dp[M][M][LOG], dp2[M][M], last, alldp[M][M];
int dp3[M][LOG], dp4[M][LOG];
int m;
void solve(int idx, long long len) {
  if (len == 1) {
    dp[0][0][idx] = 1;
    dp3[1][idx] = 1;
    last = idx;
    return;
  }
  solve(idx + 1, len / 2);
  dp3[len % m][idx] = 1;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < m; k++) {
        dp[i][j][idx] += (long long)dp[i][k][idx + 1] *
                         dp[(k == 0 ? 0 : m - k)][j][idx + 1] % 1000000007;
        if (dp[i][j][idx] >= 1000000007) dp[i][j][idx] -= 1000000007;
        dp[i][j][idx] += (long long)dp[i][k][idx + 1] *
                         dp3[(j - k < 0 ? j - k + m : j - k)][idx + 1] %
                         1000000007;
        if (dp[i][j][idx] >= 1000000007) dp[i][j][idx] -= 1000000007;
        dp[i][j][idx] += (long long)dp[k][j][idx + 1] *
                         dp3[(i - k < 0 ? i - k + m : i - k)][idx + 1] %
                         1000000007;
        if (dp[i][j][idx] >= 1000000007) dp[i][j][idx] -= 1000000007;
      }
    }
  }
}
long long n;
int main() {
  cin >> n >> m;
  for (int i = 61; i >= 0; i--) {
    if (((n >> i) & 1) == 1) {
      solve(0, ((long long)1 << (long long)i));
      break;
    }
  }
  int idx = last;
  bool notyet = true;
  for (int i = 0; i < 62; i++) {
    if (((n >> i) & 1) == 1) {
      if (notyet) {
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < m; j++) {
            alldp[i][j] = dp[i][j][idx];
          }
        }
        for (int i = 0; i < m; i++) {
          alldp[0][i] += dp3[i][idx];
          if (alldp[0][i] >= 1000000007) alldp[0][i] -= 1000000007;
        }
        notyet = false;
      } else {
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < m; j++) {
            dp2[i][j] = alldp[i][j];
            alldp[i][j] = 0;
          }
        }
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
              alldp[i][j] += (long long)dp2[i][k] *
                             dp[(k == 0 ? 0 : m - k)][j][idx] % 1000000007;
              if (alldp[i][j] >= 1000000007) alldp[i][j] -= 1000000007;
              alldp[i][j] += (long long)dp2[i][k] *
                             dp3[(j - k < 0 ? j - k + m : j - k)][idx] %
                             1000000007;
              if (alldp[i][j] >= 1000000007) alldp[i][j] -= 1000000007;
            }
          }
        }
      }
    }
    idx--;
  }
  cout << alldp[0][0] << endl;
  return 0;
}
