#include <fstream>
#include <algorithm>

using namespace std;

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

int lucas (long long int n ,long long  int m , int p)
{
		if( m == 0)
				return 0;
		while(m)
		{
				if( m % p > n % p)
						return 1;
				m /= p;
				n /= p;

		}

		return 0;
}

int lucas2 ( long long int n , long long int m , int p)
{
		if( m == 0)
				return 0;

		int transport = 0 , exponent = 0 , var = n - m;
		
		while(n)
		{
				if( n % p + var % p + transport >= p)
				{
						exponent ++;
						transport = 1;
				}
				
				else
						transport = 0;
				n /= p;
				var /= p;

		}

		return exponent;
}

						
int main()
{
		long long int n;
		int d;

		fin >> n >> d;
		fin.close();

		int rezultat = 0;

		if ( d == 2 || d == 3 || d ==5)
		{
				for(int i = 0 ; i <= n ;i++)
						if(lucas(n,i,d))
								rezultat ++;
				fout << rezultat;
		}

		if( d == 6 )
		{
				for ( int i = 0 ; i < n ;i++)
						if(lucas(n,i,2) && lucas(n,i,3))
								rezultat ++;
				fout << rezultat ;
		}

		if ( d == 4)
		{
				for ( int i =0 ; i<n ;i++)
						if(lucas2(n,i,2) >= 2)
								rezultat ++;
				fout << rezultat;
		}

		fout.close();
		return 0;
}