Counting Non‐Isomorphic M-Cycloalkanes

Antonio is interested in organic chemistry and wants your help in quickly computing the number of non‐isomorphic isomers for a certain hydrocarbon (cycloalkane) structure. To simplify the discussion, we make the following definitions:

• Cycloalkane: A cycloalkane with n carbon atoms is represented as an undirected, connected, simple graph with n vertices and n edges (which can be seen as a unique cycle together with tree branches attached to it). Moreover, the degree of each vertex does not exceed 4.
• M-cycloalkane: A cycloalkane that has at most m vertices on its cycle. (Note that every cycle must have at least 3 vertices because between any two vertices there is at most one edge.)
• Isomorphism: Two structures A and B (each with n carbon atoms) are isomorphic if and only if there exists a labeling (from 1 to n) of the carbon atoms in both structures such that for any two vertices v₁ and v₂, there is an edge between them in A if and only if there is an edge between the corresponding vertices in B (i.e. the graphs corresponding to A and B are isomorphic).

Given three integers: n (the number of carbon atoms), m (the maximum allowed number of cycle vertices), and a prime p, your task is to compute the number of non‐isomorphic M-cycloalkanes with n carbon atoms and output the answer modulo p.

In this problem, we do not consider whether a structure is chemically stable or other forms of isomers.

inputFormat

The input consists of a single line containing three space-separated integers: n, m, and p, where:

• n is the number of carbon atoms.
• m is the maximum number of vertices allowed in the cycle of the cycloalkane.
• p is a prime number; you should output the final count modulo p.

outputFormat

Output a single integer which is the number of non‐isomorphic M-cycloalkanes with n carbon atoms, taken modulo p.

sample

3 3 7

1