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

• \(A_0 = 1\)
• \(A_i = A_{i/p} + A_{i/q}\), \(i \geq 1\)

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

Вхідні дані

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

Вихідні дані

Виведіть значення \(A_n\).

Вхідні дані #1

0 2 3

Відповідь #1

1

Вхідні дані #2

10000000 3 3

Відповідь #2

32768