#include <bits/stdc++.h>
#define mod 1000000009
using namespace std;
ifstream fin("pascal.in");
ofstream fout("pascal.out");


int main()
{
    int n,d,k,s = 0;
    long long val = 1;
    fin >> n >> d;
    //nr din triunghiul lui pascal de pe linia n pozitia k = C(n - 1,k) = (n - 1)! / (k! * (n - 1 - k)!)
    // C(n,k + 1) = C(n,k) * (n - k) / (k + 1);
    for(k = 1; k < n; k++){
        val *= (n + 1 - k);
        val /= k;
        val %= mod;
        if(val % d == 0) s++;
    }
    fout << s;
    return 0;
}