### 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:

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

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

### Definition

 Class: InfiniteSequence2 Method: calc Parameters: long, int, int, int, int Returns: long Method signature: long calc(long n, int p, int q, int x, int y) (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^13, inclusive.
-p and q will both be between 2 and 10^9, inclusive.
-x and y will both be between 0 and 10^9, inclusive.

### Examples

0)

 `10000000` `2` `3` `10000000` `10000000`
`Returns: 2`
 A = A[-5000000] + A[-6666667] = 2.
1)

 `12` `2` `3` `1` `0`
`Returns: 8`
2)

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

 `123` `45` `67` `8` `9`
`Returns: 2`

#### Problem url:

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

#### Problem stats url:

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

yuhch123

#### Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming