jmc

Let $\omega$ and $\zeta$ be the two complex third-roots of 1. Then let $S=(1+\omega {)}^{2007}+(1+\zeta {)}^{2007}+(1+1{)}^{2007}={\sum }_{i=0}^{2007}(\genfrac{}{}{0ex}{}{2007}{i})({\omega }^i+{\zeta }^i+1)$. Now, if $i$ is a multiple of 3, ${\omega }^i+{\zeta }^i+1=1+1+1=3$. If $i$ is one more than a multiple of 3, ${\omega }^i+{\zeta }^i+1=\omega +\zeta +1=0$. If $i$ is two more than a multiple of 3, ${\omega }^i+{\zeta }^i+1={\omega }^2+{\zeta }^2+1=\zeta +\omega +1=0$. Thus $S={\sum }_{i=0}^{669}3\left(\genfrac{}{}{0ex}{}{2007}{3i}\right)$, which is exactly three times our desired expression. We also have an alternative method for calculating $S$: we know that $\{\omega ,\zeta \}=\{-\frac{1}{2}+\frac{\sqrt{3}}{2}i,-\frac{1}{2}-\frac{\sqrt{3}}{2}i\}$, so $\{1+\omega ,1+\zeta \}=\{\frac{1}{2}+\frac{\sqrt{3}}{2}i,\frac{1}{2}-\frac{\sqrt{3}}{2}i\}$. Note that these two numbers are both cube roots of -1, so $S=(1+\omega {)}^{2007}+(1+\zeta {)}^{2007}+(1+1{)}^{2007}=(-1{)}^{669}+(-1{)}^{669}+2^{2007}=2^{2007}-2$. Thus, the problem is reduced to calculating $2^{2007}-2(\mathrm{mod}1000)$. $2^{2007}\equiv 0(\mathrm{mod}8)$, so we need to find $2^{2007}(\mathrm{mod}125)$ and then use the Chinese Remainder Theorem. Since $\varphi (125)=100$, by Euler's Totient Theorem $2^{20\cdot 100+7}\equiv 2^7\equiv 3(\mathrm{mod}125)$. Combining, we have $2^{2007}\equiv 128(\mathrm{mod}1000)$, and so $3S\equiv 128-2(\mathrm{mod}1000)\Rightarrow S\equiv \boxed{42}(\mathrm{mod}1000)$.