시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 541 202 148 35.238%

문제

무한 수열 A는 다음과 같다.

  • A[0] = 1;
  • A[i] = A[i/P] + A[i/Q] (i>=1, i/P또는 i/Q가 정수가 아닐 때는 가우스 기호를 이용한다. (가우스 기호, [3.4] = 3)을 이용한다.

N, P와 Q가 주어질 때, A[N]을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N P Q가 주어진다. N은 10^12보다 작거나 같은 자연수 또는 0이고, P와 Q는 2보다 크거나 같고, 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 A[N]을 출력한다.

예제 입력

7 2 3

예제 출력

7

힌트

출처