P5818 [JSOI2011] Counting Structural Isomers

Antonio has recently become interested in organic chemistry, and he wants you to help him quickly compute the number of structural isomers of a certain type of hydrocarbon. For convenience, we define the following: - Cycloalkane: A cycloalkane with $n$ carbon atoms can be represented as an undirected connected simple graph with $n$ vertices and $n$ edges (a base cycle plus outward trees). The degree of each vertex is at most $4$. - M-cycloalkane: A cycloalkane in which at most $m$ vertices lie on the cycle. (Note that the cycle must contain at least $3$ vertices, because between any two vertices there can be at most $1$ edge.) - Isomorphism: Suppose structures $A$ and $B$ both have $n$ carbon atoms. $A$ and $B$ are isomorphic if and only if we can label every carbon atom in both $A$ and $B$ with numbers $1 \sim n$ such that for two carbon atoms labeled $v_1$ and $v_2$, there is an edge between them in $A$ if and only if there is an edge between them in $B$. (In other words, the corresponding graphs of $A$ and $B$ are isomorphic.) Now, given $n$ and $m$, Antonio wants you to count how many pairwise non-isomorphic M-cycloalkanes with $n$ carbon atoms there are. Since this number may be very large, you only need to output it modulo $p$ ($p$ is a prime). In this problem, we do not consider whether a structure can exist stably in chemistry, and we do not consider other types of isomerism.

The input contains only one line with three integers $n$, $m$, and $p$, separated by spaces.

Output exactly one line: the number of pairwise non-isomorphic M-cycloalkanes with $n$ carbon atoms, modulo $p$.

**Constraints** $3 \le n \le 1000$, $3 \le m \le 50$, $m \le n$, $10^4 \le p \le 2 \times 10^9$, and $p$ is guaranteed to be prime. Translated by ChatGPT 5