Unit Fraction Decomposition

A unit fraction is a fraction whose numerator is 1 and whose denominator is a positive integer. If a positive rational number p/q is written as a finite sum of unit fractions, that expression is called a decomposition of p/q into unit fractions.

The order of terms does not matter. The expressions 1/6 + 1/2 and 1/2 + 1/6 count as the same decomposition because they differ only by order. The same denominator may be used more than once.

Given positive integers p, q, a, and n, count the decompositions of p/q satisfying both conditions:

1. The decomposition uses at most n unit fractions.
2. The product of all denominators used in the decomposition is at most a.

The first line contains four positive integers p, q, a, and n, separated by spaces.

• 1 ≤ p, q ≤ 800
• 1 ≤ a ≤ 12000
• 1 ≤ n ≤ 7

Output the number of decompositions satisfying the conditions.