Painting Graphs with AtCoDeer

One day, AtCoDeer the deer found a simple graph (that is, a graph without self-loops and multiple edges) with $N$ vertices and $M$ edges, and brought it home. The vertices are numbered $1$ through $N$ and mutually distinguishable, and the edges are represented by $(a_i,b_i) (1≦i≦M)$. He is painting each edge in the graph in one of the $K$ colors of his paint cans. As he has enough supply of paint, the same color can be used to paint more than one edge. The graph is made of a special material, and has a strange property. He can choose a simple cycle (that is, a cycle with no repeated vertex), and perform a circular shift of the colors along the chosen cycle. More formally, let $e_1$, $e_2$, $...$, $e_a$ be the edges along a cycle in order, then he can perform the following simultaneously: paint $e_2$ in the current color of $e_1$, paint $e_3$ in the current color of $e_2$, $...$, paint $e_a$ in the current color of $e_{a-1}$, and paint $e_1$ in the current color of $e_{a}$. Figure $1$: An example of a circular shift Two ways to paint the edges, $A$ and $B$, are considered the same if $A$ can be transformed into $B$ by performing a finite number of circular shifts. Find the number of ways to paint the edges. Since this number can be extremely large, print the answer modulo $10^9+7$. ## Constraints * $1≦N≦50$ * $1≦M≦100$ * $1≦K≦100$ * $1≦a_i,b_i≦N (1≦i≦M)$ * The graph has neither self-loops nor multiple edges. ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$ [samples]