RSA

Time Limit: 3000MS

Memory Limit: 65536K

Description

RSA is the best-known public key encryption algorithm. In this algorithm each participant has a private key that is shared with no one else and a public key which is published so everyone knows it. To send a secure message to this participant, you encrypt the message using the widely known public key; the participant then decrypts the messages using his or her private key. Here is the procedure of RSA: First, choose two different large prime numbers P and Q, and multiply them to get N (= P * Q). Second, select a positive integer E (0 < E < N) as the encryption key such that E and T= (P - 1) * (Q - 1) are relatively prime. Third, compute the decryption key D such that 0 <= D < T and (E * D) mod T = 1. Here D is a multiplicative inverse of E, modulo T. Now the public key is constructed by the pair {E, N}, and the private key is {D, N}. P and Q can be discarded. Encryption is defined by C = (M ^ E) mod N, and decryption is defined by M = (C ^ D) mod N, here M, which is a non-negative integer and smaller than N, is the plaintext message and C is the resulting ciphertext. To illustrate this idea, let’s see the following example: We choose P = 37, Q = 23, So N = P * Q = 851, and T = 792. If we choose E = 5, D will be 317 ((5 * 317) mod 792 = 1). So the public key is {5, 851}, and the private key is {317, 851}. For a given plaintext M = 7, we can get the ciphertext C = (7 ^ 5) mod 851 = 638. As we have known,for properly choosen very large P and Q, it will take thousands of years to break a key, but for small ones, it is another matter. Now you are given the ciphertext C and public key {E, N}, can you find the plaintext M?

Input

The input will contain several test cases. Each test case contains three positive integers C, E, N (0 < C < N, 0 < E < N, 0 < N < 2 ^ 62).

Output

Output the plaintext M in a single line.

Sample Input

638 5 851

Sample Output

7

Hint

Source

N/A

提交代码