{$N+}
Program AB;
 Var x,y,n:Extended;
     a:Array[0..32] Of Extended;
     mx,i,k,b:Longint;
 Function Fac(a:Longint):Extended;
  Var i:Longint;
      r:Extended;
 Begin
  r:=1;
  For i:=1 To a Do
   r:=r*i;
  Fac:=r;
 End;
 Function C(n,k:Longint):Extended;
  Var a:Extended;
 Begin
  If k>n Then
   C:=0
  Else
   C:=Trunc(Trunc(Fac(n) / (Fac(k))/Fac(n-k)));
 End;
 Function f(x:Extended; k,mx:Longint):Extended;
  Var i:Longint;
      s:Extended;
 Begin
{  Writeln('x=',x:0:0,' k=',k); Readln;}
  If x=0 Then Begin
   If k=0 Then
    f:=1
   Else
    f:=0;
   Exit;
  End;
  s:=0;
  If k=1 Then Begin
   i:=-1;
   For i:=0 To mx-1 Do
    If a[i+1]>x Then
     Break;
   f:=i+1;
   Exit;
  End;
  For i:=0 To mx-1 Do
   If a[i+1]<=x Then Begin
    s:=s+C(i,k-1);
   End Else Begin
    s:=s+f(x-a[i],k-1,i);
    Break;
   End;
  f:=s;
 End;
Begin
{ Assign(input,'1057.in'); Reset(input);}
 Read(x,y,k,b);
 a[0]:=1;
 mx:=32;
 For i:=1 To 32 Do Begin
  a[i]:=a[i-1]*b;
  If a[i]>1E11 Then Begin
   mx:=i;
   Break;
  End;
 End;
 Writeln(f(y,k,mx)-f(x-1,k,mx):0:0);
End.