Aliquot Fractions
In ancient Egypt, fractions were typically expressed with numerators of one, known as unit fractions, in the form 1/n. Additionally, the fraction 2/3 was also used. Fractions with numerators greater than one were represented as a sum of unit fractions. For example, 2/5 could be written as 1/5 + 1/5, and 2/7 as 1/4 + 1/28.
Given natural numbers P, Q, A, and N, determine how many ways the fraction P/Q can be expressed as a sum of unit fractions such that the number of terms does not exceed N, and the product of the denominators equals A. Different permutations of the same terms are considered as one unique way.
For instance, the Egyptian fraction 2/3, with P, Q, A, and N being 2, 3, 120, and 3 respectively, can be represented in 4 distinct ways using unit fractions:
Input
Each test consists of several test cases, with a maximum of 200 cases. Each input line contains four numbers P, Q, A, and N, separated by spaces.
0 <= P, Q <= 800, 0 <= A <= 12000, 0 <= N <= 7.
The sequence 0, 0, 0, 0 marks the end of the test data.
Output
For each test case, print the solution to the problem on a separate line.