Balanced String

The condition is essentially saying that the absolute difference of the numbers of 1's and -1's in any contiguous subsequence doesn't exceed 2.

Call an index $i$ ( $1 \leq i < n$ ) repetitive if $a_i= a_{i+1}$ . Note that if we fix the set of repetitive indices, there are exactly two possibilities for the sequence (one starts with 1, the other starts with -1, and the remaining positions are filled with alternating 1's and -1's).

Now, note that the parity of all repetitive indices are same. To see why (let's say A=1 and B=-1), suppose we have two consecutive A's. Then, there must exist a pair of two consecutive B's between the next pair of consecutive A's, otherwise the substring is like ...AABABABAA..., which violates the condition (number of A's - number of B's > 2). Thus, the next repetitive index must be a B, and all B's are placed at an even distance from the first repetitive index.

If the parity of all repetitive indices are odd, we get $2^{\lceil (n-1)/2 \rceil}$ possibilities (just select a subset consisting entirely of odd numbers among the first $n-1$ natural numbers). Similarly, if the parity of all repetitive indices are even, we get $2^{\lfloor (n-1)/2 \rfloor}$ possibilities. Overall, the answer is $2 (2^{\lceil (n-1)/2 \rceil} + 2^{\lfloor (n-1)/2 \rfloor} -1)$ (-1 because we double count the empty set for both cases).

In this case, our answer is $2(2^{1007} + 2^{1008} -1$ ), which evaluates to $\boxed{776}$ modulo 1000.