Нескінченну послідовність A визначено наступним чином:
A_0 = 1,
A_i = A_{i/p} + A_{i/q}, \quad i \ge 1
Три цілих числа n, p, q (0 \le n \le 10^{12},\ 2 \le p, q \le 10^9).
Виведіть значення A_n.
Приклад 1
Приклад 2
