Compute $1008^{189642}\pmod{2011}$ How to begin computation of $1008^{189642}\pmod{2011}$
I am quite lost trying to figure out how to go about this. 
There are some "facts" I can find, but not sure how these can help me


*

*gcd(2011,1008) = 1. 

*2011 is prime.

*Prime factorisation of $1008$ is $2^4\times3^2\times7$


A pedestrian solution:
By Fermat's little theorem, $1008^{2010}\equiv 1 \bmod 2011$, and since $189642\equiv 702 \bmod 2010$, we get $1008^{189642}\equiv 1008^{702} \bmod 2011$.
A few iterations yield $1008^9\equiv 48 \bmod 2011$, hence $1008^{702} \equiv 48^{78} \bmod 2011 $.
Noting that $48^3 \equiv -13 \bmod 2011$, we get $48^{78}\equiv 13^{26}  \bmod 2011$.
Finally, $13^{26}  = 13^{15}\cdot 13^{11}\equiv 74 \cdot 183 \equiv 1476 \bmod 2011$.
Putting everything together, $1008^{189642}\equiv 1476 \bmod 2011$.
