P8633 [Lanqiao Cup 2015 National B] Model Coloring

In the movie *Big Hero 6*, Hiro can use his micro robots to combine into various shapes. Now he has used his micro robots to build a big toy for kids to play with. To make it look nicer, he decided to color the toy. Hiro’s toy consists of $n$ spherical vertices and $m$ edges connecting these vertices. The figure below shows a toy made of $5$ spherical vertices and $4$ edges, which looks like a ball-and-stick molecular model.  Because Hiro’s micro robots are very flexible, these spherical vertices can move freely in space, and the edges connecting adjacent vertices can stretch or shrink freely, so the toy can change into different shapes. During the transformation, no edges will be added or removed. Hiro wants to color his toy using no more than $k$ colors, so that the toy will look different. If by transforming the toy it can become exactly the same color pattern, then the two colorings are considered essentially the same. Now Hiro wants to know how many essentially different colorings are possible.

The first line contains three integers $n, m, k$, representing the number of vertices, the number of edges, and the number of colors Hiro may use. The vertices are numbered from $1$ to $n$. The next $m$ lines each contain two integers $a, b$, indicating that there is an edge between vertex $a$ and vertex $b$. The input guarantees that there will not be two identical edges.

Output one line indicating the number of essentially different coloring schemes. Since the number of schemes may be large, output the remainder of the answer modulo $10007$.

**[Sample Explanation]** Let $(a, b, c)$ denote that the first vertex is colored $a$, the second vertex is colored $b$, and the third vertex is colored $c$. Then the following $6$ colorings are essentially different: $(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,2),(2,2,2)$. And $(2,1,1)$ is essentially the same as $(1,1,2)$, and $(2,2,1)$ is essentially the same as $(2,1,2)$. **[Constraints]** For $20\%$ of the testdata, $1 \le n \le 5$, $1 \le k \le 2$. For $50\%$ of the testdata, $1 \le n \le 10$, $1 \le k \le 8$. For $100\%$ of the testdata, $1 \le n \le 10$, $1 \le m \le 45$, $1 \le k \le 30$. Translated by ChatGPT 5