### 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[10000000] = A[-5000000] + A[-6666667] = 2.
1)

 12 2 3 1 0
Returns: 8
2)

 0 2 2 0 0
Returns: 1
 A[0] = 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