#include <iostream>
#include<fstream>
using namespace std;
ifstream fin("pascal.in");
ofstream fout("pascal.out");
int main() {
    long long R;
    int D;
    fin >> R >> D;

    if (D == 2 || D == 3 || D == 5) {
        long long produs = 1;
        long long x = R;

        while (x > 0) {
            produs = produs * (x % D + 1);
            x = x / D;
        }

        fout << R + 1 - produs;
        return 0;
    }

    long long cnt = 0;

    if (D == 4) {
        long long sumaR = 0, x = R;

        while (x > 0) {
            sumaR = sumaR + x % 2;
            x = x / 2;
        }

        long long v2R = R - sumaR;

        for (long long k = 0; k <= R; k++) {
            long long sumaK = 0, sumaRK = 0;

            x = k;
            while (x > 0) {
                sumaK = sumaK + x % 2;
                x = x / 2;
            }

            x = R - k;
            while (x > 0) {
                sumaRK = sumaRK + x % 2;
                x = x / 2;
            }

            long long v2 = v2R - (k - sumaK) - ((R - k) - sumaRK);

            if (v2 >= 2)
                cnt = cnt + 1;
        }

        fout << cnt;
    }

    if (D == 6) {
        long long sumaR2 = 0, sumaR3 = 0, x = R;

        while (x > 0) {
            sumaR2 = sumaR2 + x % 2;
            x = x / 2;
        }

        x = R;
        while (x > 0) {
            sumaR3 = sumaR3 + x % 3;
            x = x / 3;
        }

        long long v2R = R - sumaR2;
        long long v3R = (R - sumaR3) / 2;

        for (long long k = 0; k <= R; k++) {
            long long sumaK2 = 0, sumaRK2 = 0;
            long long sumaK3 = 0, sumaRK3 = 0;

            x = k;
            while (x > 0) {
                sumaK2 = sumaK2 + x % 2;
                x = x / 2;
            }

            x = R - k;
            while (x > 0) {
                sumaRK2 = sumaRK2 + x % 2;
                x = x / 2;
            }

            long long v2 = v2R - (k - sumaK2) - ((R - k) - sumaRK2);

            x = k;
            while (x > 0) {
                sumaK3 = sumaK3 + x % 3;
                x = x / 3;
            }

            x = R - k;
            while (x > 0) {
                sumaRK3 = sumaRK3 + x % 3;
                x = x / 3;
            }

            long long v3 = v3R - (k - sumaK3) / 2 - ((R - k) - sumaRK3) / 2;

            if (v2 >= 1 && v3 >= 1)
                cnt = cnt + 1;
        }

        fout << cnt;
    }

    return 0;
}