Problem 1267

1. Identify the problem and decompose the modulus:
We need to find the remainder when the sum of all possible remainders of $2^n \mod 1000$ (where $n$ is a nonnegative integer) is divided by 1000. We start by decomposing 1000 into its prime factors:
$$1000 = 2^3 \cdot 5^3$$
We will compute the sum modulo $2^3 = 8$ and $5^3 = 125$ separately and then combine the results using the Chinese Remainder Theorem.

2. Compute the sum modulo 8:
The powers of 2 modulo 8 cycle every 3 terms:
$$2^0 \equiv 1 \pmod{8}, \quad 2^1 \equiv 2 \pmod{8}, \quad 2^2 \equiv 4 \pmod{8}, \quad 2^3 \equiv 0 \pmod{8}, \quad \text{and so on.}$$
Therefore, the sum of all possible remainders modulo 8 is:
$$S_8 = 1 + 2 + 4 + 0 + 0 + 0 + \cdots = 1 + 2 + 4 = 7$$
Hence,
$$S \equiv 7 \pmod{8}$$

3. Compute the sum modulo 125:
We need to find the order of 2 modulo 125, denoted as $\text{ord}_{125}(2)$. This is the smallest positive integer $d$ such that:
$$2^d \equiv 1 \pmod{125}$$
By Euler's theorem, since $\phi(125) = 100$, we know:
$$2^{100} \equiv 1 \pmod{125}$$
We need to check if there is a smaller $d$ that satisfies this condition. We test the divisors of 100:
$$2^4 \equiv 16 \pmod{125} \quad (\text{not } 1)$$
$$2^{20} = (2^{10})^2 = 1024^2 \equiv 24^2 = 576 \pmod{125} \quad (\text{not } 1)$$
Therefore, the order is indeed 100. The sequence of remainders modulo 125 will repeat every 100 terms. The sum of the first 100 terms is:
$$2^0 + 2^1 + 2^2 + \cdots + 2^{99}$$
This is a geometric series with the sum:
$$S_{125} = \frac{2^{100} - 1}{2 - 1} = 2^{100} - 1$$
Since $2^{100} \equiv 1 \pmod{125}$, we have:
$$2^{100} - 1 \equiv 0 \pmod{125}$$
Therefore,
$$S \equiv 0 \pmod{125}$$

4. Combine results using the Chinese Remainder Theorem:
We have:
$$S \equiv 7 \pmod{8}$$
$$S \equiv 0 \pmod{125}$$
We need to find $S$ such that:
$$S \equiv 7 \pmod{8}$$
$$S \equiv 0 \pmod{125}$$
Let $S = 125k$. Then:
$$125k \equiv 7 \pmod{8}$$
Since $125 \equiv 5 \pmod{8}$, we have:
$$5k \equiv 7 \pmod{8}$$
Multiplying both sides by the modular inverse of 5 modulo 8, which is 5 (since $5 \cdot 5 \equiv 1 \pmod{8}$), we get:
$$k \equiv 7 \cdot 5 \equiv 35 \equiv 3 \pmod{8}$$
Therefore,
$$k = 8m + 3 \quad \text{for some integer } m$$
Substituting back, we get:
$$S = 125k = 125(8m + 3) = 1000m + 375$$
Hence,
$$S \equiv 375 \pmod{1000}$$

The final answer is $\boxed{375}$