eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

Пример

Входные данные #1
0 2 3
Выходные данные #1
1
Входные данные #2
10000000 3 3
Выходные данные #2
32768