#include <fstream>
using namespace std;
long long x,i,d,n,sol,d1,d2,D,x1,x2,l,r,m,p1[100],p2[100],pm1,pm2,good,div1[5000010],div2[5000010];
int main()
{
    ifstream fi("pascal.in");
    ofstream fo("pascal.out");
    fi>>n>>D;
    if(D==6) { d1=2; d2=3; } else
    if(D==4) d1=2; else d1=D;
    p1[0]=p2[0]=1;
    for(i=1;p1[i-1]<n;i++) p1[i]=p1[i-1]*d1;
    pm1=i-1;
    if(d2) for(i=1;p2[i-1]<n;i++) p2[i]=p2[i-1]*d2;
    pm2=i-1;
    for(i=1;i<=n;i++)
    {
        x=i;
        div1[i]=div1[i-1];
        if(x%d1==0)
        {
            l=0; r=pm1;
            while(l<=r)
            {
                m=(l+r)/2;
                if(x%p1[m]) r=m-1; else { good=m; l=m+1; }

            }
            div1[i]+=good;
        }
        if(d2!=0) div2[i]=div2[i-1];
        if(d2!=0 and x%d2==0)
        {
            l=0; r=pm2;
            while(l<=r)
            {
                m=(l+r)/2;
                if(x%p2[m]) r=m-1; else { good=m; l=m+1; }
                if(l==r) break;
            }
            div2[i]+=good;
        }
    }
    //O(n)
    for(i=0;i<=n;i++)
    {
        if(D==6)
        {
            x1=div1[n]-div1[i]-div1[n-i];
            x2=div2[n]-div2[i]-div2[n-i];
            if(x1 and x2) sol++;
            continue;
        }
        else
        if(D==4)
        {
            x1=div1[n]-div1[n-i]-div1[i];
            if(x1>1) sol++;
            continue;
        }
        else
        {
            x1=div1[n]; x2=div1[n-i]+div1[i];
        }
        if(x1>x2)  sol++;

    }
    fo<<sol<<"\n";
    return 0;
}