Description

一名年轻的生物学家正在研究进化史，她遇到了系统发育树。系统发育树展示了不同生物物种之间的进化关系。为了更好的可视化展示，系统发育树以平面嵌入的形式呈现，其叶子结点排列在圆周上。我们处理的是一棵无根树，其中叶子结点的度数为 1。树中的所有结点都被染上颜色，以便于区分不同的物种。

这位生物学家正在使用图形可视化软件，但软件需要一些辅助才能生成理想的布局。因此，她决定在平面嵌入中相邻的叶子之间添加边。树至少有 3 个叶子，她将这些叶子连接成一个环。下图展示了这样一棵示例（未染色的）树，虚线部分表示在相邻叶子之间额外添加的边。

:::align{center} :::align

现在，布局完成后，她想知道有多少种方式可以用 $K$ 种颜色为该图的结点染色。为了便于区分，每一对相邻的结点必须染成不同的颜色。请编写程序，读取该图的结构描述并计算合法染色的数量。

Input Format

第一行包含三个整数 $N, M, K$。
接下来的 $M$ 行中，每行包含一对整数 $A_i, B_i$，表示一条边的两个端点（结点编号为 $1 \sim N$）。同一行中的整数以空格分隔。

保证该图由一棵树（无环、连通、无向图）的平面嵌入出发，再在其叶子之间按圆周顺序添加边得到。图中不会出现自环或重边（即同一对结点之间不会有多条边）。

Output Format

输出一个整数，表示合法染色方案的数量，对 $1\ 000\ 000\ 007$ 取模。

8 12 3
2 5
3 6
2 6
5 4
4 1
1 6
7 5
2 7
3 4
2 8
7 8
1 8

24

Hint

输入限制

• $4 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$

翻译由 ChatGPT-5 完成