### PROBLEM LINK:

**Author:** Misha Chorniy

**Tester:** Mugurel Ionut Andreica

**Editorialist:** Mugurel Ionut Andreica

### DIFFICULTY:

HARD

### PREREQUISITES:

### PROBLEM:

Count the number of colorings with **C** colors of the faces of a polyhedron, where two colorings are equivalent if one can be obtained from the other by using rotations or mirroring.

### EXPLANATION:

This is an application of Burnside’s lemma, which states that the total number of (non-equivalent) colorings is equal to the average number of fixed points of the group of permutations which define the equivalence relationships.

An *equivalence permutation* **(p(1), …, p(N))** has the meaning that any two colorings of the faces **1, …, N** in which each pair of faces **(i,p(i))** has the same color are equivalent.

So the general solution for this problem looks like this:

Step 1. Find all the equivalence permutations.

Step 2. For each such permutation compute its number of fixed points.

Step 3. Add up all the numbers computed at Step 2 and then divide the sum by the total number of equivalence permutations. This will be the answer for this problem.

Let’s see how to handle each of the 3 steps:

**Step 1**

An equivalence permutation is an automorphism of the graph defined by the faces of the polyhedron as nodes and the adjacency between them as edges. That is, a permutation **(p(1), …, p(N))** is an *equivalence permutation* if for every pair **(i,j)** we have that **Adjacent(i,j)=Adjacent(p(i),p(j))** (i.e. if the faces **i** and **j** are adjacent, then so must be the faces **p(i)** and **p(j)**; if the faces **i** and **j** are not adjacent then the faces **p(i)** and **p(j)** must also not be adjacent).

In order to generate all these permutation we can use recursive backtracking. When adding a new element **p(i)** to the permutation we first check that the prefix **p(1), …, p(i)** satisfies the adjacency rules mentioned above (i.e. we check the pairs of faces **(k,i)** with **1\leq k\leq i-1** to see if they satisfy the adjacency conditions). Only if the adjacency conditions are satisfied do we continue to the next element of the permutation.

You need to take a small leap of faith to implement this to verify that this backtracking approach is actually very fast.

**Step 2**

Let’s compute the number of fixed points of a permutation **(p(1), …, p(N))**. A **fixed point** is a coloring of the faces **(col(1), …, col(N))** which, when we permute the order of the faces according to the permutation **p**, we obtain the exact same sequence of colors (i.e. **(col(1), …, col(N)) = (col(p(1)), …, col(p(N)))**).

The number of fixed points of a permutation is related to the number of cycles of a permutation. Basically, every element in the same cycle of the permutation must be assigned the same color in order for the coloring to be a fixed point for the permutation. This means that for every cycle we can choose the color of all of its elements to be any of the **C** colors, but once the color is chosen, we need to assign it to all the elements in the cycle. Once we know this it’s easy to see that the number of fixed points of a permutation is **C^{numCycles}**, where **numCycles** is the number of cycles of the permutation (don’t forget to compute this number modulo 10^9+7).

**Step 3**

Adding up all the values from Step 2 is straight-forward (don’t forget to add them up modulo 10^9+7). In order to divide the sum by the total number of permutations **NP** we need to find **NP^{-1}** = the inverse of **NP** modulo 10^9+7. Since **10^9+7** is a prime number we have that **NP^{-1} = NP^{10^9+5}** (modulo 10^9+7). Then, dividing by **NP** is actually equivalent to multiplying by **NP^{-1}**.

### TESTER’S SOLUTIONS:

Tester’s solution can be found here.