시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 8 3 100.000%

문제

분수 중에서 분자가 1이고 분모가 양수인 것을 단위분수라고 한다. 분수 p/q를 유한개의 단위분수의 합으로 나타내었을 때 p/q를 단위분수로 분할했다고 말한다. 예를 들면 2/3는 1/2+1/6으로 분할 할 수 있다. 분할에서 더하기의 순서만 바뀐 것은 고려하지 않는다. 예를 들면 1/6+1/2와 1/2+1/6은 같은 분할로 본다.

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

  1. n개 이하의 단위분수의 합으로 나타내야 한다.
  2. 분할을 이루는 단위분수의 분모의 크기의 곱은 a보다 작거나 같아야 한다.

예를 들어 만약 (p, q, a, n)이 (2, 3, 120, 3)일 때 답은 4가 되어야 한다.

2/3 = 1/3+1/3 = 1/2+1/6 = 1/4+1/4+1/6 = 1/3+1/6+1/6

입력

첫째 줄에 양의 정수 p, q, a, n이 입력된다. (p, q <= 800, a <= 12000, n <= 7)

출력

첫째 줄에 문제의 조건을 만족하는 분할의 개수를 출력한다.

예제 입력

2 3 120 3

예제 출력

4

힌트