program hio;
var f:text;
    tot,i,r,d,qr,qr2:longint;

function calc(a,b,d:longint):longint;
var sa,p:longint;
begin
sa:=0;
p:=d;
while (a div p)>0 do
      begin
      sa:=sa+(a div p);
      p:=p*d;
      end;
p:=d;
while b div p>0 do
      begin
      sa:=sa+(b div p);
      p:=p*d;
      end;
calc:=sa;
end;




begin {pp}
assign(f,'pascal.in');reset(f);
read(f,r,d);
close(f);
tot:=0;
case d of
     2:
     begin
     qr:=calc(r,1,d);
     for i:=0 to (r div 2)-1 do
         if qr-calc(i,r-i,d)>0 then inc(tot,2);
     if r mod 2=0 then
        if (qr-calc(i+1,r-i-1,d)>0) then inc(tot);
     end;
     3:
     begin
     qr:=calc(r,1,d);
     for i:=0 to (r div 2)-1 do
         if qr-calc(i,r-i,d)>0 then inc(tot,2);
     if r mod 2=0 then
        if (qr-calc(i+1,r-i-1,d)>0) then inc(tot);
     end;
     4:
     begin
     qr:=calc(r,1,2);
     for i:=0 to (r div 2)-1 do
         if ((qr-calc(i,r-i,2)) div 2)>0 then inc(tot,2);
     if r mod 2=0 then
        if ((qr-calc(i+1,r-i-1,2)) div 2)>0 then inc(tot);

     end;
     5:
     begin
     qr:=calc(r,1,d);
     for i:=0 to (r div 2)-1 do
         if qr-calc(i,r-i,d)>0 then inc(tot,2);
     if r mod 2=0 then
        if (qr-calc(i+1,r-i-1,d)>0) then inc(tot);

     end;
     6:
     begin
     qr:=calc(r,1,3);
     qr2:=calc(r,1,2);
     for i:=0 to (r div 2)-1 do
         if (qr-calc(i,r-i,3)>0) and (qr2-calc(i,r-i,2)>0) then inc(tot,2);
     if r mod 2=0 then
        if (qr-calc(i+1,r-i-1,3)>0) and (qr2-calc(i+1,r-i-1,2)>0) then inc(tot);

     end;
     end;
assign(f,'pascal.out');rewrite(f);
write(f,tot);
close(f);
end.