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

using namespace std;

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

const int MAXN = 5000002;

int N, D, ans, digit_size;
unordered_set<int> invalid_numbers;
int digits[30];

void back(int lv, int value, int prime) {
    if (lv == -1) {
        invalid_numbers.insert(value);
        return;
    }

    for (int i = 0; i <= digits[lv]; ++i) {
        back(lv - 1, value * prime + i, prime);
    }
}

void compute(int prime) {
    int x = N;

    digit_size = 0;
    while (x) {
        digits[digit_size++] = x % prime;
        x /= prime;
    }
    if (digit_size == 0) ++digit_size;

    back(digit_size - 1, 0, prime);
}
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 generate all numbers that have smaller digits and put them into a set. 
        compute(D);

        fout << N + 1 - invalid_numbers.size();

        return 0;
    }

    if (D == 4) {
        for (int i = 0; i <= N; ++i) {
            // Kummer's theorem. The largest K such that p^k divides Comb(N, i) = number of carries when adding i and N-i
            // Check if there are at least 2 carries. These come from matching bits of 1 in (i) and (N - i).
            // Cases:
            // 1) There are no matching bits between i and N-i -> Comb(N, i) is not divisible by even 2
            // 2) There are more than one matching bits of 1 between i and N-i -> Comb(N, i) is at least divisible by 2^2
            // 3) There is exactly one matching bit of 1 between i and N-i. In order for Comb(N,i) to be divisible by 2^2, you need that carry to produce another carry.
            const int matching_bits = i & (N - i);
            // Case 1)
            if (matching_bits == 0) continue;
                        
            const int last_matching_bit = matching_bits & (-matching_bits);
            // Case 2)
            if (last_matching_bit != matching_bits) {
                ++ans;
                continue;
            }

            // Compute the remaining addition without the carry. It needs to be odd so that the previous carry produces another carry.
            const int remaining_addition = (i / last_matching_bit) / 2 + ((N - i) / last_matching_bit) / 2;
            if ((remaining_addition & 1) == 1) {
                ++ans;
            }

        }
        fout << ans;
        return 0;
    }

    if (D == 6) {
        // Same as D = 2,3,5 case, just that we invalidate all numbers that either are not divisible by 2 or by 3.
        
        compute(2);
        compute(3);

        fout << N + 1 - invalid_numbers.size();
        return 0;
    }

    return 0;
}