Toy Coloring

In the movie Big Hero 6, Little Hong uses his micro robots to build all sorts of shapes. Now, he has assembled a large toy for children using his micro robots, and he wants to color the toy to make it even more attractive.

The toy consists of \( n \) spherical endpoints (vertices) and \( m \) segments (edges) connecting these endpoints. An example toy with 5 endpoints and 4 edges is shown below, resembling a ball-and-stick molecular model.

The endpoints can move arbitrarily in space and the connecting segments can stretch arbitrarily as well (but no edge is ever added or removed). This flexibility means that if one coloring pattern of the toy can be transformed continuously into another, they are considered essentially the same.

Little Hong wants to color the toy using a palette of \( k \) colors (each endpoint is colored with one color chosen from \( k \) available colors). Two colorings are considered essentially identical if there exists a continuous transformation (or equivalently, a graph automorphism on the underlying structure) that maps one coloring onto the other.

Your task is to compute the number of essentially different colorings.

Hint: A coloring is an assignment of one of the \( k \) colors to each vertex. Two colorings are considered the same if one can be obtained from the other by a permutation of the vertices that preserves the connectivity structure of the toy. You may use Burnside's lemma for counting the orbits under the automorphism group of the graph.

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \) -- the number of endpoints, the number of edges, and the number of available colors respectively.

Each of the next \( m \) lines contains two integers \( u \) and \( v \) (1-indexed) indicating that there is an edge connecting vertex \( u \) and vertex \( v \).

Constraints: \( n \) is small (e.g. \( n \le 8 \)) so that checking all \( n! \) possible vertex permutations is feasible.

outputFormat

Print a single integer representing the number of essentially different colorings of the toy.

sample

3 2 2
1 2
2 3

6