Визначимо нескінченну послідовність $А$ наступним чином (ділення в індексах цілочисельне): \begin{itemize} \item $A_0 = 1$, \item $A_i = A_{i/p} + A_{i/q}, i \ge 1$ \end{itemize} За заданими $n, p, q$ обчисліть значення $A_n$. \InputFile Три цілих числа $n, p$ та $q~(0 \le n \le 10^{12}, 2 \le p, q \le 10^9)$. \OutputFile Виведіть значення $A_n$.