Infinite Sequence

Consider an infinite sequence $A$ defined as follows:

• $A_0=1$,

• $A_i=A_{i/p}+A_{i/q},i\ge 1$

You are given $n,p$ and $q$. Find the value of $A_n$.

Input

Three integers $n,p$ and $q(0\le n\le 10^{12},2\le p,q\le 10^9)$.

Output

Print the value of $A_n$.

Examples