Problem B
Pohlig-Hellman

Implement the Pohlig-Hellman algorithm to solve $g^x\equiv h(\mathrm{mod}p)$ for $x$.

Input

Input is three lines. The first line contains the prime $p$ where $3\le p<2^{63}$ and each prime factor of $p-1$ are less than $2^{40}$. The second line contains the integer $g$ where $2\le g<p$ of order at least 2. The third line contains the integer $h$ where $0\le h<p$.

Output

Output one line with any valid solution $0\le x<p-1$ or no solution if no solution exists.

3
2
1

0

449
6
99

182

7
4
3

no solution