RSA

RSA is one of the most widely used public key encryption algorithms. Its basic operation is described below.

Pick two distinct odd primes $P$ and $Q$ and compute $N = PQ$. Next compute the totient $\varphi(N) = (P - 1)(Q - 1)$ and pick an integer $E$ with $1 < E < \varphi(N)$ and $\gcd(\varphi(N), E) = 1$. Finally compute $D$, the multiplicative inverse of $E$ modulo $\varphi(N)$, that is the integer $D$ with $DE \equiv 1 \pmod{\varphi(N)}$.

This gives the public key, formed by the two integers $N$ and $E$, and the secret key, formed by the two integers $N$ and $D$.

To encrypt a message $M$ with $0 < M < N$, compute $C = M^E \bmod N$, and $C$ is the encrypted message. To decrypt it and recover the original message, compute $M = C^D \bmod N$. Decryption needs the secret key, and the public key alone is not enough. The expression $x \equiv 1 \pmod{y}$ used above means that the remainder of $x$ divided by $y$ is 1.

In this problem you break RSA. Write a program that recovers the original message $M$ from the public key $N$, $E$ and the ciphertext $C$ alone.

The single line of input contains three integers $N$, $E$, $C$ separated by spaces, where $15 \le N \le 10^9$, $1 \le E < N$ and $1 \le C < N$.

$N$ and $E$ form the RSA public key described above, and $C$ is a message encrypted with that public key. $N$ is a product of two distinct odd primes, and $\gcd(\varphi(N), E) = 1$ always holds.

Print a single line containing the original message $M$, where $1 \le M < N$.