#include <cstdio>
// How many C(n, k) are not divisible by prime p.
// Lucas: one free digit 0..d for each base-p digit d of n.
int not_div(int n, int p) {
int prod = 1;
if (n == 0) return 1;
while (n > 0) {
prod *= (n % p) + 1;
n /= p;
}
return prod;
}
// How many C(n, k) have 2-adic valuation >= need (need is 1 or 2).
// Kummer: the valuation is the number of carries when adding k and n-k in base 2.
int div_by_pow2(int n, int need) {
int ways[2][3] = {};
ways[0][0] = 1;
while (n > 0) {
int bit = n & 1;
n >>= 1;
int nxt[2][3] = {};
for (int cin = 0; cin <= 1; cin++) {
for (int got = 0; got <= need; got++) {
int w = ways[cin][got];
if (w == 0) continue;
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
int sum = a + b + cin;
if ((sum & 1) != bit) continue;
int cout = sum >> 1;
int ngot = got + cout;
if (ngot > need) ngot = need;
nxt[cout][ngot] += w;
}
}
}
}
for (int c = 0; c <= 1; c++) {
for (int got = 0; got <= need; got++) ways[c][got] = nxt[c][got];
}
}
return ways[0][need];
}
int digits[16];
// k is a submask of n, and every base-3 digit of k is <= that of n.
int count_submasks(int n) {
int len = 0;
int x = n;
while (x > 0) {
digits[len++] = x % 3;
x /= 3;
}
if (len == 0) return 1;
int ans = 0;
int k = n;
while (true) {
int v = k;
bool ok = true;
for (int i = 0; i < len; i++) {
if (v % 3 > digits[i]) {
ok = false;
break;
}
v /= 3;
}
if (ok && v == 0) ans++;
if (k == 0) break;
k = (k - 1) & n;
}
return ans;
}
int count_base3(int pos, int len, int val, int pow3, int n) {
if (pos == len) return (val & n) == val;
int ans = 0;
for (int d = 0; d <= digits[pos]; d++) {
ans += count_base3(pos + 1, len, val + d * pow3, pow3 * 3, n);
}
return ans;
}
// C(n, k) not divisible by 2 and not divisible by 3.
int neither2nor3(int n) {
int odd = not_div(n, 2);
int not3 = not_div(n, 3);
if (odd <= not3) return count_submasks(n);
int len = 0;
int x = n;
while (x > 0) {
digits[len++] = x % 3;
x /= 3;
}
if (len == 0) return 1;
return count_base3(0, len, 0, 1, n);
}
int main() {
freopen("pascal.in", "r", stdin);
freopen("pascal.out", "w", stdout);
int r, d;
scanf("%d %d", &r, &d);
int ans = 0;
if (d == 2 || d == 3 || d == 5) {
ans = (r + 1) - not_div(r, d);
} else if (d == 4) {
ans = div_by_pow2(r, 2);
} else {
// divisible by 6 = divisible by 2 and by 3
int total = r + 1;
int not2 = not_div(r, 2);
int not3 = not_div(r, 3);
ans = total - not2 - not3 + neither2nor3(r);
}
printf("%d\n", ans);
return 0;
}