{
TASK: digits
LANG: PASCAL
}
var i, br, n, m, k, l, c, o : longint;

Begin
  readln(c, m, k);
  readln(n);
  br:=0;
  for i:=1 to n do begin
    l:=i;
    repeat
      o:=l mod k;
      if o=m then inc(br);
      l:=l div k;
    until l=0;
  end;
  writeln(br);
end.


