There Must Be Odd

There are $2^{100}-1$ nonempty subsets of $\{1, 2, 3,\ldots, 100\}$ . Since there are $50$ even numbers from $1$ to $100$ , there are $2^{50}-1$ nonempty subsets of $\{1, 2, 3,\ldots, 100\}$ which don't have an odd element. Thus, there are $T=2^{100}-1-(2^{50}-1)=2^{100}-2^{50}$ subsets having at least one odd element. By Euler's Totient Theorem, we have $2^{100}\equiv 1\pmod{125}$ since $\varphi(125)=100$ . Furthermore, we have $2^7\equiv 3\pmod{125}\implies 2^{42}\equiv 729\equiv 104\pmod{125}$ and $2^8\equiv 6\pmod{125}$ , so $2^{50}\equiv 104(6)\equiv -1\pmod{125}$ , so $2^{100}-2^{50}\equiv 2\pmod{125}$ . Since $8\mid 2^{100}-2^{50}$ , by Chinese Remainder Theorem we get $2^{100}-2^{50}\equiv 752\pmod{1000}$ , so the answer is $\boxed{752}$ .