Аликвотные дроби
В древнем Египте были дроби только с числителем, равным единице, дроби вида 1/n, так называемые аликвотные дроби и еще была дробь 2/3. Дроби с числителем, отличным от единицы записывали как сумму аликвотных дробей например: 2/5 = 1/5 + 1/5, 2/7 = 1/4 + 1/28.
Задана некоторые натуральные P, Q, A и N. Сколько существует способов представить дробь P/Q в виде суммы аликвотных дробей, так, чтобы количество слагаемых не превышало N, а произведение знаменателей A. Перестановки слагаемых считаются одним способом.
Например, ту же выше упомянутую уникальную египетскую дробь 2/3 при условии, что заданные P, Q, A, N равны соответственно 2, 3, 120, 3 можно представить 4-мя следующими способами при помощи аликвотных дробей:
Входные данные
Каждый тест состоит из нескольких тестовых случаев, количество которых не превышает 200. В каждой входной строке через пробел задано четыре числа P, Q, A и N.
0 <= P, Q <= 800, 0 <= A <= 12000, 0 <= N <= 7.
Последних четыре числа в тесте 0, 0, 0, 0 являются признаком окончания тестовых данных.
Выходные данные
Для каждого тестового случая в отдельной строке вывести ответ на поставленную задачу.