[tex]x^2+x+1=\dfrac{x^3-1}{x-1}[/tex]
so we know [tex]x^2+x+1[/tex] has roots equal to the cube roots of 1, not including [tex]x=1[/tex] itself, which are
[tex]\omega=e^{2i\pi/3}\text{ and }\omega^2=e^{4i\pi/3}[/tex]
Any polynomial of the form [tex]p_n(x)=x^{2n}+1+(x+1)^{2n}[/tex] is divisible by [tex]x^2+x+1[/tex] if both [tex]p(\omega)=0[/tex] and [tex]p(\omega^2)=0[/tex] (this is the polynomial remainder theorem).
This means
[tex]p(\omega)=\omega^{2n}+1+(1+\omega)^{2n}=0[/tex]
But since [tex]\omega[/tex] is a root to [tex]x^2+x+1[/tex], it follows that
[tex]\omega^2+\omega+1=0\implies1+\omega=-\omega^2[/tex]
[tex]\implies\omega^{2n}+1+(-\omega^2)^{2n}=0[/tex]
[tex]\implies\omega^{4n}+\omega^{2n}+1=0[/tex]
and since [tex]\omega^3=1[/tex], we have [tex]\omega^{4n}=\omega^{3n}\omega^n=\omega^n[/tex] so that
[tex]\implies\omega^{2n}+\omega^n+1=0[/tex]
From here, notice that if [tex]n=3k[/tex] for some integer [tex]k[/tex], then
[tex]\omega^{2(3k)}+\omega^{3k}+1=1+1+1=3\neq0[/tex]
[tex]\omega^{4(3k)}+\omega^{2(3k)}+1=1+1+1=3\neq0[/tex]
which is to say, [tex]p(x)[/tex] is divisible by [tex]x^2+x+1[/tex] for all [tex]n[/tex] in the given range that are *not* multiples of 3, i.e. the integers [tex]3k-2[/tex] and [tex]3k-1[/tex] for [tex]k\ge1[/tex].
Since 2005 = 668*3 + 1, it follows that there are [tex]m=668 + 669 = 1337[/tex] integers [tex]n[/tex] such that [tex]x^2+x+1\mid p(x)[/tex].
Finally, [tex]m\equiv\boxed{337}\pmod{1000}[/tex].
