分数: 300 点
问题陈述
麦肯的生日快到了。由于 Mikan 非常喜欢图表,Aroma 决定今年也给她一张无向图。
Aroma 购买了一个连通无向图,其中包括 n 顶点和 n 边缘。 顶点编号从 1 到 n,并且对于每个顶点 i(1 \leq i \leq n),顶点 i 和 vartex a_i 与无向边连接。 Aroma 认为只给出现成的图表并没有什么意思,决定把它画出来。 计算购买的图形的顶点绘制方式的数量 k 颜色取模 10^9 + 7. 如果通过排列顶点数,以一种方式绘制的图形可以与以另一种方式绘制的图形相同,则两种方式被认为是相同的。
约束
- 1 \leq n \leq 10^5
- 1 \leq k \leq 10^5
- 1 \leq a_i \leq n (1 \leq i \leq n)
- 给定的图形已连接
- 给定的图不包含自环或多重边。
输入
每个数据集均以以下格式从标准输入给出。
n k a_1 : a_n
输出
输出以 k 种颜色为模绘制给定图的顶点的方法数 10^9 + 7 一行。
示例输入 1
4 2 2 3 1 1
示例输出 1
12
示例输入 2
4 4 2 3 4 1
示例输出 2
55
示例输入 3
10 5 2 3 4 1 1 1 2 3 3 4
示例输出 3
926250