Problems
Infinite Sequence
Infinite Sequence
Consider an infinite sequence $A$ defined as follows:
\begin{itemize}
\item $A_0 = 1$,
\item $A_i = A_{i/p} + A_{i/q}, i \ge 1$
\end{itemize}
You are given $n, p$ and $q$. Find the value of $A_n$.
\InputFile
Three integers $n, p$ and $q~(0 \le n \le 10^{12}, 2 \le p, q \le 10^9)$.
\OutputFile
Print the value of $A_n$.
Input example #1
0 2 3
Output example #1
1
Input example #2
10000000 3 3
Output example #2
32768