All Close To Perfect Squares

Each term of the series can be expressed as $(n+1)(n-1) = 3m$ , implying either $(n+1)$ or $(n-1)$ is a multiple of three. The even terms of the sequence have $(n-1)=3r$ for $a_{2r}$ and the odd terms have $(n+1)=3r$ for $a_{2r-1}$ . Therefore the $2016^\text{th}$ term would have $(n-1)=3 \times 1008$ $a_{2016} \equiv (3\times 1008)\times(3 \times 1008 + 2) \equiv 624 \pmod{1000}$

The terms of the sequence alternate between $(3n-1)^2-1=9n^2-6n$ and $(3n+1)^2-1$ $=9n^2+6n$ so that the 2016th term is $9\times 1008^2+6\times 1008\equiv 9\times 64+48 = \boxed{624} \pmod{1000}$