Advanced Number Theory · Superchallenge problem

Find the number of subsets of $\{1, 2, \ldots, 9\}$ (including the empty set) that contain no two consecutive integers, modulo $1000$.