### subroutines

def count_rec(pi, qi, ai, ni, q0 = 1, dens = [])
  if pi == 0
    #p [pi, qi, ai, ni, q0, dens, 1]
    return 1
  end

  if ni <= 0
    #p [pi, qi, ai, ni, q0, dens, 0]
    return 0
  end

  c = 0
  q = q0

  while q <= ai
    p1 = pi * q - qi
    if p1 >= 0
      q1 = qi * q
      g = p1.gcd(q1)
      if g > 1
        p1 /= g
        q1 /= g
      end

      c += count_rec(p1, q1, ai / q, ni - 1, q, dens + [q])
    end

    q += 1
  end

  #p [pi, qi, ai, ni, q0, dens, c]
  c
end

### main

loop do
  pi, qi, ai, ni = gets.split.map(&:to_i)
  break if (pi | qi | ai | ni) == 0

  c = count_rec(pi, qi, ai, ni)
  puts c
end