var j,r,d,p:longint;
    a,b,c,n:longint;
    f,g:text;
    ok,oki:boolean;

function exp(e,k:longint):longint;
var s,j,q:longint;
begin
q:=0;
j:=1;
repeat
s:=j;
    while j mod k=0 do
          begin
          q:=q+1;
          j:=j div k;
          end;
    j:=s+1;
until(j=e+1) or (e=0) or (e=1);
exp:=q;
end;


begin
assign(f,'pascal.in');
assign(g,'pascal.out');
reset(f);
rewrite(g);
readln(f,r,d);
c:=exp(r,d);
ok:=true;
if r mod 2=0 then ok:=false;
for j:=0 to ((r-1) div 2) do
    begin
    a:=exp(j,d);
    b:=exp(r-j,d);
    n:=c-(a+b);
    if n>0 then
       p:=p+1;
    end;


if ok then
   p:=p*2
   else begin
        p:=p*2;
        a:=exp(j+1,d);
        b:=exp(r-j-1,d);
        n:=c - (a*b);
        if n >0 then
           p:=p+1;
        end;

writeln(g,p);
close(f);
close(g);
end.