use Euler's generalization of Fermat's Little Theorem : if and only if , , where is the Euler totient of .
In your case, is a prime number (lucky you), so . And . Therefore, . Good.
Now note that . Plug in the result you found with Euler's generalization, you find that :
still is a big number, so we are going to break it into pieces. You can thus write the following :
You can easily compute , so :
is not too big and can be computed quickly (if not, break it into two pieces), so . While we're at it, . We get :
And we are done ! We can now write :
(that is, )
Can you see how I have repeatedly broken the original, gigantic number, into lots of smaller numbers, using Fermat's Generalized Little Theorem as a starting block and using algebra of indices to finish off the work ?