jmc

Note that $x\equiv y(\mathrm{mod}1000)\iff x\equiv y(\mathrm{mod}125)$ and $x\equiv y(\mathrm{mod}8)$. So we must find the first two integers $i$ and $j$ such that $2^i\equiv 2^j(\mathrm{mod}125)$ and $2^i\equiv 2^j(\mathrm{mod}8)$ and $i\ne j$. Note that $i$ and $j$ will be greater than 2 since remainders of $1,2,4$ will not be possible after 2 (the numbers following will always be congruent to 0 modulo 8). Note that $2^{100}\equiv 1(\mathrm{mod}125)$ (see Euler's theorem) and $2^0,2^1,2^2,\dots ,2^{99}$ are all distinct modulo 125 (proof below). Thus, $i=103$ and $j=3$ are the first two integers such that $2^i\equiv 2^j(\mathrm{mod}1000)$. All that is left is to find $S$ in mod $1000$. After some computation:$$S=2^0+2^1+2^2+2^3+2^4+...+2^{101}+2^{102}=2^{103}-1\equiv 8-1\mathrm{mod}1000=\boxed{7}.$$To show that $2^0,2^1,\dots ,2^{99}$ are distinct modulo 125, suppose for the sake of contradiction that they are not. Then, we must have at least one of $2^{20}\equiv 1(\mathrm{mod}125)$ or $2^{50}\equiv 1(\mathrm{mod}125)$. However, writing $2^{10}\equiv 25-1(\mathrm{mod}125)$, we can easily verify that $2^{20}\equiv -49(\mathrm{mod}125)$ and $2^{50}\equiv -1(\mathrm{mod}125)$, giving us the needed contradiction.