Trees with an odd number of independent sets

You are given a natural number $n$ (n \leq 1000) and a prime number $p$ (10^7 < p < 10^9). Your task is to determine the number of rooted trees with unmarked vertices that have an odd number of independent sets. Output the result modulo $p$.

A tree is called a rooted tree with unmarked vertices if one vertex is designated as the root, and the order of children for any vertex does not matter. In other words, two trees are considered identical if they become the same after reordering the non-root vertices. More formally, two rooted trees with unmarked vertices T_1 and T_2 are equal if there is a bijective function $f$ from the vertex set of T_1 to the vertex set of T_2 such that $f$ maps the root of T_1 to the root of T_2 and, for every edge $(u,v)$ in T_1, there is an edge (f(u), f(v)) in T_2.

A set of vertices of a graph (possibly empty) is called independent if no two vertices in the set are connected by an edge.