### Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Let's consider an infinite sequence A defined as follows:

• A0 = 1;
• Ai = A[i/p] + A[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)

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

### Definition

 Class: InfiniteSequence Method: calc Parameters: long, int, int Returns: long Method signature: long calc(long n, int p, int q) (be sure your method is public)

### Notes

-[x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.

### Constraints

-n will be between 0 and 10^12, inclusive.
-p and q will both be between 2 and 10^9, inclusive.

### Examples

0)

 `0` `2` `3`
`Returns: 1`
 A = 1.
1)

 `7` `2` `3`
`Returns: 7`
 A = 1; A = A + A = 2; A = A + A = 2 + 1 = 3; A = A + A = 3 + 2 = 5; A = A + A = 5 + 3 = 8.
2)

 `10000000` `3` `3`
`Returns: 32768`
3)

 `256` `2` `4`
`Returns: 89`
4)

 `1` `1000000` `1000000`
`Returns: 2`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9837

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13504&pm=9837

yuhch123

#### Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming