elementary number theory - simple congruence with large power and large moduli

I am trying to compute $2^{111455} \pmod{2012}$, but since the numbers are too large, I don't know how to compute it efficiently. I've got: $2012=2^2 \times 503$, $503$ is a prime. And that $111455=2012 \times 55 + 795$ but I don't know if it is useful.