Unit Fraction Decomposition

Time limit2sMemory limit128 MB

Summary

Count ways to write p/q as a sum of at most n unit fractions (order ignored) whose denominators multiply to at most a.

Level: Medium7 of 10
Topics: Backtracking, Number theory, Recursion, Math
Solved: No attempts yet

Problem

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:

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

Input

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

Output the number of decompositions satisfying the conditions.

Examples9

Example 1
Input
```
2 3 120 3
```
Expected output
```
4
```
Example 2
Input
```
2 3 300 3
```
Expected output
```
7
```
Example 3
Input
```
2 3 299 3
```
Expected output
```
6
```
Example 4
Input
```
2 3 12 3
```
Expected output
```
2
```
Example 5
Input
```
2 3 12000 7
```
Expected output
```
42
```
Example 6
Input
```
54 795 12000 7
```
Expected output
```
1
```
Example 7
Input
```
2 3 300 1
```
Expected output
```
0
```
Example 8
Input
```
2 1 200 5
```
Expected output
```
9
```
Example 9
Input
```
2 4 54 2
```
Expected output
```
3
```