Given a graph with $n$ vertices and $m$ undirected edges, count the number of distinct ways to color the vertices using $k$ colors. Two colorings are considered the same if, after renumbering all the vertices, the two graphs are isomorphic and the corresponding vertices have the same color. Output the result modulo $10^9+7$.
### Input
- The first line contains three positive integers $n,m,k.$
- The next $m$ lines, line $i$ contains two positive integers $u_i,v_i$ showing an edge of the graph.
### Output
- Output the answer of the problem modulo $10^9+7.$
### Constraints
- $1 \le n \le 10.$
- $1 \le m,k \le 40.$
### Example
Input
```
3 2 2
1 2
2 3
```
Output
```
6
```
