Problems
Infinite Sequence - 2
Infinite Sequence - 2
Consider an infinite sequence $A$ defined as follows:
\begin{itemize}
\item $A_i = 1, i \le 0$,
\item $A_i = A_{ \lfloor i/p \rfloor - x} + A_{ \lfloor i/q \rfloor - y}, i \ge 1$
\end{itemize}
You will be given $n, p, q, x$ and $y$. Find the $n$-th element of $A$ (index is $0$-based).
\InputFile
Five integers $n, p, q, x, y~(0 \le n \le 10^{13}, 2 \le p, q \le 10^9, 0 \le x, y \le 10^9)$.
\OutputFile
Print the value of $A_n$.
Input example #1
10000000 2 3 10000000 10000000
Output example #1
2
Input example #2
12 2 3 1 0
Output example #2
8