Remainder

What is the remainder when 1009^109 is divided by 101? Thanks for help.

$\begin{array}{|rcll|} \hline && 1009^{109} \pmod {101} \qquad &| \qquad 1009 \pmod {101} = -1 \\ &\equiv & (-1)^{109} \pmod {101} \qquad &| \qquad (-1)^{109}=-1\\ &\equiv & -1 \pmod {101} \\ &\equiv & 100 \pmod {101} \\ \hline \end{array}$

mod(1009^1,101) = 100

mod(1009^2,101) = 1

mod(1009^3,101) = 100

mod(1009^4,101) = 1

mod(1009^5,101) = 100

...

mod(1009^109,101) = 100

.