jmc

Consider the polynomial$$f(x)=(x-1{)}^{2004}=\sum _{n=0}^{2004}(\genfrac{}{}{0ex}{}{2004}{n})\cdot (-1{)}^n{x}^{2004-n}.$$ Let ${\omega }^3=1$ with $\omega \ne 1$. We have $$\begin{array}{rl}\frac{f(1)+f(\omega )+f({\omega }^2)}{3}& =\frac{(1-1{)}^{2004}+(\omega -1{)}^{2004}+({\omega }^2-1{)}^{2004}}{3}\\ & =\frac{1}{3}\sum _{n=0}^{2004}\left(\genfrac{}{}{0ex}{}{2004}{n}\right)\cdot (-1{)}^n\cdot (1^{2004-n}+{\omega }^{2004-n}+({\omega }^2{)}^{2004-n})\\ & =\sum _{n=0}^{668}(-1{)}^n(\genfrac{}{}{0ex}{}{2004}{3n}).\end{array}$$ where the last step follows because $1^k+{\omega }^k+{\omega }^{2k}$ is 0 when $k$ is not divisible by 3, and $3$ when $k$ is divisible by 3. We now compute $\frac{(1-1{)}^{2004}+(\omega -1{)}^{2004}+({\omega }^2-1{)}^{2004}}{3}$. WLOG, let $\omega =\frac{-1+\sqrt{3}i}{2},{\omega }^2=\frac{-1-\sqrt{3}i}{2}$. Then $\omega -1=\frac{-3+\sqrt{3}i}{2}=\sqrt{3}\cdot \frac{-\sqrt{3}+i}{2}$, and ${\omega }^2-1=\sqrt{3}\cdot \frac{-\sqrt{3}-i}{2}$. These numbers are both of the form $\sqrt{3}\cdot \phi$, where $\phi$ is a 12th root of unity, so both of these, when raised to the 2004-th power, become $3^{1002}$. Thus, our desired sum becomes $2\cdot 3^{1001}$. To find $2\cdot 3^{1001}(\mathrm{mod}1000)$, we notice that $3^{\varphi 500}\equiv 3^{200}\equiv 1(\mathrm{mod}500)$ so that $3^{1001}\equiv 3(\mathrm{mod}500)$. Then $2\cdot 3^{1001}=2(500k+3)=1000k+6$. Thus, our answer is $\boxed{6}$.