Разделение на доли
Долей называется дробь с числителем равным 1 и знаменателем в виде положительного целого числа. Представление положительного рационального числа p/q в виде суммы единичных дробей иногда называют представлением дроби p/q в виде долей. Например, 1/2 + 1/6 есть представление в виде долей дроби 2/3. При этом порядок слагаемых не учитывается. Например, нет никакого различия в представлениях 1/6 + 1/2 и 1/2 + 1/6.
Для заданных четырех положителных целых чисел p, q, a и n, посчитайте количество представлений дроби p/q в виде суммы долей, которые удовлетворяют следующим двум условиям:
Сумма не должна быть представлена более чем n долями.
Произведение знаменателей не должно превышать a.
Например, если (p, q, a, n) = (2, 3, 120, 3), то существует всего 4 представления
удовлетворяющие указанным условиям.
Входные данные
Содержит не более 200 тестов. Каждый тест представляет собой строку из четырех положительных целых чисел p, q, a и n, причем p, q ≤ 800, a ≤ 12000 и n ≤ 7. Все числа разделены пробелами.
Последняя строка содержит четыре нуля и не обрабатывается.
Выходные данные
Для каждого теста вывести в отдельной строке ответ на задачу. Каждое целое число должно соответствовать для заданного набора чисел p, q, a, n количеству представлений дроби p/q не более чем n слагаемыми, произведение знаменателей в которых не превышает a.