Compute 2^1000(mod 121) using Euler.

121 = 11^2

Phi(121) = 11*10 = 110

1000 Mod 110 = 1000 - 990 = 10

2^1000 Mod 121 = 2^10 Mod 121

In the following everything is Mod 121:

2^7 = 128 = 7

2^10 = 7 * 2^3 = 56