Бесконечная последовательность

Определим бесконечную последовательность $А$ следующим образом:

• $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$.

Примеры