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

# 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