Нескінченна послідовність

Визначимо нескінченну послідовність $А$ наступним чином (ділення в індексах цілочисельне):

• $A_0=1$,

• $A_i=A_{i/p}+A_{i/q},i\ge 1$

За заданими $n,p,q$ обчисліть значення $A_n$.

Вхідні дані

Три цілих числа $n,p$ та $q(0\le n\le 10^{12},2\le p,q\le 10^9)$.

Вихідні дані

Виведіть значення $A_n$.

Приклади