e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Data Structures contest

Infinite Sequence

Consider an infinite sequence A defined as follows:

A0 = 1,

Ai = A[i/p] + A[i/q], i1

You will be given n, p and q. Find the n-th element of A (index is 0-based).

Input

Three integers n, p and q (0n1012, 2p, q109).

Output

Print the value of An.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0 2 3
Output example #1
1
Input example #2
10000000 3 3
Output example #2
32768