A tree has grown in Uolevi's yard while he was away doing all sorts of other stuff. Since the neighbourhood association is complaining to Uolevi about the tree being ugly, he has to remove it. Of course, to remove it, he first needs to unroot it.

After doing some research online, Uolevi knows that this tree species particularly hates the number b. He also inspected the tree in his yard, and found out it has r roots, and weights p kilos. Both r and p just so happen to be prime. Now, to extract the root of the tree, Uolevi has to find some integer a such that a^{r} = b\text{ }(\text{mod } p)

However, finding such a number is too hard for Uolevi, (it might even be impossible!). As such, Uolevi wants you to find him the number a, or to tell him that such a number doesn't exist, so that he can go buy a excavator.

Input

The only line of input contains three integers r b p: The number of roots the tree has, the integer the tree hates, and the tree's weight.

Output

If a integer a exists such that a^{r} = b\text{ }(\text{mod } p), output any such integer. However, note that it must hold that 0 \leq a < p.

If no such integer exists, output -1

Constraints

• 0 \leq b < p \leq 10^{18}
• 1 \leq r \leq 10^{18}
• r and p are primes

Example

Input:

2 4 5

Output:

3