Counting Non-Isomorphic Colored Complete Graphs

Given a complete undirected graph with n vertices, each edge is colored with one of at most m colors. Two colored graphs (with the same number of vertices) are considered isomorphic if there exists a re‐labeling of the vertices that makes the colors of corresponding edges identical.

Your task is to compute the number of pairwise non‐isomorphic colored complete graphs on n vertices (with edge colors chosen from {1,2,…,m}). Since the answer can be very large, output the answer modulo a prime number p.

A classical application of Burnside’s lemma (or equivalently Pólya’s enumeration theorem) shows that the answer is

[ \frac{1}{n!}\sum_{\sigma\in S_n} m^{f(\sigma)} \pmod p, ]

where for each permutation (\sigma\in S_n) the number (f(\sigma)) is the number of orbits induced by (\sigma) on the edge set of the complete graph. In particular, if the cycle type of (\sigma) is given by cycles of lengths (c_1, c_2, \dots, c_k), then it can be shown that

[ f(\sigma)=\sum_{i=1}^{k}\left\lfloor \frac{c_i}{2} \right\rfloor+\sum_{1\le i<j\le k}\gcd(c_i,c_j). ]

An alternate equivalent formulation is to sum over conjugacy classes (i.e. cycle types). If for every (i) ((1\le i\le n)) the number of cycles of length (i) in (\sigma) is (a_i) (with (\sum_{i=1}^{n} i,a_i=n)), then the total contribution of this conjugacy class is

[ \frac{n!}{\prod_{i=1}^{n}(i^{a_i}a_i!)},m^{f(a_1,a_2,\dots,a_n)}, ]

where

[ f(a_1,\dots,a_n)=\sum_{i=1}^{n}a_i\left\lfloor \frac{i}{2} \right\rfloor+\sum_{1\le i<j\le n}a_ia_j\gcd(i,j)+\sum_{i=1}^{n}\binom{a_i}{2}i. ]

Finally, the desired answer is

[ \frac{1}{n!}\sum_{\substack{a_1,a_2,\dots,a_n\ \sum i,a_i=n}} \frac{n!}{\prod_{i=1}^{n}(i^{a_i}a_i!)},m^{f(a_1,\dots,a_n)}\pmod{p}. ]

It turns out that although the formula looks complicated, one may enumerate over all partitions (i.e. all possible sequences ((a_1, a_2,\dots,a_n)) with (\sum_{i=1}^{n} i,a_i=n)) in order to determine the answer. In this problem, since n is relatively small, you are required to implement such an algorithm.

inputFormat

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

• n (1 ≤ n ≤ 10) is the number of vertices.
• m (1 ≤ m ≤ 10⁹) is the number of available colors.
• p is a prime number (for example, p might be around 10⁶ or higher).

You may assume that p is large enough so that all necessary modular inverses exist.

outputFormat

Output a single integer — the number of pairwise non-isomorphic colored complete graphs on n vertices with colors chosen from at most m colors, taken modulo p.

sample

2 3 1000003

3