A. SQRT Problem
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Miss Burger has three positive integers $$$n$$$, $$$a$$$, and $$$b$$$. She wants to find a positive integer solution $$$x$$$ $$$(1\leq x\leq n-1)$$$ that satisfies the following two conditions:

  • $$$x^2\equiv a\pmod n$$$
  • $$$\lfloor \sqrt[3]{x^2}\rfloor=b$$$
Additionally, it is guaranteed that $$$n$$$ is an odd number and $$$\gcd(a,n)=1$$$. Here $$$\gcd(x,y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$. We also guarantee that there exists a unique solution.

Note that $$$ \left \lfloor x\right \rfloor $$$ represents the largest integer not exceeding $$$x$$$, such as $$$ \left \lfloor 0.5\right \rfloor =0$$$, $$$ \left \lfloor 11.3\right \rfloor =11$$$, $$$ \left \lfloor 101.9\right \rfloor =101$$$, $$$ \left \lfloor 99\right \rfloor =99$$$, $$$ \left \lfloor 0\right \rfloor =0$$$, $$$ \left \lfloor 2\right \rfloor =2$$$.

Input

The first line contains a single integer $$$n$$$ ($$$3 \le n \le {10}^{100}-1$$$).

The second line contains a single integer $$$a$$$ ($$$1 \le a \le n-1$$$).

The third line contains a single integer $$$b$$$ ($$$1 \le b \le n-1$$$).

Output

Output a single integer denoting the solution $$$x$$$.

Examples
Input
9
4
3
Output
7
Input
650849
253233
5059
Output
359895
Input
29268658540371639122046169677605538931
22216978925831646928504047924228222624
9226521123963832612770162
Output
28025732380501848167087889769592298758