#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("pascal.in");
ofstream g("pascal.out");

long long Pow[7][24]=
{
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608},
{1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,0,0,0,0,0,0,0,0},
{1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,0,0,0,0,0,0,0,0,0,0,0},
{1,5,25,125,625,3125,15625,78125,390625,1953125,9765625,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,6,36,216,1296,7776,46656,279936,1679616,10077696,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};
long R,D,nr,Nfact,Nkfact,kfact;

int ExtrageExponentFactorial(long n,int D)
{
    int nr=0,i=1;
    while(n>=Pow[D][i]) nr+=(n/Pow[D][i]),i++;
    return nr;
}

int ExtrageExponent(long n,int D)
{
    int exp=0,N=n;
    while(N % D==0) N/=D,exp++;
    return exp;
}


void Numara(int R,int D)

{
    if(R<=1)return;
    else
    if(R==2)
    {
        if(D==2)nr=1;
        else return;
    }
    else
    if(R==3)
    {
        if(D==3)nr=2;
        else return;
    }
    else
    {
        if(R % D==0)nr+=2;
        Nfact=ExtrageExponentFactorial(R,D);
        if(R % 2==0)
        {
            Nkfact=(ExtrageExponentFactorial(R/2,D));
            if(Nfact-2*Nkfact>0) nr++;
        }
        else
        {
            Nkfact=(ExtrageExponentFactorial(R/2,D));
            kfact=(ExtrageExponentFactorial(R-R/2,D));
            if(Nfact-Nkfact-kfact>0) nr+=2;
        }
        Nkfact=ExtrageExponentFactorial(R-1,D);
        kfact=0;
        int i;
        for(i=2;i<=-1+(R/2);i++)
        {
            Nkfact-=(ExtrageExponent(R-i+1,D));
            kfact+=(ExtrageExponent(i,D));
            if(Nfact-Nkfact-kfact>0) nr+=2;
        }
    }
}
void solve()
{
    f>>R>>D;
    nr=0;
    Numara(R,D);
    g<<nr<<'\n';
}

int main ()
{

    //int t;
    //f>>t;
    //for(int p=1;p<=t;p++)solve();
    solve();
    f.close();g.close();
    return 0;
}