modular arithmetic - What is the remainder when $5 000 000^{500 000 000 000}$ is divided by the prime number $10^{6}+3$?

What is the remainder when $5,000, 000^{500 ,000 ,000 ,000}$ is divided by the prime number $10^{6}+3$?

I tried to use Fermat's Little Theorem but the exponent is still pretty high.