Задачи
Разделение на доли
Разделение на доли
Долей называется дробь с числителем равным \textbf{1} и знаменателем в виде положительного целого числа. Представление положительного рационального числа \textbf{p}/\textbf{q} в виде суммы единичных дробей иногда называют представлением дроби \textbf{p}/\textbf{q} в виде долей. Например, \textbf{1}/\textbf{2} + \textbf{1}/\textbf{6} есть представление в виде долей дроби \textbf{2}/\textbf{3}. При этом порядок слагаемых не учитывается. Например, нет никакого различия в представлениях \textbf{1}/\textbf{6} + \textbf{1}/\textbf{2} и \textbf{1}/\textbf{2} + \textbf{1}/\textbf{6}.
Для заданных четырех положителных целых чисел \textbf{p}, \textbf{q}, \textbf{a} и \textbf{n}, посчитайте количество представлений дроби \textbf{p}/\textbf{q} в виде суммы долей, которые удовлетворяют следующим двум условиям:
\begin{itemize}
\item Сумма не должна быть представлена более чем \textbf{n} долями.
\item Произведение знаменателей не должно превышать \textbf{a}.
\end{itemize}
Например, если (\textbf{p}, \textbf{q}, \textbf{a}, \textbf{n}) = (\textbf{2}, \textbf{3}, \textbf{120}, \textbf{3}), то существует всего \textbf{4} представления
\includegraphics{https://static.e-olymp.com/content/e7/e7a07d373b4a1dd3381e7550cc5e6510ffc9825a.jpg}
удовлетворяющие указанным условиям.
\InputFile
Содержит не более \textbf{200} тестов. Каждый тест представляет собой строку из четырех положительных целых чисел \textbf{p}, \textbf{q}, \textbf{a }и \textbf{n}, причем \textbf{p}, \textbf{q} ≤ \textbf{800}, \textbf{a} ≤ \textbf{12000} и \textbf{n} ≤ \textbf{7}. Все числа разделены пробелами.
Последняя строка содержит четыре нуля и не обрабатывается.
\OutputFile
Для каждого теста вывести в отдельной строке ответ на задачу. Каждое целое число должно соответствовать для заданного набора чисел \textbf{p}, \textbf{q}, \textbf{a}, \textbf{n }количеству представлений дроби \textbf{p}/\textbf{q }не более чем \textbf{n }слагаемыми, произведение знаменателей в которых не превышает \textbf{a}.
Входные данные #1
2 3 120 3 2 3 300 3 2 3 299 3 2 3 12 3 2 3 12000 7 54 795 12000 7 2 3 300 1 2 1 200 5 2 4 54 2 0 0 0 0
Выходные данные #1
4 7 6 2 42 1 0 9 3