Home

Contest: Task: Related: TaskC TaskE

Score : $1300$ points

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$.

Sample Input 1

4 4 2
1 2
2 3
3 1
3 4

Sample Output 1

8

Sample Input 2

5 2 3
1 2
4 5

Sample Output 2

9

Sample Input 3

11 12 48
3 1
8 2
4 9
5 4
1 6
2 9
8 3
10 8
4 10
8 6
11 7
1 8

Sample Output 3

569519295