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 109+7.
### Input
- The first line contains three positive integers n,m,k.
- The next m lines, line i contains two positive integers ui,vi showing an edge of the graph.
### Output
- Output the answer of the problem modulo 109+7.
### Constraints
- 1≤n≤10.
- 1≤m,k≤40.
### Example
Input
3221223
Output
6
