Infinite Sequence - 2

Consider an infinite sequence $A$ defined as follows:

• $A_i=1,i\le 0$,

• $A_i=A_{\lfloor i/p\rfloor -x}+A_{\lfloor i/q\rfloor -y},i\ge 1$

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

Input

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)$.

Output

Print the value of $A_n$.

Examples