#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <unordered_set>
#include <bit>

using namespace std;

ifstream fin("pascal.in");
ofstream fout("pascal.out");

const int MAXN = 5000002;

unsigned char sumDig[MAXN], sumDig2[MAXN];
int N, D;

void precomputeSumDigits(int Limit, int prime, unsigned char S[]) {
    S[0] = 0;
    int div = 0;
    int rem = 0;
    for (int i = 1; i <= Limit; ++i) {
        ++rem;
        if (rem == prime) {
            rem = 0;
            div++; 
            S[i] = S[div];
        } else {
            S[i] = S[i - 1] + 1;
        }
    }
}

inline int get_power_comb(int N, int K, int prime, unsigned char S[]) {
    return (S[K] + S[N - K] - S[N]) / (prime - 1);
}

int main() {
    fin >> N >> D;

    if (D == 2 || D == 3 || D == 5) {
        // Lucas theorem. Comb(N, i) is divisible by a prime p, iff at least one digit in the prime-base representation of N is smaller than the equivalent in i.
        // Therefore, the only numbers that aren't divisible by p, are the ones that have smaller or equal digits in prime-base.
        // Solution: Simply calculate their number

        int notDivisible = 1;
        int tmp = N;
        while (tmp) {
            notDivisible *= (tmp % D + 1);
            tmp /= D;
        }
        fout << N + 1 - notDivisible;
        return 0;
    }

    if (D == 4) {
        int ans = 0;
        precomputeSumDigits(N, 2, sumDig);
        for (int i = 0; i <= N; ++i) {
            if (get_power_comb(N, i, 2, sumDig) >= 2) ++ans;
        }
        fout << ans;
        return 0;
    }

    if (D == 6) {
        int ans = 0;
        precomputeSumDigits(N, 2, sumDig);
        precomputeSumDigits(N, 3, sumDig2);
        for (int i = 0; i <= N; ++i) {
            if (get_power_comb(N, i, 2, sumDig) >= 1 && get_power_comb(N, i, 3, sumDig2) >= 1) ++ans;
        }
        return 0;
    }

    return 0;
}