AIME 2011a Problem 11

Let $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by 1000. Let $S$ be the sum of the elements in $R$. Find the remainder when $S$ is divided by 1000.