You are given a small undirected graph with n vertices (numbered 1..n) and m edges, and an integer k. A proper k-coloring assigns each vertex one of k colors (numbered 1..k) such that every edge connects two vertices of different colors.
Count the number of distinct proper k-colorings of the graph. Since this count can be large, print it modulo 1,000,000,007.
Input format
Line 1: three integers n, m, and k.
Next m lines: two integers u v (1-indexed) — an undirected edge between vertex u and vertex v.
Output format
A single integer: the number of proper k-colorings, modulo 1,000,000,007.
Constraints
- 1 ≤ n ≤ 7
- 0 ≤ m ≤ n*(n-1)/2, with no self-loops and no duplicate edges
- 1 ≤ k ≤ 5