Solution:

The remainders $2^0 = 1,$ $2^1 = 2,$ and $2^2 = 4$ occur, and for $n \ge 3$ every $2^n$ is divisible by $8.$ Modulo $125$ the powers of $2$ for $n \ge 3$ repeat with period $100,$ so $R$ consists of $1,$ $2,$ $4,$ and the $100$ distinct remainders of $2^3, 2^4, \ldots, 2^{102}.$

The key fact is $2^{50} \equiv -1 \pmod{125}:$ indeed $2^{50} + 1 = (2^{10} + 1)(2^{40} - 2^{30} + 2^{20} - 2^{10} + 1),$ where $2^{10} + 1 = 1025$ is divisible by $25$ and the second factor is $\equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5$ because $2^{10} \equiv -1 \pmod 5.$ Hence for $n \ge 3,$ the sum $2^{n+50} + 2^n$ is divisible by $125$ and by $8,$ so by $1000.$

Pairing each remainder in the cycle with the one $50$ steps later therefore gives $50$ pairs of distinct remainders, each pair summing to exactly $1000,$ so those $100$ remainders contribute a multiple of $1000$ to $S.$ Thus $S \equiv 1 + 2 + 4 = 7 \pmod{1000}.$