{"raw_statement":[{"iden":"statement","content":"在电影《超能陆战队》中，小宏可以使用他的微型机器人组合成各种各样的形状。\n\n现在他用他的微型机器人拼成了一个大玩具给小朋友们玩。为了更加美观，他决定给玩具染色。\n\n小宏的玩具由 $n$ 个球型的端点和 $m$ 段连接这些端点之间的边组成。下图给出了一个由 $5$ 个球型端点和 $4$ 条边组成的玩具，看上去很像一个分子的球棍模型。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/sefn3dug.png)\n\n由于小宏的微型机器人很灵活，这些球型端点可以在空间中任意移动，同时连接相邻两个球型端点的边可以任意的伸缩，这样一个玩具可以变换出不同的形状。在变换的过程中，边不会增加，也不会减少。\n\n小宏想给他的玩具染上不超过 $k$ 种颜色，这样玩具看上去会不一样。如果通过变换可以使得玩具变成完全相同的颜色模式，则认为是本质相同的染色。现在小宏想知道，可能有多少种本质不同的染色。"},{"iden":"input","content":"输入的第一行包含三个整数 $n,m,k$，分别表示小宏的玩具上的端点数、边数和小宏可能使用的颜色数。端点从 $1$ 到 $n$ 编号。\n\n接下来 $m$ 行每行两个整数 $a,b$，表示第 $a$ 个端点和第 $b$ 个端点之间有一条边。输入保证不会出现两条相同的边。"},{"iden":"output","content":"输出一行，表示本质不同的染色的方案数。由于方案数可能很多，请输入方案数除 $10007$ 的余数。"},{"iden":"note","content":"**【样例说明】**\n\n令 $(a,b,c)$ 表示第一个端点染成 $a$，第二个端点染成 $b$，第三个端点染成 $c$，则下面 $6$ 种本质不同的染色：$(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,2),(2,2,2)$。\n\n而 $(2,1,1)$ 与 $(1,1,2)$ 是本质相同的，$(2,2,1)$ 与 $(2,1,2)$ 是本质相同的。\n\n**【数据规模与约定】**\n\n对于 $20\\%$ 的评测数据，$1 \\le n \\le 5$，$1 \\le k \\le 2$。\n\n对于 $50\\%$ 的评测数据，$1 \\le n \\le 10$，$1 \\le k \\le 8$。\n\n对于 $100\\%$ 的评测数据，$1 \\le n \\le 10$，$1 \\le m \\le 45$，$1 \\le k \\le 30$。"}],"translated_statement":null,"sample_group":[["3 2 2\n1 2\n3 2","6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}