Infinite Sequence 2

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.

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

Print the value of A_N on one line.

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

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