1351번 - 무한 수열

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

• A₀ = 1
• A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)

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

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

첫째 줄에 A_N을 출력한다.

• 0 ≤ N ≤ 10¹²
• 2 ≤ P, Q ≤ 10⁹

⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.