В древньому Єгипті були дроби тільки з чисельником, рівним одиниці, дроби виду \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 Для кожного тестового випадку в окремому рядку вивести відповідь на поставлену задачу.