I don't even...

Probability Level 3

Define a subset $S$ of the first $30$ positive integers to be uneven if, for all $i \in S$ , $i+2 \notin S$ . For example, $\{1, 2\}$ is an uneven subset, while $\{1, 2, 3\}$ is not. If $N$ represents the number of uneven subsets, find the remainder when $N$ is divided by $1000$ .

Notes:

The empty set is considered to be an uneven subset.

You may want use a calculator at the end.