<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

282. Isomorphism
Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Let's call aa non-oriented graph such that each pair of different vertices is connected by exactly one edge, colored in any of M different colors. Two colored graphs areif the vertices of the first graph can be renumbered in such a way that it becomes equal to the second graph (i.e. the colors of the edges are the same).

You are given N, M and a prime P. Your task is to find the number of distinct non-isomorphic graphs having N vertices. The number should be output modulo P.

Input
The only line of the input contains three integers N, M, P (1≤ N≤ 53, 1≤ M≤ 1000, N
9).


Output
Output the answer to the problem in the only line of the output.

Example(s)
sample input
sample output
1 1 2
1

sample input
sample output
3 2 97
4

sample input
sample output
3 4 97
20



Novosibirsk SU Contest #2, by Novosibirsk Team #1

<|response|>
1. **Abridged Problem Statement**

We consider complete undirected graphs on \(N\) vertices. Every edge is colored with one of \(M\) colors. Two such colored graphs are considered the same if one can be obtained from the other by renaming vertices (i.e., via a permutation of vertices that preserves edge colors).

Given \(N\) (up to 53), \(M\) (up to 1000), and a prime modulus \(P\), compute the number of non‑isomorphic such graphs, modulo \(P\).

Formally: count the number of isomorphism classes of edge‑colored complete graphs on \(N\) vertices with colors from \(\{1,\dots,M\}\), modulo \(P\).


---

2. **Key Observations**

1. **Group action and Burnside’s Lemma**

   - Labelled version: there are \(\binom{N}{2}\) edges, each can be colored in \(M\) ways, so \(M^{\binom{N}{2}}\) labeled colorings.
   - We want to count colorings up to vertex relabeling, i.e. up to the action of the permutation group \(S_N\) on vertices.
   - Burnside’s Lemma:
     \[
     \#\text{(non-isomorphic colorings)} 
       = \frac{1}{|S_N|} \sum_{\pi \in S_N} \text{Fix}(\pi),
     \]
     where \(\text{Fix}(\pi)\) is the number of colorings unchanged (fixed) by permutation \(\pi\).

2. **Fixed colorings for a given permutation**

   - A permutation \(\pi\) acts on vertices, and hence on edges: \(\{u,v\} \mapsto \{\pi(u),\pi(v)\}\).
   - Edges are partitioned into orbits under repeated application of \(\pi\).
   - In a coloring that is fixed by \(\pi\), all edges in the same orbit must have the same color, but different orbits can choose colors independently.
   - If \(\pi\) has \(E(\pi)\) edge-orbits, then:
     \[
     \text{Fix}(\pi) = M^{E(\pi)}.
     \]

3. **Permutations with the same cycle structure behave identically**

   - Any permutation’s action on vertices decomposes into disjoint cycles.
   - Only the **cycle lengths** matter for how edges are permuted (not which specific vertices are in which cycle).
   - So we can group permutations by their cycle structure, i.e. by partitions of \(N\):
     \[
       N = c_1 + c_2 + \dots + c_k,\quad c_i \ge 1.
     \]
   - All permutations with this cycle type have:
     - The same number of edge-orbits \(E(\mathbf{c})\).
     - The same number of fixed colorings \(M^{E(\mathbf{c})}\).

4. **Counting edge-orbits for a given cycle structure**

   Let the cycle lengths be \(c_1, \dots, c_k\).

   - **Edges inside a cycle of length \(c\)**:

     Label the cycle \(v_0, v_1, \dots, v_{c-1}\) and let \(\pi(v_i) = v_{i+1 \bmod c}\).

     Each edge inside the cycle is an unordered pair \(\{v_i, v_j\}\), \(i \neq j\). Distances along the cycle modulo \(c\) behave like:

     - An edge is characterized by its (cyclic) distance \(d = (j - i) \bmod c\).
     - Because edges are undirected, distance \(d\) and \(c-d\) represent the same type.
     - Distinct edge-orbits correspond to distinct undirected distances.

     Number of such distances:
     - If \(c\) odd: \((c-1)/2\).
     - If \(c\) even: \(c/2\).

     In integer division, both equal `c // 2`. So:
     \[
       \text{edge-orbits inside cycle of length }c = \left\lfloor \frac{c}{2}\right\rfloor.
     \]

   - **Edges between two different cycles of lengths \(c_i, c_j\)**:

     Take cycles:
     - First: \(a_0,\dots,a_{c_i-1}\),
     - Second: \(b_0,\dots,b_{c_j-1}\).

     Edge \(\{a_x, b_y\}\) is sent under \(\pi\) to \(\{a_{x+1}, b_{y+1}\}\), then \(\{a_{x+2}, b_{y+2}\}\), etc. This is a cycle in the edge set whose length is \(\text{lcm}(c_i, c_j)\). There are \(c_i\cdot c_j\) such edges, so the number of distinct orbits is:
     \[
       \frac{c_i c_j}{\text{lcm}(c_i,c_j)} = \gcd(c_i, c_j).
     \]
     So between cycles \(i\) and \(j\) we get \(\gcd(c_i, c_j)\) edge-orbits.

   - **Total edge-orbits for partition \(\mathbf{c} = (c_1,\dots,c_k)\)**:
     \[
       E(\mathbf{c}) = \sum_{i=1}^k \left\lfloor \frac{c_i}{2}\right\rfloor + \sum_{1\le i<j\le k} \gcd(c_i, c_j).
     \]

5. **How many permutations have a given cycle structure?**

   For cycle structure \(c_1,\dots,c_k\) (order not important), the number of permutations with this structure:
   \[
     \#(\mathbf{c}) = \frac{N!}{\left(\prod_i c_i\right)\left(\prod_{\ell} \text{mult}(\ell)!\right)},
   \]
   where \(\text{mult}(\ell)\) is how many cycles have length \(\ell\).

6. **Burnside’s lemma simplified over partitions**

   Burnside:
   \[
     \text{answer} = \frac{1}{N!}\sum_{\pi\in S_N} M^{E(\pi)}.
   \]
   Grouping by cycle types:
   \[
     \text{answer} = \frac{1}{N!}\sum_{\mathbf{c}} \#(\mathbf{c}) \cdot M^{E(\mathbf{c})}.
   \]
   Plug in \(\#(\mathbf{c})\):
   \[
     \text{answer} 
       = \sum_{\mathbf{c}} \frac{M^{E(\mathbf{c})}}{\left(\prod_i c_i\right)\left(\prod_{\ell} \text{mult}(\ell)!\right)}.
   \]

   This expression no longer has \(N!\), which is nice because we can evaluate each term modulo \(P\) by computing a modular inverse of the denominator.

7. **Constraints and partition enumeration**

   - \(N \le 53\).
   - Number of integer partitions of 53 is about 200k (manageable).
   - For each partition, \(k\) (number of parts) is at most 53, but typically much smaller, and we do an \(O(k^2)\) loop for gcds.
   - Overall complexity is easily within time limits.

8. **Using modular arithmetic**

   - We must compute everything modulo prime \(P\).
   - Division modulo \(P\) is done via modular inverse using Fermat’s little theorem:
     \[
       a^{-1} \equiv a^{P-2} \pmod{P}.
     \]
   - Precompute factorials \(i!\bmod P\) for multiplicity factorials.


---

3. **Full Solution Approach**

1. **Precomputation**

   - Read \(N, M, P\).
   - Precompute factorials modulo \(P\): `fact[i] = i! % P` for \(0 \le i \le N\), since multiplicities of cycle lengths sum to at most \(N\).

2. **Enumerate all partitions of \(N\)**

   Use a recursive function `gen(last, sum_left, cur)`:

   - `cur` holds the current partition (list of cycle lengths).
   - `sum_left` is how much remains to reach \(N\); initially `sum_left = N`.
   - `last` is the maximum allowed next part, ensuring non-increasing order so each partition appears exactly once.

   Pseudocode:

   ```text
   gen(last, sum_left, cur):
       if sum_left == 0:
           process partition cur
           return its contribution

       total = 0
       for x from min(last, sum_left) down to 1:
           cur.push(x)
           total += gen(x, sum_left - x, cur)
           cur.pop()
       return total
   ```

3. **Processing a complete partition `cur`**

   For partition `cur = [c1, c2, ..., ck]`:

   1. Compute `ex = E(cur)`:

      - Start `ex = 0`.
      - Add intra-cycle orbits:
        ```text
        for each c in cur:
            ex += c // 2
        ```
      - Add inter-cycle orbits:
        ```text
        for i in 0..k-1:
            for j in i+1..k-1:
                ex += gcd(cur[i], cur[j])
        ```

   2. Compute the denominator components:

      - Product of cycle lengths:
        ```text
        prod_ci = 1
        for c in cur:
            prod_ci = (prod_ci * c) % P
        ```
      - Multiplicities of each length:
        ```text
        freq[length] = count of cycles with this length
        ```
      - Product of factorials of multiplicities:
        ```text
        prod_mfact = 1
        for each length in freq:
            count = freq[length]
            prod_mfact = (prod_mfact * fact[count]) % P
        ```

      Denominator:
      \[
        D = \left(\prod_i c_i\right)\left(\prod_{\ell} \text{mult}(\ell)!\right) \bmod P.
      \]

      Compute its modular inverse:
      \[
        D^{-1} \equiv D^{P-2} \pmod{P}.
      \]

   3. Compute number of fixed colorings for this cycle structure:

      ```text
      fix = M^ex % P
      ```

   4. Contribution of this partition:

      \[
        \text{contrib} = \text{fix} \cdot D^{-1} \bmod P.
      \]

      Return this contribution to the recursive caller.

4. **Final answer**

   - Start recursion with `gen(N, N, [])`.
   - Sum all contributions modulo \(P\).
   - That sum is exactly the required number of non-isomorphic colored complete graphs.

This directly implements the simplified Burnside formula over partitions:
\[
  \text{answer} = \sum_{\mathbf{c} \vdash N}
     \frac{M^{E(\mathbf{c})}}{\left(\prod_i c_i\right)\left(\prod_{\ell} \text{mult}(\ell)!\right)} \pmod{P}.
\]


---

4. **C++ Solution**

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t mod_pow(int64_t b, int64_t e, int64_t mod) {
    int64_t res = 1;
    b %= mod;
    while(e) {
        if(e & 1) {
            res = res * b % mod;
        }
        b = b * b % mod;
        e >>= 1;
    }
    return res;
}

int64_t mod_inverse(int64_t a, int64_t mod) { return mod_pow(a, mod - 2, mod); }

int n, m;
int64_t p;
vector<int64_t> fact;

int64_t gen(int last, int sum_left, vector<int>& cur) {
    if(sum_left == 0) {
        int64_t ex = 0;
        for(int c: cur) {
            ex += c / 2;
        }
        for(int i = 0; i < (int)cur.size(); i++) {
            for(int j = i + 1; j < (int)cur.size(); j++) {
                ex += gcd(cur[i], cur[j]);
            }
        }

        int64_t prod_ci = 1;
        for(int c: cur) {
            prod_ci = prod_ci * c % p;
        }
        map<int, int> freq;
        for(int c: cur) {
            freq[c]++;
        }

        int64_t prod_mfact = 1;
        for(auto pr: freq) {
            prod_mfact = prod_mfact * fact[pr.second] % p;
        }

        int64_t inv_denom = mod_inverse(prod_ci * prod_mfact % p, p);
        int64_t fix = mod_pow(m, ex, p);
        int64_t contrib = fix * inv_denom % p;
        return contrib;
    }
    int64_t total = 0;
    for(int x = min(last, sum_left); x >= 1; x--) {
        cur.push_back(x);
        total = (total + gen(x, sum_left - x, cur)) % p;
        cur.pop_back();
    }
    return total;
}

void read() { cin >> n >> m >> p; }

void solve() {
    // We use Burnside's lemma to count distinct colored complete graphs up to
    // isomorphism. The actions are permutations of the vertices, and by
    // Burnside's lemma we need to count fixed points for each permutation. A
    // coloring is fixed by permutation p if edge (i,j) has the same color as
    // edge (p[i], p[j]).
    //
    // Consider a cycle in the permutation: i[1], i[2], ..., i[k] where i[j+1] =
    // p[i[j]]. For the coloring to be fixed, edge (i[1], i[2]) must have the
    // same color as (p[i[1]], p[i[2]]) = (i[2], i[3]), and so on. This creates
    // orbits of edges that must share the same color.
    //
    // For edges between two different cycles of sizes c1 and c2: choosing any
    // x, y from the two cycles, we get (x,y) = (p[x], p[y]) = (p[p[x]],
    // p[p[y]]), etc. This visits every gcd(c1, c2) pair, yielding gcd(c1, c2)
    // orbits.
    //
    // For edges within the same cycle of size c: we have c*(c-1)/2 edges. For
    // any edge (x,y), we have (x,y) = (p[x], p[y]). Edges can be grouped by
    // their distance (y-x) mod c, and edges at distance k are in the same orbit
    // as edges at distance c-k (since we have a cycle). This gives c/2 orbits
    // per cycle.
    //
    // Computing this for every permutation is exponential in n. However, we
    // only care about the cycle structure, not the specific permutation. We
    // group by partitions of n (cycle sizes c1, c2, ..., ck). The number of
    // partitions of n is manageable - for n=53 it's only ~200k
    // (https://oeis.org/A000041).
    //
    // To summarize, we iterate through all partitions into cycles and count:
    //
    //     - Number of permutations with that cycle type: n! / (product of all
    //       ci * product of mult(i)!), where mult(i) is the frequency of cycle
    //       size i.
    //     - Number of edge orbits: sum of (ci / 2) over all cycles (intra-cycle
    //       orbits) + sum of gcd(ci, cj) over all pairs i < j (inter-cycle
    //       orbits).
    //     - Number of fixed colorings for that partition: m^(number of edge
    //       orbits).

    fact.assign(n + 1, 1);
    for(int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % p;
    }

    vector<int> cur;
    int64_t ans = gen(n, n, cur);
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

5. **Python Implementation with Detailed Comments**

```python
import sys
from math import gcd

# Read input: N, M, P
data = sys.stdin.read().strip().split()
n = int(data[0])   # number of vertices
m = int(data[1])   # number of colors
p = int(data[2])   # prime modulus

# Fast modular exponentiation: compute (base^exp) % mod
def mod_pow(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:          # if least significant bit of exp is 1
            result = (result * base) % mod
        base = (base * base) % mod  # square base
        exp >>= 1                   # shift exp right by 1 (divide by 2)
    return result

# Modular inverse using Fermat's little theorem (mod is prime)
def mod_inverse(a, mod):
    # a^(mod-2) is inverse of a modulo mod
    return mod_pow(a, mod - 2, mod)

# Precompute factorials: fact[i] = i! % p for i = 0..n
fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % p

# Recursive function to enumerate partitions of n
# last:     maximum allowed next part
# sum_left: remaining sum to reach n
# cur:      current list of parts (cycle lengths)
def gen(last, sum_left, cur):
    # Base case: we have a complete partition
    if sum_left == 0:
        # cur is a list of cycle lengths: [c1, c2, ..., ck]

        # 1) Compute ex = number of edge-orbits

        ex = 0

        # Intra-cycle orbits: floor(c / 2) for each cycle
        for c in cur:
            ex += c // 2

        # Inter-cycle orbits: gcd(ci, cj) for all pairs i < j
        k = len(cur)
        for i in range(k):
            for j in range(i + 1, k):
                ex += gcd(cur[i], cur[j])

        # 2) Compute denominator factors

        # Product of all cycle lengths: Π ci (mod p)
        prod_ci = 1
        for c in cur:
            prod_ci = (prod_ci * c) % p

        # Count multiplicities of each cycle length
        freq = {}
        for c in cur:
            freq[c] = freq.get(c, 0) + 1

        # Product of factorials of multiplicities: Π fact[count]
        prod_mfact = 1
        for count in freq.values():
            prod_mfact = (prod_mfact * fact[count]) % p

        # Full denominator D = prod_ci * prod_mfact (mod p)
        denom = (prod_ci * prod_mfact) % p

        # Inverse of denominator modulo p
        inv_denom = mod_inverse(denom, p)

        # 3) Number of fixed colorings: M^ex (mod p)
        fix = mod_pow(m, ex, p)

        # 4) Contribution from this partition: fix * inv_denom (mod p)
        contrib = (fix * inv_denom) % p
        return contrib

    # Recursive case: still have sum_left to fill
    total = 0
    upper = min(last, sum_left)

    # Try next part x from upper down to 1 (to enforce non-increasing order)
    for x in range(upper, 0, -1):
        cur.append(x)                        # choose x as next cycle length
        total = (total + gen(x, sum_left - x, cur)) % p
        cur.pop()                            # backtrack

    return total

# Start recursion with maximum part n, remaining sum n, and empty partition
answer = gen(n, n, [])

# Print final answer
print(answer)
```

This Python code mirrors the logic of the C++ solution:

- Enumerates all partitions of \(N\).
- For each partition:
  - Computes the number of edge-orbits \(E(\mathbf{c})\).
  - Constructs the denominator based on cycle lengths and their multiplicities.
  - Uses modular exponentiation and modular inverse to get the contribution.
- Sums all contributions modulo \(P\) to obtain the number of non‑isomorphic \(M\)-colored complete graphs on \(N\) vertices.