단위 분수 분할

분자가 1이고 분모가 양의 정수인 분수를 단위 분수라고 한다. 양의 유리수 p/q를 유한 개의 단위 분수의 합으로 나타내면 p/q를 단위 분수로 분할했다고 한다.

분할에서는 항의 순서를 구분하지 않는다. 항의 순서만 다른 1/6 + 1/2와 1/2 + 1/6은 같은 분할이다. 같은 분모의 단위 분수를 여러 번 사용할 수 있다.

양의 정수 p, q, a, n이 주어질 때, 다음 조건을 모두 만족하는 p/q의 분할 개수를 구한다.

1. 사용한 단위 분수의 개수는 n개 이하이다.
2. 사용한 단위 분수들의 분모를 모두 곱한 값은 a 이하이다.

첫째 줄에 양의 정수 p, q, a, n이 공백으로 구분되어 주어진다.

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

조건을 만족하는 분할의 개수를 출력한다.