무한 수열

무한 수열 A는 다음과 같이 정의된다.

• A_0 = 1
• i ≥ 1일 때, A_i = A_⌊i / P⌋ + A_⌊i / Q⌋

정수 N, P, Q가 주어질 때 A_N을 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 N, P, Q가 공백으로 구분되어 주어진다.

A_N의 값을 출력한다.

• 0 ≤ N ≤ 10^12
• 2 ≤ P, Q ≤ 10^9

⌊x⌋는 x보다 크지 않은 가장 큰 정수이다.