Auto comment: topic has been updated by VIIIIIIVX (previous revision, new revision, compare).

Use a^phi(n) is 1 mod n. Find a^a mod n, and a^a mod phi(n).

Incase a, n are co-prime, I guess this will work.

You can use Euler's Theorem for x^y % n even when gcd(x, n) ≠ 1. This requires that the residue used in the exponentiation is equal or bigger than the highest power of the prime powers shared by x and n. So in such case, find y % φ(n) until the value is the smallest value greater or equal to the highest power of the prime factors shared by x and n.

Having said this, in above case the highest shared power is  ≤ 10. So calculations then can fit in long long.

A simple way is to compute the values 1, a, a², a³, ... modulo n until you find a loop. Due to non-coprimeness issues, it may not end in 1, so it has the so-called ρ structure (a tail and a cycle). Still, we know the start of the cycle and its period, so we can reduce the exponent modulo this period.

So now we have to compute the exponent . This can be done straightforwardly or using fast exponentiation.