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