Description

If every edge of an undirected complete graph (a complete graph means that any two distinct vertices are connected by exactly one edge) is colored with one color, we call such a graph a colored graph. If two colored graphs have the same number of vertices and, after some relabeling of the vertices, the colors of the corresponding edges are identical, then the two colored graphs are said to be isomorphic. The following two graphs are isomorphic, because if you permute the vertices of the first graph $(1,2,3,4)$ into $(4,1,2,3)$ in the second graph, you will find they are the same.

Your task is to compute, among all undirected complete graphs on $n$ vertices whose edges are colored using at most $m$ colors, how many pairwise non-isomorphic graphs there are. Since the answer can be very large, you only need to output the remainder modulo $p$ (where $p$ is a prime).

Input Format

The input contains a single line with three positive integers $n,m,p$.

Output Format

Output the remainder of the total count modulo $p$.

1 1 2

1

3 2 97

4

3 4 97

20

Hint

For $100\%$ of the testdata, $1 \leq n \leq 53$, $1 \leq m \leq 1000$, $n < p \leq 10^9$.

Translated by ChatGPT 5