O. Discrete Logarithm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given positive integers $$$a$$$, $$$c$$$, $$$p$$$, ensure that $$$p$$$ is prime, find $$$b$$$ such that:

$$$$$$a^b \equiv b^c \pmod{p}$$$$$$

We say that integers $$$A, B, C$$$ have $$$A \equiv B \pmod{C}$$$ if and only if there exists an integer $$$k$$$ such that $$$A - B = C \times k$$$.

Input

Input is just one line of three integers $$$a$$$, $$$c$$$, and $$$p$$$ ($$$1 \leq a, c \lt p \leq 10^9$$$), separated by a space, with the meaning as described in the question.

The data guarantees that $$$p$$$ is a prime.

Output

Output only one integer $$$b$$$ ($$$1 \leq b \leq 10^{18}$$$). If there are multiple legal answers, you can output any one.

It can be proved that there is at least one solution in the range.

Examples
Input
3 5 7
Output
16
Input
14530529 19260817 19491001
Output
5660025
Note

For the first sample, we have:

$$$$$$3^{16} \equiv 16^5 \pmod{7}$$$$$$

Because:

$$$$$$3^{16} \bmod 7 = 43046721 \bmod 7 = 4$$$$$$

$$$$$$16^5 \bmod 7 = 1048576 \bmod 7 = 4$$$$$$