Problem Statement

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

Output

Print the number of ways to paint the edges, modulo $10^9+7$.