Розділення на одиничні дроби#7025

Розділення на одиничні дроби

1 секунда

64 мегабайти

Легка

Одиничною дроб'ю називається дріб, у якого чисельник дорівнює $1$ , а знаменник є додатним цілим числом. Подання додатного раціонального числа $p / q$ у вигляді суми одиничних дробів іноді називають поданням дробу $p / q$ у вигляді суми одиничних дробів. Наприклад, $1/2 + 1/6$ 1/2 + 1/6 є поданням у вигляді суми одиничних дробів числа $2/3$ . При цьому порядок доданків не враховується. Наприклад, немає жодної різниці між поданнями $1/6 + 1/2$ 1/6 + 1/2 і $1/2 + 1/6$ 1/2 + 1/6.

Для заданих чотирьох додатних цілих чисел $p$ , $q$ , $a$ і $n$ , порахуйте кількість подань дробу $p / q$ у вигляді суми одиничних дробів, які задовольняють наступним двом умовам:

Сума не повинна бути подана більше ніж $n$ одиничними дробами.
Добуток знаменників не повинен перевищувати $a$ .

Наприклад, якщо $(p, q, a, n) = (2, 3, 120, 3)$ (p, q, a, n) = (2, 3, 120, 3), то існує всього $4$ подання

які задовольняють вказаним умовам.

Вхідні дані

Містить не більше $200$ тестів. Кожен тест являє собою рядок з чотирьох додатних цілих чисел $p$ , $q$ , $a$ і $n$ , причому $p, q \leq 800$ p, q \le 800, $a \leq 12000$ a \le 12000 і $n \leq 7$ n \le 7. Усі числа розділені пробілами.

Останній рядок містить чотири нулі і не обробляється.

Вихідні дані

Для кожного тесту виведіть в окремому рядку відповідь на задачу. Кожне ціле число повинно відповідати для заданого набору чисел $p$ , $q$ , $a$ , $n$ кількості подань дробу $p / q$ не більше ніж $n$ доданками, добуток знаменників у яких не перевищує $a$ .

Приклади

Приклад 1