Advanced Number Theory · Challenge problem

Let $N$ be the number of permutations $\sigma$ of $\{1, 2, \ldots, 8\}$ such that $\sigma(i) \ne i$ and $\sigma(i) \ne i + 1$ for every $i$ (the second condition is empty for $i = 8$). Find the remainder when $N$ is divided by $1000$.