Infinite Sequence#1211

Infinite Sequence

1 second

128 megabytes

Very easy

Define the infinite sequence $A$ as follows:

$A_{0} = 1$ A_0 = 1,
$A_{i} = A_{i / p} + A_{i / q}, i \geq 1$ A_i = A_{i/p} + A_{i/q}, \quad i \ge 1

Input

Three integers $n$ , $p$ and $q$ $(0 \leq n \leq 1 0^{12}, 2 \leq p, q \leq 1 0^{9})$ (0 \le n \le 10^{12},\ 2 \le p, q \le 10^9).

Print the value of $A_{n}$ A_n.

Example 1

Loading

Example 2

Loading

A_{0} = 1

A_{i} = A_{i / p} + A_{i / q}, i \geq 1

(0 \leq n \leq 1 0^{12}, 2 \leq p, q \leq 1 0^{9})

A_{n}