RSA is one of the most used cryptographic algorithms and it is considered to be one of the most secure existing alternatives. Its basic operation is described below.

Two odd prime numbers P and Q are chosen and N = PQ is computed. Then the totient function φ(N) = (P − 1)(Q − 1) is computed and an integer e satisfying 1 < E < φ(N) is chosen so that gcd(φ(N), E) = 1. Finally the integer D, the inverse multiplicative of e module φ(N) is computed, that is, the integer D satisfying DE ≡ 1 mod φ(N).

In that way we obtain the public key, which consists of the pair of integers N and E, and the secret key, containing the integers N and D.

To encrypt a message M, with 0 < M < N, we calculate C = M^{e} mod N, and C is the encrypted message. To decrypt the message, that is, to recover the original message, it suffices to compute M = C^{d} mod N. Note that, in order to do that, the secret key must be known; knowing the public key is not enough to decrypt the message.

In this problem your task is to break the RSA cryptography.

## Input

The input contains several test cases. **A** test case consists of one line, which contains three integers **N**, **E**, and **C**, where 15 ≤ **N** ≤ 10^{9} , 1 ≤ **E** < **N** and 1 ≤ **C** < **N** , such that **N** and **E** constitute the RSA public key described above, and **C** is a message encrypted with that public key.

## Output

For each test case in the input your program must produce a single line, containing a single integer **M** , **1** ≤**M** < **N** , the original message.

Sample Input | Sample Output |

1073 71 436 | 726 |

my solution:

<br />#include<bits/stdc++.h> using namespace std; typedef long long num; const int MP = 100004; num n, m, e, d, c, phi, aux; int primes[MP], ps; char comp[MP]; num mod( num x, num y ) { return (x%y + y)%y; } num tot( num n ) { num ans = n, aux = n; for(int i=0;i<ps;i++) if( aux%primes[i] == 0 ) { while( aux%primes[i] == 0 ) aux /= primes[i]; ans = ans/primes[i]*(primes[i]-1); } return ans; } num euclid(num a, num & x, num b, num & y) { num d, ix, iy; if( a%b == 0 ) { x = 0ll; y = 1ll; return b; } d = euclid(b,ix,a%b,iy); x = iy; y = ix - (a/b)*iy; return d; } num fexp( num a, int e ) { num t = 1; while(e) { if(e%2) t = mod(t*a, n); a = mod(a*a,n); e /= 2; } return t; } int main() { comp[0] = comp[1] = 1; for(int i=2;i<MP;i++) if( !comp[i] ) { primes[ps++] = i; for(int j=2*i;j<MP;j+=i) comp[j] = 1; } scanf("%lld %lld %lld", &n, &e, &c); phi = tot(n); euclid(e,d,phi,aux); d = (d%phi + phi)%phi; printf("%lld\n", mod(fexp(c,d),n) ); }