Розділення на частки
Долею називається дріб, у якого чисельник дорівнює 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.