Answer: 907

Solution:

A person sits next to two others exactly when three consecutive chairs are all occupied, so we count $8$-element subsets of the $16$ chairs with no three consecutive chairs chosen. The occupied chairs then form maximal blocks of size $1$ or $2.$ If there are $m$ blocks, then $8 - m$ of them are pairs and $2m - 8$ are singles, so $4 \le m \le 8,$ and the pair positions can be chosen in $\binom{m}{8-m}$ ways. The $8$ empty chairs create $9$ gaps (including the ends), and the $m$ blocks occupy $m$ distinct gaps: $\binom{9}{m}$ ways.

Therefore $$\begin{gathered} N = \sum_{m=4}^{8} \binom{m}{8-m}\binom{9}{m} \\ = 1 \cdot 126 + 10 \cdot 126 + 15 \cdot 84 \\ \quad {}+ 7 \cdot 36 + 1 \cdot 9 = 2907. \end{gathered}$$

The remainder when $N = 2907$ is divided by $1000$ is $907.$