一位年轻的生物学家正在研究进化史，并接触到了系统发育树。系统发育树展示了各种生物物种之间的进化关系。为了获得更好的视觉呈现，它以平面嵌入的方式展示，其叶子节点按圆形排列。我们处理的是一棵无根树，其中叶子是度数为 1 的节点。树的所有节点都被着色，这使得区分不同的物种变得更容易。

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

现在可视化已经完成，她对用 $K$ 种颜色为该图的节点着色的方法数量感兴趣。为了便于视觉识别，每一对相邻节点都应该有不同的颜色。请编写一个程序，读取她图结构的描述并计算着色方案的数量。

输入格式

第一行包含整数 $N$、$M$ 和 $K$。图的边在接下来的 $M$ 行中给出，每行一对端点 $A_i$ 和 $B_i$（图的节点编号从 1 到 $N$）。同一行中的所有整数均由空格分隔。

保证该图是通过树（无环连通无向图）的平面嵌入，并将叶子节点按圆形连接而获得的。该图不包含自环或重边（即同一对节点之间不会有多条边）。

数据范围

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

输出格式

输出着色方案的数量，结果对 $1\,000\,000\,007$ 取模。

样例

输入 1

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

输出 1

24

说明

该示例对应于任务中说明的图。