← 返回题目列表

AtCoder · kupc2016_j

J. 着色

中文机器翻译题面 查看原题

分数: 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