Infinite Sequence 2

Time limit10sMemory limit512 MB

Summary

Compute A_N for a recursively defined sequence using nested floor divisions, requiring memoized recursion over a bounded set of distinct arguments.

Level: Medium6 of 10
Topics: Recursion, Math, Hash map, Dynamic programming
Solved: No attempts yet

Problem

Sequence A is defined for every integer i as follows.

If i ≤ 0, then A_i = 1.
If i ≥ 1, then A_i = A_{⌊i / P⌋ - X} + A_{⌊i / Q⌋ - Y}.

Given integers N, P, Q, X, and Y, compute A_N.

Input

The first line contains five integers N, P, Q, X, and Y.

Output

Print the value of A_N on one line.

Constraints

0 ≤ N ≤ 10^13
2 ≤ P, Q ≤ 10^9
0 ≤ X, Y ≤ 10^9

Hint

⌊x⌋ denotes the greatest integer less than or equal to x.

Examples4

Example 1
Input
```
10000000 2 3 10000000 10000000
```
Expected output
```
2
```
Example 2
Input
```
12 2 3 1 0
```
Expected output
```
8
```
Example 3
Input
```
0 2 2 0 0
```
Expected output
```
1
```
Example 4
Input
```
123 45 67 8 9
```
Expected output
```
2
```

Loading...