Description

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.

Input Format

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

Output Format

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

10 10 66103

475

Hint

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