Find the number of sequences $(a_n)_{n=1}^\infty$ of integers satisfying $a_n \ne -1$ and
\[a_{n+2} =\frac{a_n + 2006}{a_{n+1} + 1}\]
for each $n \in \mathbb{N}$.
1. We start with the given recurrence relation:
   \[
   a_{n+2} = \frac{a_n + 2006}{a_{n+1} + 1}
   \]
   for each \( n \in \mathbb{N} \).

2. We derive the expression:
   \[
   (a_{n+3} - a_{n+1})(a_{n+2} + 1) = a_{n+2} - a_n
   \]
   This can be obtained by manipulating the recurrence relation and considering the differences between terms.

3. Suppose there are infinitely many \( n \) such that \( a_{n+3} \neq a_{n+2} \). Then we get:
   \[
   |a_3 - a_1| = \left| \prod_{i=1}^{k} (a_i + 1)(a_{k+1} - a_{k-1}) \right|
   \]
   This implies that the product of differences and terms must be bounded, which is a contradiction if there are infinitely many such \( n \).

4. Therefore, there must be finitely many \( i \) such that \( a_i \neq 0 \) or \( a_i \neq -2 \). This implies that after some stage, all \( a_i \) must be either \( 0 \) or \( -2 \).

5. However, this is not possible because substituting \( a_i = 0 \) or \( a_i = -2 \) into the recurrence relation does not satisfy the condition \( a_n \neq -1 \).

6. Hence, there are finitely many \( n \) such that \( a_{n+3} \neq a_{n+2} \). After some stage, for all \( n > N \), we get \( a_{n+3} = a_{n+2} \).

7. For all \( n > N \), we have:
   \[
   a_n a_{n+1} = 2006
   \]
   Let \( a = a_N \) and \( b = a_{N+1} \). Then:
   \[
   ab = 2006
   \]

8. Suppose \( a_N \neq x \). Then either:
   \[
   b = \frac{x + 2006}{a + 1} \implies x = b
   \]
   or:
   \[
   a = \frac{x + 2006}{b + 1} \implies x = a
   \]

9. Thus, we conclude that all \( a_i \in \{a, b\} \) where \( ab = 2006 \) and \( a_n = a_{n+2} \) for all \( n \).

The final answer is \( \boxed{a_i \in \{a, b\} \text{ where } ab = 2006 \text{ and } a_n = a_{n+2} \text{ for all } n} \)