I don't even...

The problem can be solved by hand.

Note that we can let $S=A \cup B$ where $A \in \{1,3,5,...,29\}$ and $B \in \{2,4,6,...,30\}$ .

Now let $K_n$ be the number of subsets $T$ of $\{1,2,3,...,n\}$ such that for all $i \in T, i+1 \not\in T$ . Note that there are $K_{15}$ possibilities for $A$ and $B$ each such that $S$ is uneven (something like number of ways to pick from a row of $n$ people, picking no two adjacent people).

We can establish the recurrence relation $K_n = K_{n-1}+K_{n-2}$ by considering if $n$ is included or not included. $K_1 = 2, K_2 = 3$ thus $K_{15}$ is the 16th Fibonacci number, 1597 (this can be worked out by hand fairly fast).

Now there are $1597^2=2250409$ uneven subsets (also doable by hand, especially if you just focus on finding the last 3 digits).

Let $U_{n}$ represent the number of uneven subsets for the first $n$ positive integers. Also, let $I_{n}$ represent the first $n$ positive integers. We will create a recursion for $U_{n}$ based on the inclusion of $n$ and $n-1$ in the subset:

Case 1: $n$ is not included.

Our problem whittles down to finding the number of uneven subsets of $I_{n-1}$ , which is $U_{n-1}$ from our original definition of the symbol.

Case 2: $n$ and $n-1$ are included.

We cannot have $n-2$ or $n-3$ in our subset, due to our definition of an uneven subset. Note that for every uneven subset of $I_{n-4}$ , we can include $n$ and $n-1$ into it to get a subset of $I_{n}$ . Thus, the number of subsets for this case is $U_{n-4}$ .

Case 3: $n$ is included, but $n-1$ is not.

Here, the second largest integer we can include in the subset is $n-3$ . By the same argument as for Case 2, the total number of subsets for this case is $U_{n-3}$ .

These three cases cover all the ways $n$ and $n-1$ can be included in our subset, so we have $U_{n} = U_{n-1} + U_{n-3} + U_{n-4}$ . By counting out the subsets directly, we have $U_{0} = 1, U_{1} = 2, U_{2} = 4,$ and $U_{3} = 6$ as our initial conditions. Thus, after some brute force calculations using our recursion, we have $U_{30} = 2550409$ , which leaves a remainder of $\boxed{409}$ when divided by $1000$ .